You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
This lesson covers arrays and records (structs) — two of the most fundamental data structures in computing. Understanding how data is organised in memory at this level is essential for the OCR A-Level Computer Science (H446) specification, section 1.4.
An array is a data structure that stores a fixed-size, ordered collection of elements, all of the same data type, in contiguous memory locations.
Each element is accessed using an index (position number). In most languages, indexing starts at 0.
| Property | Description |
|---|---|
| Homogeneous | All elements must be the same data type (e.g., all integers, all strings). |
| Fixed size | The size is set when the array is created and cannot change. |
| Contiguous | Elements are stored next to each other in memory. |
| Indexed | Each element has a unique index for direct access. |
| Static | Arrays are a static data structure — size determined at compile time. |
A 1D array is a simple list of elements arranged in a single row.
array scores[10] // declares an array of 10 elements, indices 0 to 9
scores[0] = 85
scores[1] = 92
scores[2] = 78
# Python lists serve as arrays (though technically dynamic)
scores = [85, 92, 78, 64, 91, 88, 73, 95, 67, 82]
# Access by index
print(scores[0]) # Output: 85
print(scores[9]) # Output: 82
# Modify an element
scores[3] = 70
Arrays occupy a contiguous block of memory. If the base address is B and each element occupies S bytes, the address of element at index i is:
Address = B + (i x S)
This formula is why array access is O(1) — the address of any element can be calculated directly.
An integer array starts at memory address 2000. Each integer occupies 4 bytes.
| Index | Address Calculation | Memory Address |
|---|---|---|
| 0 | 2000 + (0 x 4) | 2000 |
| 1 | 2000 + (1 x 4) | 2004 |
| 2 | 2000 + (2 x 4) | 2008 |
| 3 | 2000 + (3 x 4) | 2012 |
| 4 | 2000 + (4 x 4) | 2016 |
Exam Tip: You must be able to calculate the memory address of any element in an array given the base address, index, and element size. This is a common 2-3 mark question.
A 2D array is an array of arrays — it stores data in rows and columns, forming a grid or table structure.
array grid[3,4] // 3 rows, 4 columns
grid[0,0] = 1
grid[1,2] = 5
grid[2,3] = 9
# 2D array as a list of lists
grid = [
[1, 2, 3, 4], # Row 0
[5, 6, 7, 8], # Row 1
[9, 10, 11, 12] # Row 2
]
# Access: grid[row][column]
print(grid[1][2]) # Output: 7 (row 1, column 2)
print(grid[0][3]) # Output: 4 (row 0, column 3)
To visit every element, use nested loops — one for rows, one for columns.
for row in range(3):
for col in range(4):
print(grid[row][col], end=" ")
print() # new line after each row
2D arrays are stored in memory as a single contiguous block. In row-major order (the most common approach), all elements of row 0 come first, then row 1, and so on.
Address of element [r][c] in a 2D array with C columns:
Address = B + ((r x C) + c) x S
A 2D array has 5 columns, starts at address 1000, and each element is 4 bytes.
Address of element [2][3]:
A record (or struct) is a data structure that groups together related data items of different types under named fields.
Unlike arrays (which store elements of the same type), records can store a mix of data types — for example, a student record might contain a string (name), an integer (age), and a float (grade).
| Property | Description |
|---|---|
| Heterogeneous | Fields can be different data types. |
| Named fields | Each piece of data is accessed by its field name, not an index. |
| Grouped | Related data is kept together as a single unit. |
| Fixed structure | The fields are defined at design time. |
record Student
name: string
age: integer
grade: real
end record
// Create an instance
student1 = new Student()
student1.name = "Alice"
student1.age = 17
student1.grade = 8.5
# Using a class to represent a record
class Student:
def __init__(self, name, age, grade):
self.name = name
self.age = age
self.grade = grade
# Create instances
student1 = Student("Alice", 17, 8.5)
student2 = Student("Bob", 18, 7.2)
# Access fields using dot notation
print(student1.name) # Output: Alice
print(student2.grade) # Output: 7.2
A very common pattern is to store an array of records — for example, an array of student records.
students = [
Student("Alice", 17, 8.5),
Student("Bob", 18, 7.2),
Student("Charlie", 17, 9.1),
]
# Access the name of the second student
print(students[1].name) # Output: Bob
# Find all students aged 17
for s in students:
if s.age == 17:
print(s.name)
Exam Tip: Questions often ask you to design a record structure for a scenario (e.g., a library book, a patient record). Define each field with its name and data type. Then show how you would create an array of these records and access individual fields.
Arrays and records are static data structures:
| Feature | Static (Arrays, Records) | Dynamic (Linked Lists, Trees) |
|---|---|---|
| Size | Fixed at creation | Can grow/shrink at runtime |
| Memory | Allocated at compile time | Allocated at runtime (heap) |
| Access | O(1) direct/random access | O(n) sequential traversal |
| Waste | May waste memory if not full | Uses only what is needed |
| Overhead | No pointer overhead | Pointer overhead per element |
| Scenario | Best Choice | Reason |
|---|---|---|
| Known, fixed number of elements | Array | No wasted memory, fast access |
| Need to store different data types together | Record | Groups heterogeneous data |
| Frequent insertions/deletions | Linked list (dynamic) | No shifting required |
| Size changes unpredictably | Dynamic structure | Grows/shrinks as needed |
| Fast lookup by position | Array | O(1) indexed access |
| Feature | Array | Record |
|---|---|---|
| Element types | All the same (homogeneous) | Can differ (heterogeneous) |
| Access method | By index (e.g., arr[3]) | By field name (e.g., rec.name) |
| Purpose | Store a list of similar items | Group related but different data |
| Example | List of exam scores | A single student's details |
| Operation | Description | Time Complexity |
|---|---|---|
| Access | Read/write element at index i | O(1) |
| Linear search | Find an element by scanning | O(n) |
| Binary search | Find in a sorted array | O(log n) |
| Insert at end | Place element at next free position | O(1) |
| Insert at position | Shift elements right, then insert | O(n) |
| Delete at position | Remove element, shift elements left | O(n) |
| Traverse | Visit every element | O(n) |
Exam Tip: Be ready to calculate memory addresses for 1D and 2D arrays, design record structures for real-world scenarios, and explain the trade-offs between static and dynamic data structures. These are high-frequency exam topics in the OCR H446 paper.