HookThe Tube map that threw away London
In 1931 an out-of-work engineering draughtsman named Harry Beck redrew the London Underground map in his spare time. He did something that looked like vandalism: he threw away London. Real distances, the true curve of every tunnel, the position of the Thames — all gone. What he kept was the only thing a passenger actually needs: which stations connect to which lines, and where you can change between them. London Transport thought it too radical and printed just a trial run in 1933; it sold out, and Beck's design has been the template ever since. Without ever using the word, Beck had drawn a graph — stations as nodes, track as edges — and in doing so he had performed the defining act of computer science: deciding what to keep and what to discard so that the operations you care about become easy.
That is exactly what a data structure is: a deliberate arrangement of data, chosen so that the things you do most often are fast, at the cost of things you rarely do being slow. Store your edit history as a stack and Ctrl+Z becomes a single pop. Store a million contacts in a hash table and a lookup that would otherwise scan the whole list finishes in one step. Model a road network as a weighted graph and the shortest route falls straight out of an algorithm. This section is the catalogue of those structures — arrays, records and files, then the abstract data types built on them: stacks, queues, graphs, trees, hash tables, dictionaries and vectors — and the trade-offs that make one of them the right box and another a slow, expensive mistake.
ModelStatic and dynamic: arrays, records and files
Every structure is one of two shapes. A static structure has its size fixed when the program is written — the classic example is the array, a block of memory holding a fixed number of same-typed elements laid out contiguously and reached by index. Static structures are fast and predictable but waste space if over-sized and break if you need more. A dynamic structure grows and shrinks at run time (a linked list, for instance, chaining nodes together with pointers), trading a little speed and memory overhead for flexibility. Knowing which you are dealing with is half of every data-structure question.
Arrays come in one dimension (a list) and several. A two-dimensional array is a table addressed by row and column, stored in memory one row after another (row-major order), which is why the position of an element can be calculated arithmetically. To store data of mixed types you need a record: a user-defined composite type gathering several fields, each field a named attribute of one entity — a Student record might hold an integer id, a string name and a real average. A file is a sequence of records held on secondary storage, and a key field is the field whose value uniquely identifies each record (the id, never the name). Fields, records and files scale the same idea up: a field describes one thing, a record describes one entity, a file describes many.
Addressing a 2D array. Suppose grid is a 3-row by 4-column array of 4-byte integers, stored row-major, with the first element at memory address 1000. Where is grid[2][3] (row index 2, column index 3, counting from 0)? First find its position in the flattened row-major order: position = row × numberOfColumns + column = 2 × 4 + 3 = 11. It is the twelfth element (index 11). Its address is base + position × elementSize = 1000 + 11 × 4 = 1044. That single formula — base + (row × cols + col) × size — is why an array lookup is instant: no searching, just arithmetic straight to the byte.
ModelAbstract data types: the idea behind the idea
An abstract data type (ADT) is a logical description of a structure by what it does, not how it is built. A stack is defined entirely by its operations — push, pop, peek, isEmpty — and that definition says nothing about whether it sits on top of an array or a linked list underneath. This separation is information hiding at work: the code that uses a stack only needs the interface, so the implementation can be swapped without breaking a single caller. Change the storage from an array to a linked list to remove a size limit, and every program using the stack keeps working untouched.
This is why the same ADT can have a static and a dynamic implementation. A stack built on a fixed array has a maximum height and can suffer overflow; the same stack built on a linked list grows until memory runs out. The ADT — the contract — is identical; only the engineering underneath differs. The structures the rest of this section covers (queue, list, graph, tree, dictionary) are all ADTs in this sense: define them by their operations first, choose an implementation second. Examiners reward candidates who keep the two levels apart, because conflating 'a stack' with 'an array with a top pointer' is precisely the confusion that abstraction exists to prevent.
One contract, two implementations. The Stack ADT promises four operations: push(item), pop(), peek() and isEmpty(). Implementation A uses a fixed array plus a top pointer that starts at −1; push does top ← top + 1 then stores the item, and it can overflow when top reaches the last index. Implementation B uses a linked list with a head pointer; push creates a new node pointing at the old head, and it never overflows until memory is exhausted. A program written against the four-operation contract cannot tell which one it is using — that is the whole point of an ADT.
MechanismStacks and queues: order is everything
A stack is Last-In-First-Out (LIFO): the last item pushed is the first popped, like a spring-loaded stack of plates. It has a single top pointer and three core moves — push (add to the top), pop (remove from the top), peek (read the top without removing). Pushing onto a full array-stack is overflow; popping an empty one is underflow. Stacks are everywhere the most recent thing must be handled first: the call stack from the previous section, undo/redo, backtracking out of a maze, and evaluating expressions.
A queue is First-In-First-Out (FIFO), like an orderly line: items enqueue at the rear and dequeue from the front, using two pointers. A naïve linear queue wastes space — as the front advances, the freed slots at the start are stranded. The fix is a circular queue, where the rear and front pointers wrap around to the beginning using modulo arithmetic, reusing the emptied slots. A priority queue is a further variant where items leave in priority order rather than arrival order — the model for a hospital triage list or an operating-system scheduler.
A circular queue with 5 slots (indices 0–4). Start empty with front = 0, rear = −1. Enqueue A, B, C: rear moves 0, 1, 2, so slots hold A B C. Dequeue once: A leaves, front advances to 1, and slot 0 is now free. Enqueue D, E: rear moves to 3 then 4, filling the array. Enqueue F: instead of reporting 'full', the rear wraps — rear = (rear + 1) MOD 5 = (4 + 1) MOD 5 = 0 — dropping F into the freed slot 0. That single MOD size step is the difference between a queue that reuses its space and one that jams solid after a few dequeues.
For contrast, a stack trace: push 10, push 20, push 30 leaves top = 2 holding 30. peek() returns 30 without changing top. pop() returns 30 and drops top to 1, so the next pop would return 20 — last in, first out.
MechanismGraphs and trees
A graph is a set of vertices (nodes) joined by edges. Edges can be directed (one-way, an arrow) or undirected (two-way), and weighted (each edge carries a cost — distance, time, price) or unweighted. Graphs model anything relational: road and rail networks, the internet, social connections. There are two standard implementations, and choosing between them is a stock exam question. An adjacency matrix is a V×V grid where cell [i][j] records the edge from i to j; it uses O(V²) space and answers 'is there an edge?' instantly, so it suits dense graphs. An adjacency list stores, for each vertex, a list of its neighbours; its space grows with the number of edges, so it suits sparse graphs — most real networks.
A tree is a special graph: connected, with no cycles, and (usually) with one distinguished root. Every other node has exactly one parent; nodes with no children are leaves; any node plus its descendants form a subtree. A binary tree restricts every node to at most two children (a left and a right). The workhorse version is the binary search tree (BST), which keeps an ordering invariant: at every node, all values in the left subtree are smaller and all values in the right subtree are larger. That invariant is what makes a BST searchable in roughly log-of-n steps — the subject of the next section's traversal and search algorithms.
Two views of one graph. Take four vertices A, B, C, D with undirected edges A–B, A–C, B–D and C–D. As an adjacency matrix (1 = edge, 0 = none), row A reads 0 1 1 0, row B reads 1 0 0 1, row C reads 1 0 0 1, row D reads 0 1 1 0 — and notice it is symmetric across the diagonal, which is always true for an undirected graph. As an adjacency list the same graph is far leaner: A → [B, C], B → [A, D], C → [A, D], D → [B, C]. With only 4 edges the list stores 8 entries while the matrix reserves all 16 cells — the space argument for lists on sparse graphs, in miniature.
MechanismHash tables and dictionaries
A hash table stores key–value pairs and retrieves them in close to constant time — no searching. The trick is a hash function that turns a key into an array index directly, so you compute where a value lives rather than looking for it. The catch is a collision: two different keys hashing to the same index. There are two standard cures. Chaining stores a linked list at each slot, so colliding keys queue up in the same bucket. Open addressing (rehashing) probes for the next free slot instead. Either way, performance depends on the load factor — the ratio of stored items to available slots. As it climbs, collisions multiply and lookups slow; past a threshold (often around 0.7) the table is resized and every key rehashed into the bigger array.
A dictionary is the ADT this typically implements: an unordered collection of key→value associations with fast insert, lookup and delete by key. Python's dict, JavaScript's objects and most language 'maps' are hash tables underneath. The dictionary is the interface (associate a key with a value); the hash table is the machinery (compute an index, handle collisions, watch the load factor). Keeping that distinction straight is, once again, the ADT-versus-implementation point from earlier in this section.
Hashing with collisions. Use a 10-slot table and the hash function h(key) = key MOD 10. Insert 27: 27 MOD 10 = 7, so it lands in slot 7. Insert 13: 13 MOD 10 = 3, slot 3. Insert 47: 47 MOD 10 = 7 — collision, slot 7 is taken by 27. Under chaining, slot 7 becomes a small list [27, 47]. Under open addressing with linear probing, 47 checks slot 8, finds it free, and settles there. After these three inserts the load factor is 3 ÷ 10 = 0.3 — comfortably low, so lookups stay fast. Push it toward 0.8 and slot 7's chain lengthens, dragging its lookups from one step toward many.
DataVectors
A vector, in the AQA sense, is an ordered list of numbers of fixed length — its dimension. A 3-dimensional vector is just three numbers in order. It can be represented three ways: as a one-dimensional array, as a list, or as a dictionary mapping each index to its value (useful when most entries are zero). Geometrically a vector is an arrow, or a point, in n-dimensional space, which is why vectors underpin graphics, physics engines and machine learning — a pixel's colour, a position, a set of features are all vectors.
The operations the specification names are all component-wise or reductions. Vector addition adds matching components, producing another vector of the same dimension. Scalar–vector multiplication multiplies every component by a single number, stretching or shrinking the arrow. The dot product multiplies matching components and sums the results, collapsing two vectors into a single number (a scalar) that measures how aligned they are. A convex combination is a weighted blend of vectors whose weights are non-negative and sum to 1 — it always lands on the line (or region) between them, which is how you interpolate smoothly from one point to another.
Working the four operations. Let a = (2, 3) and b = (4, 1). Addition is component-wise: a + b = (2 + 4, 3 + 1) = (6, 4). Scalar multiplication scales every component: 3a = (3 × 2, 3 × 3) = (6, 9). The dot product multiplies matching components and adds: a · b = (2 × 4) + (3 × 1) = 8 + 3 = 11 — one number, not a vector. A convex combination with weights 0.25 and 0.75 (which sum to 1) is 0.25a + 0.75b = (0.25 × 2 + 0.75 × 4, 0.25 × 3 + 0.75 × 1) = (0.5 + 3, 0.75 + 0.75) = (3.5, 1.5) — a point three-quarters of the way from a toward b.
VocabularyKey terms the mark scheme pays for
TrapsMisconceptions that cost marks
ExamWhat examiners want
Data-structure marks split cleanly across the assessment objectives, so read the command word. AO1 questions ('describe a stack', 'state two operations of a queue') want the precise vocabulary — LIFO versus FIFO, top pointer, overflow, front and rear — stated exactly, plus a small labelled diagram, which examiners consistently reward. AO2 questions hand you a scenario and ask you to trace or choose: to trace, redraw the structure after every operation and mark the pointers each time (for a circular queue, always show the (rear + 1) MOD size step — that is where the marks are); to choose, name the structure AND justify it against the alternative ('a stack, because the most recent action must be undone first'). Bare naming with no justification caps you at the lower band.
AO3 questions ('evaluate', 'compare') want a reasoned trade-off, not a list of features. The examinable comparisons are the ones in these blocks: adjacency matrix versus list (space against lookup speed, dense against sparse), array against linked-list implementations of the same ADT (fixed size and overflow against dynamic growth and pointer overhead), and hash table against a linear structure (near-constant lookup against the load-factor cost). Frame each as 'X is better when…, but Y wins when…' and anchor it to the specific data in the question. When drawing a graph or tree, label vertices and edge weights clearly and keep directed edges as arrows — an unlabelled sketch earns nothing even when your reasoning is right.