Data structures - Arrays, tuples, lists and records (1.4.2)
- 20p13280
- Apr 14
- 3 min read
This post covers the following topics:
Static vs Dynamic
Arrays
Tuples
Records
Static vs Dynamic
In static data structures the size of the structure is set at the beginning of the program when the data structure is created, the size cannot be changed. This makes the data structures easier to implement but they are more limited.
In dynamic data structures there is no size limit and they can expand and shrink as needed. This does make them more complex than static data structures.
Dynamic | Static |
|---|---|
Memory is allocated to the data structures dynamically as the program executes. | The memory is allocated when the program is compiled and the structure is created, fixed size. |
(-) As memory allocation is dynamic it means that there can be an 'overflow' if it exceeds the allowed memory limit on the data structure. | (+) There is no memory allocation and so no issues when adding and removing items. |
(+) Uses memory efficiently as it only uses what's required. | (-) It can be very inefficient if a large amount of the memory allocated isn't being used as the structure is empty. |
(-) Harder to implement due to the requirement to keep track of size and memory locations. | (+) Easier to implement as everything is consecutive and allocated. |
Typically larger and more complex data structures are made up of more simpler ones for example this can be done to create a binary tree or a stack.
Arrays
1D (One Dimensional) Arrays
An Array is a collection of variables on the same type all grouped with a single identifier. Each position in an array is given a number, with position 0 being the first element. It's easy to change and retrieve elements, you can do array[x] to get elements and array[x] = y to set a value of a variable in an array. Arrays are static so they have a fixed length.
Two Dimensional Arrays
Two Dimensional arrays are arrays that are made up of more arrays, there's no limit to how many dimensions an array can be made of. For example to define a a 2D array in python it looks like this:
Names = [['Sam', 'Lucy', 'James', 'Jack', 'Jane'],…
['Peter', 'Sarah', 'Adam', 'Karen', 'Verity'],…
['Emily', 'Edward', 'Dominic', 'Justyn', 'Jake']]Changing data within a 2D (or more) array can be done by using the [x] syntax repeated for each array. For example array[x][y][z][a][b][c] would be used on a 6D list.
Array values are stored in contiguous memory locations (physical unbroken block of memory.). Within 2D (and more) arrays the are allocated in row-major order, where the memory layout is all the values in row 0, then row 1, etc.
Tuples
A Tuple is the python equivalent of an array.
Like records they are used to group together related data, they appear very similar to 1D arrays. However tuples can't be edited which makes them immutable and tuples can contain values of different types unlike arrays, so e.g. a tuple can contain a Boolean, string and an int all in the same tuple.
Example of creating a tuple in python:
student = ('James', 'Smith', '30/01/2000', 'Computer Science')To retrieve data from a tuple it's the same syntax as an array, for example student[3] would return "Computer Science". However it's not possible to do student[3] = "Maths" as tuples are immutable and can't be modified. This makes tuples commonly used when data needs to be accessed a a list but shouldn't be changed.
List
A list is a simple data structure like an array and a tuple but is mutable and dynamic. Lists can hold a range of data types within their elements and can be edited once they have been initiated. A list is like an array which is an ordered data structure as a list has indexes (0,1,2,etc.) and has the same syntax for retrieving and setting data as a 1D array does. Since lists are dynamic this means that the size is variable and means that as many elements as needed can be added. Elements can also be deleted.
Records
A record is used to organise data by attributes, like a record within a database. To access data you can do record.attribute. A record is an unordered data structure however indices (like array indexes) can be added to provide order on a particular field.
Example of creating a record in Java:
public record Person(String name, String address) {
public Person(String name, String address) {
this.name = name;
this.address = address;
}
}
.