This mini-lesson covers AQA 4.2 — Fundamentals of data structures. Choosing the right structure is what separates a program that runs in milliseconds from one that runs for a week.
Work through each screen, answer the questions as you go (some are recall, some are calculations you must actually work out) and collect ⭐ stars. Press Start when you're ready.
An array is a fixed-size, ordered set of elements all of the same type, accessed by index. Because every element is the same size, the address of element i is found by arithmetic — so access is O(1), instantly, at any index.
A record groups fields of different types under one name (a row in a file or database table). A file is a collection of records held in secondary storage.
An abstract data type (ADT) is defined by its operations, not its implementation. A stack is an ADT: it promises push, pop and peek. Whether it is built on an array or a linked list is an implementation detail the user never needs to know — that is abstraction at work.
Static vs dynamic: a static structure has its memory fixed at compile time (a plain array) — fast, but it can overflow or waste space. A dynamic structure grows and shrinks at run time using the heap — flexible, but with pointer overhead and a risk of running out of heap memory.
A stack is LIFO: the last item pushed is the first popped. It has a single stack pointer holding the index of the top element.
Overflow = pushing onto a full stack. Underflow = popping an empty one. Both must be tested for.
Stacks are everywhere:
A queue is FIFO: first in, first out. It needs two pointers — front and rear.
A linear queue has a fatal flaw. Every dequeue advances front, so the used space at the low end is never reclaimed: eventually rear hits the end of the array while the front of the array sits empty.
The circular queue fixes this by wrapping the pointers round with MOD:
A separate size counter (or one deliberately wasted slot) distinguishes "full" from "empty", since in both cases front and rear can coincide.
Priority queue: items are dequeued in order of priority, not arrival. Equal priorities are served in arrival order. Used by operating-system schedulers and by Dijkstra's algorithm.
A graph is a set of vertices (nodes) joined by edges (arcs). Edges may be directed (one-way) or undirected, and weighted (carrying a cost, distance or time) or unweighted.
Two standard representations:
| Adjacency matrix | Adjacency list |
|---|---|
| An n × n table; cell [i][j] holds the weight of the edge i→j (or 0). | For each vertex, a list of the vertices it connects to. |
| Space O(n²) regardless of the number of edges. | Space O(n + e) — only real edges are stored. |
| Testing "is i joined to j?" is O(1). | Testing that edge needs a scan of one list. |
| Best for dense graphs; convenient to program. | Best for sparse graphs — e.g. a road network. |
Sparse means: the number of edges is far smaller than the maximum n(n−1)/2. A road network with 10 000 junctions has perhaps 25 000 roads, not 50 million — an adjacency matrix would be over 99.9% zeros.
A tree is a connected, undirected graph with no cycles. A rooted tree adds a designated root; every other node has exactly one parent. Nodes with no children are leaves.
In a binary search tree (BST), every node has at most two children and obeys one invariant:
That single rule makes searching a halving process. Searching, inserting and deleting are O(log n) in a balanced tree — but if you insert already-sorted data the tree degenerates into a linked list and collapses to O(n).
Traversals — the name tells you when the root is visited:
A hash table converts a key straight into an array index using a hashing algorithm:
No searching is needed — the key computes its own address, so lookup, insert and delete are O(1) on average. That is the whole point.
A collision happens when two different keys hash to the same index. Two standard fixes:
As the load factor (items ÷ slots) rises, collisions rise. Above roughly 0.7 the table is usually rehashed into a bigger array — every key is recomputed against the new size.
Dictionary: an ADT of <key, value> pairs, almost always implemented as a hash table. A good hash function is fast, deterministic and distributes keys uniformly. Table sizes are usually prime to spread the MOD results out.
AQA treats a vector in three equivalent ways: as a list of numbers [2, 3, −1], as a function from an index set to the reals, and as an arrow in n-dimensional space.
Vector addition and scalar multiplication work component by component:
The dot product multiplies matching components and sums the results, giving a single number (scalar):
A convex combination of a and b is αa + βb where α, β ≥ 0 and α + β = 1. Geometrically it lands somewhere on the straight line between the two vectors.
Why a computer scientist cares: the dot product measures similarity. Machine-learning models, search engines and recommender systems compare documents or images by turning them into vectors and taking dot products.
Tap a use case, then tap the structure it needs.
Tap an item on the left, then its partner on the right.
Arrays & records: array = same type, indexed, O(1) access; record = mixed-type fields
Stack: LIFO · push/pop/peek · overflow & underflow · call stack, undo, RPN, DFS
Queue: FIFO · front & rear · circular queue wraps with MOD · priority queue serves by priority
Graph: adjacency matrix O(n²) for dense; adjacency list O(n + e) for sparse
Tree / BST: left < node < right · O(log n) balanced, O(n) degenerate · pre / in (sorted) / post-order
Hash table: index = h(key) · collisions → probing or chaining · rehash above ~0.7 load factor
Vector: component-wise add and scale · dot product gives a scalar · convex combination lies between
That is the whole of AQA 4.2. Press Finish to see your score.
You've worked through Fundamentals of data structures for AQA A-level Computer Science (7517). 🎉
Your stars: 0 / 0
Next: test yourself in the Verify stage.