1.4.2a Arrays, Lists, Tuples and Records — OCR H446

Data Structures Overview

A data structure is a way of organising and storing data so it can be accessed and modified efficiently. Choosing the right data structure is fundamental to good algorithm design. Different structures make different operations (insertion, deletion, searching) faster or slower.

Arrays

An array is a fixed-size, ordered collection of elements all of the same data type, stored in contiguous memory locations.

Static: size is fixed at declaration — cannot grow or shrink at runtime
Zero-indexed (in most languages): first element is at index 0
Direct access (O(1)): any element can be accessed instantly using its index
Homogeneous: all elements must be the same type

1D Array

-- A 1D array of 5 integers (pseudocode)
scores = [84, 67, 91, 55, 78]
-- Access: scores[0] = 84, scores[4] = 78

2D Array (Matrix)

-- A 2D array: 3 rows, 4 columns
grid = [[1,2,3,4],
        [5,6,7,8],
        [9,10,11,12]]
-- grid[1][2] = 7 (row 1, column 2)

Array Address Calculation

For a 1D array starting at base address B, element size w bytes, element at index i is at:

Address = B + (i × w)

For a 2D array with n columns (row-major order), element [r][c] is at:

Address = B + ((r × n + c) × w)

Lists

A list is an ordered, dynamic collection — unlike arrays, lists can grow and shrink at runtime:

Elements can be of mixed types (in Python/pseudocode)
Support operations: append, insert, remove, pop, length
Slower random access than arrays (linked list implementation = O(n); Python list = O(1) via dynamic array)
More flexible than arrays for variable-length data

myList = [10, "hello", True, 3.14]
myList.append(42)      -- [10, "hello", True, 3.14, 42]
myList.remove(True)    -- [10, "hello", 3.14, 42]

Tuples

A tuple is an ordered, immutable collection — once created, it cannot be changed (no adding, removing, or modifying elements):

Can contain mixed types
More memory-efficient than lists (immutability allows optimisation)
Use cases: coordinates (x, y, z), RGB colour values, database rows, function returning multiple values
Accessed by index like arrays, but cannot be modified

point = (4, 7, -2)              -- x, y, z coordinates
colour = (255, 128, 0)          -- RGB orange
print(point[0])                 -- 4
-- point[0] = 10  ← Error! Tuples are immutable

Records

A record (called a struct in some languages) is a collection of named fields which can be of different types, grouped together to represent a single entity:

Each field has a name and a data type
Fields are accessed by name, not by index
Similar to a row in a database table
Used to represent real-world objects: Student, Employee, Product

-- Define a record type
TYPE Student
    name : String
    age  : Integer
    grade: Real
ENDTYPE

-- Create and use a record
s.name  = "Alice"
s.age   = 17
s.grade = 89.5

Comparison Table

Feature	Array	List	Tuple	Record
Size	Fixed	Dynamic	Fixed	Fixed
Type	Homogeneous	Mixed	Mixed	Mixed (named)
Mutable?	Yes	Yes	No	Yes
Access	By index	By index	By index	By field name
Use case	Fixed collection same type	Variable-length ordered data	Immutable grouped values	Represent a real-world object/entity

Exam tip: The key distinction for tuples is immutability — once created, you cannot change them. If asked why tuples are used instead of lists, the answer is: immutability guarantees data integrity, and they use less memory. Coordinates, RGB values, and database records are classic tuple examples.

Exam tip: Arrays store elements in contiguous memory, which enables O(1) direct access via index. The address formula B + (i × w) is important for computing element addresses in memory — this can appear in exam questions.

⚠ Common Mistakes

Saying arrays can hold mixed types — standard arrays are homogeneous (all same type). Lists/tuples can hold mixed types.
Confusing lists (dynamic, mutable) with tuples (fixed-size, immutable) — the key difference is mutability.
Forgetting zero-indexing — in most pseudocode and languages, the first element is at index 0, not 1.

✓ Notes completed!

▶

Video coming soon

Click to advance · Arrow keys also work

Click slide or press arrow keys to navigate

✍

Worksheet — 1.4.2a Arrays, Lists, Tuples and Records

8 questions · 20 marks · instantly marked

Q1State two differences between an array and a list.[2 marks]

✓ Mark scheme

Any two of: Arrays are fixed-size (static); lists are dynamic (can grow/shrink) [1]. Arrays are homogeneous (all same type); lists can hold mixed types [1]. Arrays use contiguous memory with direct index access; list implementations may use dynamic arrays or linked nodes [1].

Q2An array starts at base address 2000. Each element is 4 bytes. Calculate the memory address of the element at index 7.[2 marks]

✓ Mark scheme

Address = Base + (index × element size) [1] = 2000 + (7 × 4) = 2000 + 28 = 2028 [1].

Q3Explain what is meant by a tuple being immutable and give one situation where a tuple would be preferred over a list.[3 marks]

✓ Mark scheme

Immutable means the contents of the tuple cannot be changed after it is created — elements cannot be added, removed, or modified [1]. A tuple would be preferred when the data should not change — e.g. storing a 2D coordinate (x, y) or an RGB colour value (r, g, b) [1] — because immutability provides data integrity guarantees and tuples use less memory than lists [1].

Q4A 2D array has 5 rows and 4 columns. The base address is 1000 and each element is 2 bytes. Using row-major ordering, calculate the address of element [2][3].[3 marks]

✓ Mark scheme

Formula: Address = Base + ((row × num_columns + column) × element_size) [1] = 1000 + ((2 × 4 + 3) × 2) [1] = 1000 + (8+3) × 2 = 1000 + 11 × 2 = 1000 + 22 = 1022 [1].

Q5Describe a record data structure and explain how it differs from an array. Give an example of a suitable record in a school context.[4 marks]

✓ Mark scheme

A record is a data structure that groups together related fields of different types under a single entity; each field has a name and type [1]. A record differs from an array in that: fields can be of different types (arrays are homogeneous) [1]; fields are accessed by name rather than index [1]. Example: a Student record with fields name (String), age (Integer), score (Real) — representing a single student's information [1].

Q6A programmer stores the (latitude, longitude) coordinates of a city as a Python tuple rather than a list. Justify this choice.[2 marks]

✓ Mark scheme

A tuple is immutable — the coordinates of a city are fixed and should not be accidentally modified [1]; using a tuple prevents inadvertent changes that could corrupt the data, and tuples also use less memory than equivalent lists [1].

Q7Explain why arrays provide O(1) (constant time) access to any element, regardless of the array size.[2 marks]

✓ Mark scheme

Arrays store elements in contiguous (consecutive) memory locations [1]. Given the base address and element size, the address of any element can be calculated directly using the formula B + (i × w) — this is a single arithmetic operation, taking constant time regardless of the array's length [1].

Q8A teacher needs to store, for each student: their name, form group, 5 subject grades, and whether they receive free school meals. Design a record structure for this, including field names and data types.[4 marks]

✓ Mark scheme

Suitable record with correct types: name: String [1]; formGroup: String (or Char) [1]; grades: Array[1..5] of Integer/Real (or 5 separate grade fields) [1]; freeMeals: Boolean [1]. Award marks for each correctly named and typed field — field names may vary but types must be appropriate.

Topic Quiz

1 of 15

You scored

out of 15

Card 1 of 15

Click to reveal

🎉

Complete!

Term	Definition

Data Structures Overview

Arrays

1D Array

2D Array (Matrix)

Array Address Calculation

Lists

Tuples

Records

Comparison Table

Worksheet — 1.4.2a Arrays, Lists, Tuples and Records

Mini Test — 1.4.2a Data Structures