A-Level Revision Aid: This resource is designed to support your revision. Content may contain errors. If you find a discrepancy with your class teaching, your teacher is correct — please let us know at alevelrevise@scott.scottrix.co.uk.
Data Structures and Algorithms
Year 1 / ASYear 2 / A-LevelAQA, OCR, WJEC/Eduqas
Exam-focused AQA 7517, OCR H446 and WJEC/Eduqas revision for data structures and algorithms: arrays, stacks, queues, trees, graphs, hash tables, searching, sorting, Dijkstra and A* with worked traces and Big-O analysis.
🎯 Learning Objectives
Describe the structure and uses of arrays, lists, linked lists, stacks, queues, trees, graphs and hash tables, and state the trade-offs between them (OCR 1.4.2, AQA 4.1 ADTs, WJEC 3.1)
Trace linear and binary search step by step, and state why binary search requires sorted data (OCR 2.3)
Trace bubble, insertion and merge sort with comparison counts, and justify O(n^2) versus O(n log n) behaviour
Trace Dijkstra's shortest-path and A* algorithms on a weighted graph (OCR 2.3)
Compute and rank time complexities in Big-O notation: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n)
Explain hashing, collision resolution (chaining, open addressing) and load factor
Choose an appropriate data structure for a problem and justify the choice by access pattern and complexity
📋 Key Definitions and Core Concepts
Array: A fixed-size, ordered collection of elements of the same type stored contiguously, accessed by index in O(1).
Stack: A LIFO (last-in, first-out) ADT supporting push and pop at one end only.
Queue: A FIFO (first-in, first-out) ADT supporting enqueue at the rear and dequeue at the front.
Binary search tree: A binary tree where every node's left subtree contains smaller values and right subtree larger values, giving O(log n) average search.
Hash table: A structure mapping keys to values via a hash function; average O(1) lookup, with collisions resolved by chaining or open addressing.
Adjacency matrix / list: Two graph representations: a V x V matrix of edge weights (O(1) edge lookup, O(V^2) space) or a list per vertex of its neighbours (O(V+E) space).
Big-O notation: An upper-bound description of how an algorithm's running time (or space) grows with input size, ignoring constant factors.
Collision: When two keys hash to the same index; resolved by chaining (linked lists per slot) or open addressing (probing for the next free slot).
Load factor: The ratio of stored items to table slots; as it approaches 1, collisions and probe lengths grow, so tables are resized (typically when load factor > 0.7).
📌 Key Points
Arrays: contiguous, O(1) index access, fixed size; linked lists: O(1) insert/delete at a known node, O(n) access
Dijkstra: shortest path, non-negative weights, greedy on tentative distances; A* adds heuristic h(n) to focus the search
Core data structures and when to use them
The 6-marker in this section is nearly always 'compare two data structures for this problem' (OCR 1.4.2, WJEC 3.1). The full-credit pattern: state the access pattern each structure optimises, state a complexity for each, then link to the problem.
Structure
Access
Key operations
Typical use
Array
O(1) by index
fixed size, contiguous
lookup tables, matrices
Linked list
O(n) sequential
O(1) insert/delete at node
dynamic ordering, chaining
Stack
LIFO
push, pop, peek O(1)
call stack, undo, RPN evaluation
Queue
FIFO
enqueue, dequeue O(1)
BFS, spooling, scheduling
BST
O(log n) avg
insert/find/delete
sorted data, ordered traversal
Hash table
O(1) avg
hash insert/find
dictionaries, caches, symbol tables
Implementation details that earn marks: a stack can be implemented over an array (top pointer, overflow when top = maxSize) or a list; a circular queue uses (rear + 1) MOD maxSize to reuse freed slots — know why a naive linear queue wastes space as the front pointer advances. A priority queue dequeues the highest-priority item rather than the oldest, and is the structure behind Dijkstra's algorithm. A hash table's average O(1) hides its worst case O(n) — when all keys collide into one slot — and exams love asking for both cases.
Tree knowledge for A*: an unbalanced BST degrades to O(n) (a linked list in disguise) if data arrives already sorted; balanced trees (AVL, red-black) keep height at O(log n) by rotating on insert. Graph representation trade-off in one line: adjacency matrix gives O(1) edge lookups but always O(V^2) space, so it suits dense graphs; an adjacency list uses O(V + E) space and suits sparse graphs — for sparse graphs the matrix is mostly empty cells.
Searching: linear, binary and hash-based
Linear search checks each element in turn; O(n) worst case; works on unsorted data. Binary search (OCR 2.3, AQA 4.1) repeatedly halves a sorted range: compare the middle element, discard the wrong half, repeat. O(log n): a million items need at most about 20 comparisons because 2^20 > 10^6 — quote that figure, it earns the explanation mark.
function binarySearch(list, target)
low = 0
high = len(list) - 1
while low <= high
mid = (low + high) DIV 2
if list[mid] == target then return mid
if list[mid] < target then low = mid + 1
else high = mid - 1
endwhile
return -1 // not found
endfunction
Full trace — target 18 in [2, 5, 8, 12, 16, 18, 24, 30], indices 0–7:
Pass
low
high
mid
list[mid]
Decision
1
0
7
3
12
18 > 12, search right half
2
4
7
5
18
found at index 5
Two comparisons. Common trace errors: computing mid as (low + high) / 2 with real division, or halving one time too many when the item is absent — the loop terminates when low > high and the exam answer is 'return -1 / not found'. The why sorted question: binary search relies on knowing which half the target must be in; with unsorted data the comparison discards the wrong half, so only linear search is valid.
Hash-based search: compute index = hash(key) MOD tableSize and read that slot — O(1) average. If the slot holds another key (a collision), resolve: chaining stores a linked list per slot (search continues down the list), or open addressing probes the next slot ((index + 1) MOD size, linear probing) until the key or an empty slot is found. A worked hash: keys 27, 43, 12 into a table of size 10 with hash = key MOD 10 — 27 lands at 7, 43 collides with nothing at 3, 12 at 2. Add 57: 57 MOD 10 = 7 collides with 27; with linear probing it goes to slot 8. Searching later for 57 must retrace the same probe sequence, which is why the hash and probe rule must be deterministic. Load factor = items/slots; at 0.9 the expected probe length grows sharply, so tables rehash to a larger size — say this when asked why performance degrades.
Sorting: bubble, insertion, merge, quick
Know each algorithm's method (trace marks), its complexity (analysis marks), and one property (evaluation marks).
Bubble sort: repeatedly swap adjacent out-of-order pairs; after pass k the largest k items are in place. O(n^2) worst and average; O(n) best case on already-sorted data with an early-exit flag. Simple but slow; stable.
Insertion sort: grow a sorted prefix, inserting each new element into place by shifting. O(n^2) worst/average, O(n) on nearly-sorted data; the usual choice for small n; stable.
Merge sort: divide-and-conquer — split to singletons, merge sorted halves. O(n log n) always; needs O(n) extra space; stable.
Quicksort: pick a pivot, partition into less-than and greater-than, recurse. O(n log n) average, O(n^2) worst (already-sorted data with first-element pivot); in-place, O(log n) stack; not stable.
Complexity justification to reproduce: log2(4) = 2 split levels, and each level merges n items in O(n) comparisons, so total O(n log n). For n = 1024: log2(1024) = 10 levels x 1024 comparisons ≈ 10,240 operations, versus bubble sort's worst case n(n-1)/2 ≈ 523,776 comparisons — the comparison the examiner wants when asking 'why is merge sort preferred for large data sets'.
Bubble-sort pass trace on [5, 3, 8, 2]: pass 1 — compare 5,3 swap → [3,5,8,2]; compare 5,8 ok; compare 8,2 swap → [3,5,2,8]. Pass 2 — 3,5 ok; 5,2 swap → [3,2,5,8]. Pass 3 — 3,2 swap → [2,3,5,8]; no swaps, sorted. Count: 9 comparisons in total; note the largest element 'bubbles' to the end after pass 1.
Quicksort trace with first-element pivot on [3, 6, 8, 10, 1, 2, 1]: pivot 3 partitions into [1, 2, 1] + [3] + [6, 8, 10]; left: pivot 1 → [1] + [1] + [2]; right: pivot 6 → [] + [6] + [8, 10], then pivot 8 → [] + [8] + [10]. Result [1, 1, 2, 3, 6, 8, 10]. Worst case arises because a sorted input with first-element pivot makes every partition one-sided: n levels instead of log n, giving O(n^2) — the standard fix is a random or middle pivot.
Graph algorithms: traversal, Dijkstra and A*
Traversals: DFS uses a stack (or recursion) and dives deep before backtracking; BFS uses a queue and visits by distance layer. On an unweighted graph, BFS finds the shortest path in edges — the exam one-liner: BFS with a queue explores nodes in increasing distance from the start, so the first time the target is dequeued the path is shortest. Tree traversals are the recursive cousins: pre-order (node, left, right — copying a tree), in-order (left, node, right — outputs a BST in sorted order), post-order (left, right, node — deleting/freeing a tree), level-order (BFS with a queue).
Dijkstra's algorithm (OCR 2.3) finds shortest paths from a source on a weighted graph with non-negative edge weights. Method: keep a tentative distance per node (start = 0, others = infinity); repeatedly visit the unvisited node with the smallest tentative distance, then relax each of its edges: if distance[u] + weight(u,v) < distance[v], update distance[v] and record u as v's predecessor.
Graph: A-B 4, A-C 2, C-B 1, B-D 5, C-D 8
Start A.
Trace: visit A(0) — relax B to 4 (via A), C to 2 (via A). Visit C(2), smallest tentative — relax B: 2+1=3 < 4 so B becomes 3 via C; relax D: 2+8=10. Visit B(3) — relax D: 3+5=8 < 10 so D becomes 8 via B. Visit D(8). Shortest A to D = 8, path A-C-B-D. The marking points: always expand the smallest tentative node next (greedy), relaxations update predecessors, and negative weights break the algorithm because a settled node could later be improved — hence alternatives such as Bellman-Ford exist.
A* is Dijkstra plus a heuristic: instead of the smallest distance-so-far g(n), expand the node with the smallest f(n) = g(n) + h(n), where h(n) estimates the remaining cost to the goal. With an admissible heuristic (never overestimates — e.g. straight-line distance on a map), A* is guaranteed to find the optimal path but expands far fewer nodes than Dijkstra because it biases the search towards the goal. Trace contrast: on the graph above with target D and heuristic h(B)=5, h(C)=6, h(A)=8: after visiting A, f-values are B: 3+5=8, C: 2+6=8 — tie; choosing B first reaches D immediately with f = 8+0. The evaluation point to make: A* trades guaranteed optimality only when h is inadmissible; a poor heuristic degenerates A* towards Dijkstra's behaviour, and h = 0 makes it exactly Dijkstra.
Big-O complexity: computing and justifying
Big-O ranks growth rates, ignoring constants: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n). Justify each with its loop shape:
O(1): a fixed number of operations — array index, hash lookup on average.
O(log n): the search space halves each step — binary search, balanced BST lookup.
O(n): one pass over the data — linear search, tree in-order traversal.
O(n log n): log n passes each doing O(n) work — merge sort, quicksort average.
O(n^2): nested loops over the data — bubble, insertion, selection sort; adjacency-matrix operations.
O(2^n): every subset considered — brute-force subset problems, naive travelling salesman.
Worked computations to memorise:
n = 1000: O(n) ≈ 1,000 steps; O(n log n) ≈ 10,000 (log2 1000 ≈ 10); O(n^2) = 1,000,000; O(2^n) is astronomically larger than any of these. This table is the whole answer to 'why does complexity matter'.
Nested loop counting: a loop to n containing a loop to n does n x n = n^2 comparisons; a loop to n containing a loop to n DIV 2 still counts as O(n^2) because constants are dropped.
Best vs worst: bubble sort best case O(n) (already sorted, early exit), worst O(n^2); quicksort average O(n log n), worst O(n^2); linear search finds the item first time (O(1) best) or last (O(n) worst).
Exam question pattern: 'An algorithm performs n(n-1)/2 comparisons. State its time complexity and justify your answer.' Answer: O(n^2); n(n-1)/2 = (n^2 - n)/2, and Big-O ignores both the constant 1/2 and the lower-order term -n, leaving n^2 as the dominant term. Second pattern: 'Explain why O(2^n) algorithms are impractical.' Each extra input item doubles the running time, so growth outpaces any hardware improvement — adding one item doubles work, while doubling processor speed only halves it; complexity wins over hardware. Finally, be ready to state space complexity: merge sort needs O(n) auxiliary space, quicksort O(log n) stack, binary search O(1) iterative (O(log n) recursive stack), adjacency matrix O(V^2).
💡 Worked Example
Exam-style: The list [2, 5, 8, 12, 16, 18, 24, 30] is searched using binary search for the value 24.
(a) Show the values of low, high and mid for each pass, and state how many comparisons are made. [4 marks]
(b) Explain why binary search cannot be used if the list is unsorted. [2 marks]
(c) State the time complexity of binary search and justify it. [2 marks]
Mark-scheme logic: (a) low=0, high=7: mid=(0+7) DIV 2=3, list[3]=12, 24 > 12 so search right half (1). low=4, high=7: mid=(4+7) DIV 2=5, list[5]=18, 24 > 18 so search right half (1). low=6, high=7: mid=6, list[6]=24 — found at index 6 after 3 comparisons (1, and 1 for correct count).
(b) Binary search works by comparing the middle element and discarding the half that cannot contain the target (1). With unsorted data there is no ordering to reason from, so the discarded half may actually contain the target and the search is invalid (1).
(c) O(log n) (1): each comparison halves the search space, so the number of comparisons grows logarithmically — for n = 2^k at most k+1 comparisons are needed (1).
❓ Practice Questions & Mark Schemes
Compare an adjacency matrix with an adjacency list for representing a graph with 1,000 vertices and 900 edges. [4 marks]
Answer: The graph is sparse (900 edges on 1,000 vertices) (1). An adjacency matrix needs O(V^2) = 1,000,000 cells, almost all empty, and an edge test is O(1) (1). An adjacency list needs O(V + E) ≈ 1,900 entries — far less memory for a sparse graph (1). Recommendation: adjacency list, because memory savings dominate; the matrix's O(1) edge test does not compensate for storing ~999,100 empty cells (1).
Trace Dijkstra's algorithm from node A on: A-B 6, A-C 3, C-B 2, C-D 7, B-D 4. Give the shortest distance from A to D and the path. [6 marks]
Answer: Visit A(0): tentative B = 6 via A, C = 3 via A, D = infinity (2 marks: correct initial relaxation). Visit C(3): relax B — 3+2=5 < 6 so B = 5 via C; relax D — 3+7=10 (2 marks). Visit B(5): relax D — 5+4=9 < 10 so D = 9 via B (1 mark). Visit D(9). Shortest distance A to D = 9 (1) with path A-C-B-D (1).
State the worst-case time complexity of bubble sort and of merge sort, and explain why merge sort scales better for large lists. [4 marks]
Answer: Bubble sort worst case O(n^2) (1); merge sort O(n log n) in all cases (1). Justification: bubble sort compares adjacent pairs in nested passes — roughly n^2/2 comparisons — so doubling n quadruples the work (1); merge sort performs log2(n) split levels, each merging O(n) items, so doubling n adds only one extra O(n) level — work grows n log n (1).
A hash table has 8 slots and uses hash = key MOD 8 with linear probing. Show where keys 21, 29, 37, 8 are stored, and state the load factor. [5 marks]
Answer: 21 MOD 8 = 5 → slot 5 (1). 29 MOD 8 = 5 → collision; probe 6 → slot 6 (1). 37 MOD 8 = 5 → collision; probe 6 (occupied), probe 7 → slot 7 (1). 8 MOD 8 = 0 → slot 0 (1). Load factor = 4/8 = 0.5 (1). Probing must be deterministic so that searching later retraces the same sequence; as load factor rises towards 1, probe lengths grow and lookup degrades towards O(n).
Explain the difference between pre-order, in-order and post-order traversal of a binary search tree, and state which traversal outputs the data in sorted order. [4 marks]
Answer: Pre-order visits the node before its subtrees (node, left, right) (1); in-order visits the left subtree, then the node, then the right subtree (1); post-order visits both subtrees before the node (left, right, node) (1). In-order traversal of a BST outputs the values in ascending sorted order, because every node is visited after all smaller values and before all larger ones (1).
An algorithm takes 0.002 seconds for n = 1,000 and is O(n^2). Estimate its running time for n = 10,000, showing your reasoning. [3 marks]
Answer: Time scales with n^2 (1). n grows by a factor of 10, so time grows by 10^2 = 100 (1). Estimated time = 0.002 x 100 = 0.2 seconds (1). Contrast worth stating: an O(n log n) algorithm would grow by only 10 x log2(10) ≈ 33x to roughly 0.066 s.
amazon.co.uk
