A-Level · Data Structures

Linked Lists, Trees, Graphs & Hash Tables

The stacks and queues from GCSE were built on arrays. These four structures solve different problems: growing without knowing the size in advance, representing hierarchy, representing arbitrary connections, and looking things up in constant time. Every one below is a real, working implementation you can operate on directly.

Section 2

Linked lists: growing one node at a time

An array needs its size fixed in advance (or expensively resized). A linked list just adds a new node and points to it, nothing else moves.

Empty list. Try inserting a value.

Insert

Delete

Exam tips

  • Inserting at the head is O(1): just point the new node at the old head. Inserting at the tail needs to walk the whole list first, O(n), unless you keep a separate tail pointer.
  • Deleting requires finding the node before the one you want to remove, since you need to redirect its pointer.
Section 3

Binary search trees: insert, delete, traverse

A BST keeps everything smaller to the left, everything bigger to the right, at every single node. That one rule is what makes searching fast and in-order traversal produce sorted output.

Tree built from inserting 50, 30, 70, 20, 40, 60, 80, 35, 45 in that order.

Insert / Delete

Traverse

Tree stats, updated live

Exam tips

  • Deleting a leaf: just remove it. Deleting a node with one child: replace it with that child. Deleting a node with two children is the tricky case, replace its value with its in-order successor (the smallest value in its right subtree), then delete that successor from where it originally was.
  • In-order traversal of a BST always visits nodes in sorted order, this is a direct, provable consequence of the BST property, not a coincidence.
  • Pre-order visits the node before its children (root, left, right), useful for copying a tree's structure. Post-order visits it after (left, right, root), useful for safely deleting a tree bottom-up.
Section 4

Graphs: representing arbitrary connections

A tree only ever branches downward from a root. A graph drops that restriction entirely, any node can connect to any other, including back to itself or in a cycle. Two standard ways to store one.

Directed or undirected?

Adjacency matrix

Adjacency list

The list is far more compact whenever most nodes aren't connected to each other, the matrix wastes space on every non-connection, but offers instant O(1) lookup for "are these two connected?"

Section 5

Hash tables: same collisions, two different fixes

These 7 keys were chosen deliberately: 5 of them hash to the exact same slot. Watch chaining and linear probing handle that identical collision completely differently.

Chaining

Collision resolution method

Key type

Table size (prime)

Controls

Exam tips

  • Chaining: each slot holds a small list. Collisions just extend that list, nothing ever moves to a different slot.
  • Linear probing: on collision, try the next slot, then the next, until an empty one is found. Notice how key 5, which naturally hashes to slot 5, still ends up displaced once slot 5 gets filled by an earlier collision cascading into it.
  • A good hash function distributes keys evenly, the default view here (integer keys, table size 7) deliberately uses a bad distribution (5 of 7 keys collide) specifically to make the difference between the two methods visible. Try a larger prime table size and watch the collisions mostly disappear, that's not a coincidence either.
Section 6

Check your understanding