Arrays and Records

This lesson covers arrays and records — two fundamental static data structures used extensively in A-Level Computer Science. Arrays store an indexed collection of elements of the same type, while records group related data of different types under named fields. Together they are the building blocks from which more complex structures (such as an array of records, the classic in-memory database table) are assembled.

Spec Mapping

This lesson addresses AQA A-Level Computer Science (7517), section 4.2.1 (Data structures), specifically arrays of one, two, and three dimensions, records (sometimes called structs), and the composite array of records. It builds directly on the static/dynamic distinction (§4.2.1) and connects to file handling (records written to and read from files) and the relational-database content (§4.3.x), where a record corresponds to a row in a table. Wording below is original and does not reproduce AQA specification text.

---

Arrays

An array is a static data structure that stores a fixed number of elements of the same data type in contiguous memory locations. Each element is accessed using an index (a numerical position).

Key Properties

Property	Description
Fixed size	The size is set when the array is created and cannot change.
Homogeneous	All elements must be of the same data type.
Contiguous memory	Elements are stored next to each other in memory.
Indexed access	Any element can be reached directly using its index in $O(1)$O(1) time.
Zero-based indexing	In most languages, the first element is at index 0.

Why Indexed Access is O(1)

Because every element is the same size and the elements are contiguous, the machine address of element i is found by arithmetic rather than searching. If the array's base address is $B$B and each element occupies $S$S bytes:

$\text{address}(i) = B + i \times S$address(i)=B+i×S

So scores[7] is reached in one step, with no dependence on the array's length. This is the single most important property of an array and the reason it is preferred whenever fast random access is needed.

Pseudocode

DECLARE names : ARRAY[0..4] OF STRING
names[0] = "Alice"
names[1] = "Bob"
names[2] = "Charlie"
// Traverse the array
FOR i = 0 TO 4
    OUTPUT names[i]
NEXT i

Python

# Python lists are dynamic, but are widely used to demonstrate array concepts
names = ["Alice", "Bob", "Charlie", "Diana", "Eve"]

print(names[0])    # Alice  -- direct index access, O(1)
print(names[2])    # Charlie

for name in names:          # traverse by element
    print(name)

for i in range(len(names)): # traverse by index
    print(f"Index {i}: {names[i]}")

---

One-Dimensional Arrays

A one-dimensional (1D) array is a linear list of elements, like a single row.

Index	0	1	2	3	4
Value	10	20	30	40	50

Common Operations and Complexity

Operation	Description	Time complexity
Access	Read/write element at index $i$i	$O(1)$O(1)
Search (linear)	Find an element by value	$O(n)$O(n)
Search (binary)	Find in a sorted array	$O(\log n)$O(logn)
Insert	Add at a specific position (shifting required)	$O(n)$O(n)
Delete	Remove from a specific position (shifting required)	$O(n)$O(n)

Traced Example: Inserting into a 1D Array

Insertion is $O(n)$O(n) because every element after the insertion point must shift right to make room. Insert the value 25 at index 2 of [10, 20, 30, 40, 50] (assuming a spare slot exists):

Step	Action	Array state
0	Start	[10, 20, 30, 40, 50, _]
1	Shift index 4 → 5	[10, 20, 30, 40, _, 50]
2	Shift index 3 → 4	[10, 20, 30, _, 40, 50]
3	Shift index 2 → 3	[10, 20, _, 30, 40, 50]
4	Write 25 at index 2	[10, 20, 25, 30, 40, 50]

Three elements shifted for one insertion: in the worst case (inserting at the front) all $n$n elements shift, hence $O(n)$O(n). Contrast this with a linked list, where the same insertion re-links a single pointer.

Traced Example: Deleting from a 1D Array

Deletion is the mirror image: every element after the gap shifts left to close it. Delete the element at index 1 from [10, 20, 30, 40, 50]:

Step	Action	Array state
0	Start (remove the 20 at index 1)	[10, 20, 30, 40, 50]
1	Shift index 2 → 1	[10, 30, 30, 40, 50]
2	Shift index 3 → 2	[10, 30, 40, 40, 50]
3	Shift index 4 → 3	[10, 30, 40, 50, 50]
4	Mark index 4 as unused (logical length now 4)	[10, 30, 40, 50, _]

Again up to $n$n elements move, so deletion is $O(n)$O(n). The array's slots cannot simply "vanish"; the logical length is reduced and the trailing slot is treated as free. This shifting cost is the central weakness of arrays for collections that change frequently, and the motivation for linked lists.

Traced Example: Linear Search

To find the value 40 in [10, 20, 30, 40, 50], inspect each element left to right until a match:

Index	Value	Match?
0	10	no
1	20	no
2	30	no
3	40	yes → return 3

The worst case (target last or absent) inspects all $n$n elements, so linear search is $O(n)$O(n). If the array were sorted, binary search would instead halve the search space each step, achieving $O(\log n)$O(logn) — but binary search requires the random access that only a contiguous array provides, another reason arrays pair so well with searching.

---

Two-Dimensional Arrays

A two-dimensional (2D) array is an array of arrays — a grid or table with rows and columns.

	Col 0	Col 1	Col 2
Row 0	10	20	30
Row 1	40	50	60
Row 2	70	80	90

Pseudocode

DECLARE grid : ARRAY[0..2, 0..2] OF INTEGER
grid[0][0] = 10
grid[1][2] = 60
// Traverse a 2D array with nested loops
FOR row = 0 TO 2
    FOR col = 0 TO 2
        OUTPUT grid[row][col]
    NEXT col
NEXT row

Python

grid = [
    [10, 20, 30],
    [40, 50, 60],
    [70, 80, 90],
]

print(grid[1][2])  # 60  -- row 1, column 2

for row in range(len(grid)):
    for col in range(len(grid[row])):
        print(f"grid[{row}][{col}] = {grid[row][col]}")

Row-Major Storage

Although a 2D array looks like a grid, memory is one-dimensional. Most languages store the rows one after another — row-major order — so the example grid is laid out in memory as the sequence 10, 20, 30, 40, 50, 60, 70, 80, 90. The address of grid[r][c] in a grid with $C$C columns is:

$\text{address}(r, c) = B + (r \times C + c) \times S$address(r,c)=B+(r×C+c)×S

This is still a single arithmetic step, so 2D access remains $O(1)$O(1). Understanding row-major order also explains why iterating row-by-row is faster than column-by-column on real hardware: consecutive row accesses hit adjacent memory and the cache.

Worked 2D Algorithm: Row Totals

A frequent exam task is to process a 2D array with nested loops — for example, computing the sum of each row of a marks grid. The outer loop selects a row; the inner loop accumulates that row's values.

marks = [
    [10, 20, 30],
    [40, 50, 60],
    [70, 80, 90],
]

for row in range(len(marks)):
    row_total = 0
    for col in range(len(marks[row])):
        row_total += marks[row][col]
    print(f"Row {row} total = {row_total}")

Tracing the first iteration (row = 0): row_total starts at 0, then becomes 10, then 30, then 60; the line prints Row 0 total = 60. Because every one of the $R \times C$R×C cells is visited exactly once, the algorithm is $O(R \times C)$O(R×C) — for a square $n \times n$n×n grid that is $O(n^2)$O(n2). This quadratic behaviour is inherent to processing every cell of a grid and is worth stating explicitly when a question asks for the time complexity of a 2D-array operation.

Searching a 2D Array

Finding a target value in an unsorted grid also requires inspecting every cell in the worst case, again $O(R \times C)$O(R×C):

def find_in_grid(grid, target):
    for r in range(len(grid)):
        for c in range(len(grid[r])):
            if grid[r][c] == target:
                return (r, c)          # row, column of first match
    return None                        # not present

Exam Tip: 2D-array questions are very common. Be fluent with nested loops for traversal, and access a specific element with array[row][col] — rows first, then columns. If a question gives row/column dimensions, you can also be asked to compute a flattened index using $r \times C + c$r×C+c, or to state that a full traversal is $O(R \times C)$O(R×C).

---

Three-Dimensional Arrays

A three-dimensional (3D) array extends the idea again: think of it as a stack of 2D grids, indexed by array[layer][row][col]. A common use is a small RGB image cube ([height][width][3], where the third index selects the red, green, or blue channel) or a 3D game world divided into voxels.

# A 2 x 2 x 2 cube of zeros (layers x rows x cols)
cube = [[[0 for _ in range(2)] for _ in range(2)] for _ in range(2)]
cube[1][0][1] = 99      # layer 1, row 0, column 1
print(cube[1][0][1])    # 99

The address formula generalises: with $R$R rows and $C$C columns per layer, cube[l][r][c] sits at $B + (l \times R \times C + r \times C + c) \times S$B+(l×R×C+r×C+c)×S, so access is still $O(1)$O(1).

---

Records

A record groups together related data items of different data types under a single name. Each item within a record is called a field. Where an array is homogeneous (all same type, accessed by number), a record is heterogeneous (mixed types, accessed by name).

Key Properties

Property	Description
Heterogeneous	Fields can be of different data types.
Named fields	Each field has a name, not a numeric index.
Fixed structure	The number and types of fields are defined at design time.
Used for	Representing entities with multiple attributes (a student, a product, a transaction).

Pseudocode

TYPE Student
    firstName : STRING
    lastName  : STRING
    age       : INTEGER
    grade     : CHAR
ENDTYPE

DECLARE pupil : Student
pupil.firstName = "Alice"
pupil.lastName  = "Smith"
pupil.age       = 17
pupil.grade     = 'A'

OUTPUT pupil.firstName & " " & pupil.lastName

Python

# A class is the natural way to model a record in Python
class Student:
    def __init__(self, first_name: str, last_name: str, age: int, grade: str):
        self.first_name = first_name
        self.last_name = last_name
        self.age = age
        self.grade = grade

pupil = Student("Alice", "Smith", 17, "A")
print(f"{pupil.first_name} {pupil.last_name}")

# Alternative: a dictionary also behaves like a record
pupil_dict = {
    "first_name": "Alice",
    "last_name": "Smith",
    "age": 17,
    "grade": "A",
}

A record's fields are accessed by name (pupil.age), which is more readable and less error-prone than a numeric index, and the compiler/interpreter knows the type of each field.

Parallel Arrays: The Alternative to Records

Before records (or in languages without them), related attributes were sometimes stored in parallel arrays — one array per field, with the same index representing one entity across all arrays.

first_names = ["Alice", "Bob", "Charlie"]
ages        = [17,      18,    17]
grades      = ["A",     "B",   "A"]

# Student at index 1 is Bob, 18, grade B -- spread across three arrays
print(first_names[1], ages[1], grades[1])

Parallel arrays work, but they are fragile: the arrays must be kept exactly in step (inserting a student means updating all three), and there is nothing tying ages[1] to first_names[1] except the convention that index 1 means "Bob". A record bundles the fields together so they cannot drift apart, and an array of records makes the relationship explicit. For this reason an array of records is almost always preferable to parallel arrays for representing a list of multi-attribute entities — a useful comparison to draw in an evaluation question.

---

Arrays of Records

In practice you usually need a collection of records — a list of students, a table of products. This is an array of records, and it is the in-memory equivalent of a database table: each array element is a row, each field a column.

Pseudocode

DECLARE students : ARRAY[0..29] OF Student

students[0].firstName = "Alice"
students[0].lastName  = "Smith"
students[0].age       = 17
students[0].grade     = 'A'

// Display all students
FOR i = 0 TO 29
    OUTPUT students[i].firstName & " - " & students[i].grade
NEXT i

Python

students = [
    Student("Alice", "Smith", 17, "A"),
    Student("Bob", "Jones", 18, "B"),
    Student("Charlie", "Brown", 17, "A"),
]

for student in students:
    print(f"{student.first_name} - Grade {student.grade}")

Traced Example: Linear Search over an Array of Records

To find the student with grade B, iterate and inspect a field of each record:

Index	Record inspected	grade == "B"?	Action
0	Alice / A	No	continue
1	Bob / B	Yes	return index 1