Data structures organise and store data efficiently. Choosing the right structure is crucial for program performance.
Arrays
Definition
An array is an ordered, fixed-size collection of elements, all of the same data type, stored in contiguous memory locations.
Key Point
Array Characteristics:
• Fixed size (declared at creation)
• Same data type for all elements
• Indexed from 0 (in most languages)
• Direct access by index - O(1) time
• Contiguous memory - efficient for CPU cache
• Fixed size (declared at creation)
• Same data type for all elements
• Indexed from 0 (in most languages)
• Direct access by index - O(1) time
• Contiguous memory - efficient for CPU cache
One-Dimensional Arrays
Worked Example
Worked Example: 1D Array
pseudocode
// Declare and initialise
scores = [85, 92, 78, 90, 88]
// Access by index (0-based)
firstScore = scores[0] // 85
thirdScore = scores[2] // 78
lastScore = scores[4] // 88
// Modify an element
scores[1] = 95 // scores is now [85, 95, 78, 90, 88]
// Iterate through array
for i = 0 to 4:
print(scores[i])
end for
Two-Dimensional Arrays
Definition
A 2D array is like a table with rows and columns - an array of arrays.
Worked Example
Worked Example: 2D Array
pseudocode
// Seating plan - 3 rows, 4 columns
seats = [
["A1", "A2", "A3", "A4"], // Row 0
["B1", "B2", "B3", "B4"], // Row 1
["C1", "C2", "C3", "C4"] // Row 2
]
// Access: array[row][column]
seat = seats[1][2] // "B3" (row 1, column 2)
// Iterate through 2D array
for row = 0 to 2:
for col = 0 to 3:
print(seats[row][col])
end for
end for
Three-Dimensional Arrays
Definition
A 3D array is an array of 2D arrays. Each element is reached with three indexes, and the number of elements is the three sizes multiplied together.
The specification expects arrays of up to three dimensions. A 3D array suits data with three ways of dividing it, such as shop, week and day.
Worked Example
Worked Example: 3D Array
pseudocode
// Sales for 2 shops, over 4 weeks, on 7 days: 2 x 4 x 7 = 56 elements
array sales[2][4][7]
// Access: array[shop][week][day]
sales[1][0][6] = 250 // shop 1, week 0, day 6
// Iterate through a 3D array: one loop for each dimension
total = 0
for shop = 0 to 1:
for week = 0 to 3:
for day = 0 to 6:
total = total + sales[shop][week][day]
end for
end for
end for
Records
Definition
A record is a data structure that groups together related items of potentially different data types. Each item is called a field.
Worked Example
Worked Example: Records
pseudocode
// Define record structure
record Student:
string studentID
string firstName
string lastName
integer age
real averageGrade
end record
// Create a record
student1 = new Student()
student1.studentID = "S12345"
student1.firstName = "Alice"
student1.lastName = "Smith"
student1.age = 17
student1.averageGrade = 82.5
// Access fields using dot notation
print(student1.firstName) // "Alice"
print(student1.averageGrade) // 82.5
Key Point
Record vs Array:
• Array: All elements same type, accessed by index
• Record: Elements can be different types, accessed by field name
• Array: All elements same type, accessed by index
• Record: Elements can be different types, accessed by field name
Lists
Definition
A list is an ordered collection of elements that can grow and shrink dynamically. Unlike arrays, lists can change size and often allow mixed data types.
Worked Example
Worked Example: List Operations
pseudocode
// Create a list
myList = [10, 20, 30, 40, 50]
// Common operations:
myList.append(60) // Add to end: [10, 20, 30, 40, 50, 60]
myList.insert(0, 5) // Insert at index: [5, 10, 20, 30, 40, 50, 60]
myList.remove(30) // Remove value: [5, 10, 20, 40, 50, 60]
item = myList.pop() // Remove and return last: 60
length = length(myList) // Get length: 5
position = myList.index(20) // Find position: 2
Key Point
Size
• Array: Fixed at creation
• List: Can grow/shrink
Data types
• Array: Same type
• List: Often mixed types
Memory
• Array: Contiguous
• List: May be non-contiguous
Access time
• Array: O(1) by index
• List: O(1) by index
Insert/Delete
• Array: Expensive (shift elements)
• List: Can be O(1)
• Array: Fixed at creation
• List: Can grow/shrink
Data types
• Array: Same type
• List: Often mixed types
Memory
• Array: Contiguous
• List: May be non-contiguous
Access time
• Array: O(1) by index
• List: O(1) by index
Insert/Delete
• Array: Expensive (shift elements)
• List: Can be O(1)
Tuples
Definition
A tuple is an ordered, immutable collection of elements. Once created, it cannot be modified.
Key Point
Tuple Characteristics:
• Fixed size (like arrays)
• Immutable (unlike arrays and lists)
• Can contain mixed data types
• Useful for fixed collections (coordinates, RGB values)
• Fixed size (like arrays)
• Immutable (unlike arrays and lists)
• Can contain mixed data types
• Useful for fixed collections (coordinates, RGB values)
Worked Example
Worked Example: Tuples
pseudocode
// Create a tuple
coordinates = (10, 20) // x, y coordinates
colour = (255, 128, 0) // RGB values
person = ("Alice", 17, "A") // Mixed types
// Access elements
x = coordinates[0] // 10
y = coordinates[1] // 20
// Tuples are immutable - cannot change
coordinates[0] = 15 // ERROR! Cannot modify tuple