C6 · Data Structures

Spec reference: Section C - Programming Paradigms
Key idea: Use arrays, lists, records and other structures to organise and store collections of data.

---

Difficult topic

This is a challenging topic, read through the notes and practise the examples to fully understand it.

▶ Data Structures: Arrays and Records explained

---

Arrays and lists

An array (called a list in Python) is an ordered collection of elements, all accessible by an index.

scores = [45, 82, 63, 71, 90]

# Accessing elements (zero-indexed)
print(scores[0])   # 45  -  first element
print(scores[4])   # 90  -  last element
print(scores[-1])  # 90  -  also last element (Python shortcut)

# Modifying
scores[2] = 68     # changes 63 → 68

# Length
print(len(scores)) # 5

Iterating over an array

# Print all scores
for score in scores:
    print(score)

# Print with index
for i in range(len(scores)):
    print(f"Student {i+1}: {scores[i]}")

2D arrays (tables)

A 2D array stores data in rows and columns:

# 3 students, 3 subjects each
marks = [
    [72, 65, 80],   # Student 0
    [88, 91, 76],   # Student 1
    [55, 60, 70],   # Student 2
]

print(marks[1][2])  # 76  -  Student 1, Subject 2 (index 2)

# Print all marks
for student in marks:
    for mark in student:
        print(mark, end=" ")
    print()

---

Records (dictionaries)

A record stores named fields for a single entity - like a row in a database.

In Python, this is a dictionary:

student = {
    "name": "Alice",
    "age": 17,
    "grade": "A"
}

print(student["name"])   # Alice
student["age"] = 18      # update a field
student["school"] = "Greenfield"  # add new field

List of records

students = [
    {"name": "Alice", "score": 85},
    {"name": "Bob",   "score": 72},
    {"name": "Carol", "score": 90},
]

for s in students:
    print(s["name"], "-", s["score"])

---

Stacks - Last In, First Out (LIFO)

A stack only allows access to the top element. Think of a stack of plates.

Operation	Description
PUSH	Add an item to the top
POP	Remove and return the top item
PEEK	Look at the top item without removing
isEmpty	Check if stack is empty

stack = []
stack.append("a")   # PUSH
stack.append("b")
stack.append("c")

top = stack.pop()   # POP → "c"
print(top)          # c
print(stack)        # ["a", "b"]

LIFO - the last item pushed is the first to be popped.

Real-world uses: undo/redo in text editors, browser back button, call stack in programming.

---

Queues - First In, First Out (FIFO)

A queue adds to the back and removes from the front. Think of a queue at a shop.

Operation	Description
ENQUEUE	Add to the back
DEQUEUE	Remove from the front

from collections import deque

queue = deque()
queue.append("Alice")    # ENQUEUE
queue.append("Bob")
queue.append("Carol")

first = queue.popleft()  # DEQUEUE → "Alice"
print(first)             # Alice
print(list(queue))       # ["Bob", "Carol"]

FIFO - the first item enqueued is the first to be dequeued.

Real-world uses: print queues, task scheduling, network packet buffering.

---

Stack vs Queue comparison

	Stack	Queue
Order	LIFO (Last In, First Out)	FIFO (First In, First Out)
Add to	Top	Back/rear
Remove from	Top	Front
Add operation	PUSH	ENQUEUE
Remove operation	POP	DEQUEUE
Example	Undo history	Print queue

---

Choosing a data structure

Need	Use
Ordered list of items, accessed by position	Array / List
Named fields for a single entity	Record / Dictionary
Multiple entities with same fields	List of records
Process in reverse order (LIFO)	Stack
Process in arrival order (FIFO)	Queue

---

Test Yourself

Question 1 of 5

A list in Python is: scores = [10, 20, 30, 40, 50]. What does scores[3] return?