Arrays, records and abstract data types

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.

Stacks — last in, first out

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:

• the call stack — return addresses, parameters and locals for each subroutine call (this is why deep recursion causes a stack overflow);
• undo in an editor;
• evaluating reverse Polish notation;
• backtracking in depth-first search.

Queues — including the circular queue

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.

Your turn — circular queue

Stack or queue?

Graphs

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:

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.

Choosing a graph representation

Trees and binary search trees

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:

• Pre-order: root, left, right → A B D E C F G. (Used to copy a tree, or to output prefix expressions.)
• In-order: left, root, right → D B E A F C G. (On a BST this outputs the data in sorted order.)
• Post-order: left, right, root → D E B F G C A. (Used to delete a tree, and to produce reverse Polish.)

Your turn — post-order traversal

Binary search trees

Hash tables and dictionaries

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:

• Open addressing / linear probing — walk forward to the next free slot. Simple, but causes clustering, which degrades performance.
• Chaining — each slot holds a list of all items that hashed there.

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.

Your turn — hashing with linear probing

Vectors

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.

Your turn — the dot product

Hash tables

Which structure fits the job?

Tap a use case, then tap the structure it needs.

Match the structure to its defining feature

Tap an item on the left, then its partner on the right.

The big ideas to know

That is the whole of AQA 4.2. Press Finish to see your score.