Comparing Data Structures

AQA 4.2.7–4.2.9 — Comparing and selecting data structures

Retrieval: this lesson draws on every structure covered this sequence — graphs, trees, binary search trees, hash tables — and, essentially, on Year 12 Sequence 5's algorithm performance work: none of the comparisons below mean anything without already understanding what O(1), O(log n) and O(n) actually represent.

Understand — there is no single "best" structure

Every choice made across this sequence has been a genuine trade-off between the operations a scenario actually needs, how the data changes over time, and memory constraints. This lesson makes that trade-off systematic.

See it — a direct comparison

Understand — applying Year 12's algorithm performance to real numbers

Searching 1,000,000 items: linear search takes up to 1,000,000 comparisons in the worst case; binary search or a balanced BST takes around log₂(1,000,000) ≈ 20; a hash table takes around 1. The gap between O(n) and O(log n) genuinely matters at scale — this is exactly the algorithm-performance reasoning from Year 12, now applied to structures that didn't exist in that course.

Select, justify — three unfamiliar scenarios

1. A phonebook app needs to look up a contact by name instantly, and also display all contacts in alphabetical order in a list view.
2. A web browser's "visited URLs" cache, checked before every page load purely to answer "have I seen this URL before?", with millions of entries, never needing to be listed in any particular order.
3. A delivery company's route-planning system, modelling which depots have a direct road connection to which other depots, including the distance of each road.

(1: A BST. A hash table alone gives fast lookup but no order; a BST gives both O(log n) lookup AND sorted output for free via in-order traversal, satisfying both requirements with one structure. 2: A hash table. Pure existence-checking at maximum speed is the only requirement - order is never needed, so a hash table's O(1) average lookup is the clear winner. 3: A weighted graph (adjacency list, since real road networks are sparse - most depot pairs have no direct road). None of the other structures model many-to-many relational connections at all.)

Debug it — diagnose, explain, fix, test, justify (algorithm/data-structure mismatch)

prices = {"banana": 0.5, "apple": 1.2, "cherry": 3.0, "date": 2.5}
keys = list(prices.keys())

def binary_search(sorted_list, target):
    low, high = 0, len(sorted_list) - 1
    while low <= high:
        mid = (low + high) // 2
        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

print(binary_search(keys, "cherry"))

This can return -1 (not found) for a key that genuinely is present, or find the wrong index — with no crash at all.

1. Diagnose: is keys actually guaranteed to be in alphabetically sorted order?
2. Explain: what does a Python dict actually guarantee about the order of .keys(), and is that the same as being sorted?
3. Fix: propose a correct fix.
4. Test: confirm the fixed version finds "cherry" correctly.
5. Justify: explain why this is a fundamentally different kind of bug from the exception-based and link-based bugs seen earlier this sequence.

(A dict preserves INSERTION order in modern Python, not alphabetical order - the mismatch is applying a sorted-data-only algorithm (binary search) to data that was never actually sorted. A correct fix either sorts keys first (sorted(prices.keys())) before searching, or - more importantly - recognises that a dict already provides O(1) direct lookup ("cherry" in prices), making binary search unnecessary here entirely. This differs from earlier bugs because the code runs to completion and may even happen to give a right answer by luck on some inputs - its correctness was never actually guaranteed, unlike a crash, which at least announces itself immediately.)

Common mistake

Treating "which structure is fastest" as a single, context-free question. As the comparison table and the three scenarios above show, the right answer always depends on which operations the scenario actually needs, not on any one structure's raw speed in isolation.

Check your understanding

A school's library system needs to (1) instantly check whether a given ISBN exists in the collection, and (2) periodically print a full list of all ISBNs in numerical order for a stock report. Evaluate whether a hash table alone would be a sufficient choice for this system. (4 marks)

(Not sufficient alone. A hash table satisfies requirement (1) very well (O(1) average existence check), but hash tables provide no meaningful order over their keys, so requirement (2) cannot be achieved directly - the system would need to separately sort the ISBNs before every report (an extra O(n log n) step each time), or use a BST instead, which supports both requirements natively via O(log n) lookup and free in-order traversal. Evaluating both options, a BST is likely the more elegant single-structure solution unless raw lookup speed is significantly more critical than the reporting requirement.)

Challenge

An online multiplayer game needs to track which of thousands of players are currently "online" — a simple yes/no membership question, checked extremely frequently, with players constantly joining and leaving. Select and justify an appropriate data structure from this sequence.

Looking ahead: Sequence 13 (Advanced Algorithms) finally traverses these graphs and trees properly — Breadth-First Search, Depth-First Search, and Dijkstra's algorithm — building directly on the structures just covered.