Notes · Computer ScienceUK · A-Levels

Fundamentals of data structures

A data structure is a way of organising data so that the operations a program needs are efficient. This chapter separates the abstract data type - the operations promised - from its concrete implementation, then builds the core structures: arrays and records, the last-in-first-out stack and the first-in-first-out queue, the pointer-linked list, graphs and trees, and the hash table that gives near-constant-time lookup. Choosing the right structure is one of the most heavily assessed design skills in the whole A-Level.

5 sections~19 min reading time3 competenciesLevel Foundation 1 · Standard 2 · Advanced 2

T·0222 / 14

Exam profile

AO1 · Know the properties and operations of arrays, records, stacks, queues, linked lists, graphs, trees and hash tables, and the abstract/concrete distinctionAO2 · Trace pushes and pops, enqueues and dequeues, list insertions and deletions, and hashing with collision resolutionAO3 · Select and justify an appropriate data structure for a given problem

Operators:definedescribetraceexplaincomparedesign

basic level

AS-Level expects arrays, records, stacks and queues and their operations, plus the idea of an abstract data type.

higher level

The full A-Level adds linked lists, graphs (with adjacency matrix and list representation), trees including binary trees, and hash tables with collision resolution.

Depth

Text

Contents · 5 sections

Fundamentals of data structures

Arrays, records and abstract data types#

FoundationAQA 7517 4.2.1AQA 7517 4.2.2DfE GCE Computer Science - data structures

An abstract data type (ADT) is defined by the operations it supports and the rules those operations obey, not by how it is stored - it is a promise about behaviour. A stack, for instance, promises push, pop and isEmpty with last-in-first-out order; nothing in that promise says whether it is built from an array or a linked list. Separating the ADT (the interface) from its concrete implementation (the storage and code) is the central abstraction of this chapter: a program can be written against the ADT and the implementation swapped underneath without any other code changing.

An array is the most basic concrete structure: a fixed-size, ordered collection of elements of the same type, stored contiguously and accessed by an integer index. Because the elements are the same size and adjacent in memory, the address of element

i

is computed directly as

\text{base} + i \times \text{elementSize}

, giving constant-time (

O(1)

) random access - the array's defining advantage. Arrays may be 1-dimensional (a list), 2-dimensional (a table or grid, indexed by row and column) or 3-dimensional (a stack of tables); a 2-D array

A[r][c]

is the natural model for a matrix, board or image.

A record groups a fixed set of named fields, each of its own type, into a single value - the row of a database table is a record. Where an array holds many values of one type indexed by number, a record holds several values of different types accessed by name (

\texttt{student.name}

\texttt{student.mark}

). Combining the two gives the workhorse of data handling: an array of records models a table of many rows, and is how a program holds a list of students, transactions or products in memory.

The trade-off of the array is its fixed size and the cost of insertion and deletion in the middle: to insert an element you must shift every later element up one place, an

O(n)

operation, and static arrays cannot grow. These weaknesses motivate the dynamic, pointer-based structures - lists, stacks and queues built on linked nodes - that follow. Choosing between them is a question of which operations must be fast: random access favours the array; frequent insertion and deletion favour a linked structure.

\text{address}(A[i]) = \text{base} + i \times \text{elementSize}

Array element address

Because elements are equal-sized and contiguous, any index is reached in constant time - the array's key advantage.

Worked example

Addressing a 2-D array in row-major order

A 2-D array grid has 4 columns and is stored row by row (row-major). If element grid[0][0] is at address 200 and each element occupies 4 bytes, find the address of grid[2][1].

Linear position
In row-major order element $[r][c]$ has linear index $r \times \text{columns} + c = 2 \times 4 + 1 = 9$ .
Address
Add the offset to the base: $200 + 9 \times 4 = 200 + 36 = 236$ .

Result: grid[2][1] is at address 236 - the same constant-time arithmetic the hardware uses for every array access.

Typical mistakes

Confusing an array (many values of one type, indexed by number) with a record (several fields of different types, accessed by name).
Off-by-one indexing: a zero-indexed array of length $n$ has valid indices 0 to $n-1$ , so index $n$ is out of bounds.

Active revision

A program stores 30 students, each with an id (integer), name (string) and average mark (real). Describe the data structure you would use, give the type of one element, and state the index of the tenth student in a zero-indexed array.

Active recall

Recall the key points — then reveal.

Sources: GCE AS and A level subject content for computer science (Department for Education) · AQA A-level Computer Science 7517 specification (AQA)

Stacks and queues#

StandardAQA 7517 4.2.3AQA 7517 4.2.4DfE GCE Computer Science - stacks and queues

A circular queue

Fig. 1Six slots arranged in a ring. Items enter at the rear and leave at the front; when a pointer passes the last slot it wraps back to slot 0 using modulo arithmetic, so cells freed by dequeuing are reused. Here the queue holds C, D, E between the front (slot 2) and rear (slot 4).

A stack is a last-in-first-out (LIFO) structure: the last item pushed is the first popped. All access is at one end, the top, tracked by a stack pointer that indexes the next free (or the current top) position. The core operations are push (add to the top, and increment the pointer), pop (remove from the top, and decrement the pointer), peek/top (read the top without removing it), and isEmpty/isFull. Stacks are everywhere in computing: the call stack that manages subroutine returns, the undo history of an editor, expression evaluation, and the backtracking of a depth-first traversal all rely on LIFO behaviour.

A queue is a first-in-first-out (FIFO) structure: items are added at the rear (enqueue) and removed from the front (dequeue), so they leave in the order they arrived - like a queue of people. It needs two pointers, front and rear. Queues model any situation of fair, ordered waiting: a printer's job queue, the buffer between a fast producer and a slow consumer, and the frontier of a breadth-first traversal.

A naive linear queue in an array wastes space: as items are dequeued the front pointer marches up the array, leaving unusable empty cells behind it. The circular queue solves this by wrapping the pointers round to the start using modulo arithmetic - after position

n-1

comes position

0

again - so the freed cells are reused (shown opposite). The rear advances as

\text{rear} \leftarrow (\text{rear} + 1)\ \text{MOD}\ n

, and the same for the front; a separate count (or a reserved empty cell) distinguishes the full state from the empty state, since in both cases the two pointers coincide.

A priority queue relaxes strict FIFO: each item carries a priority and the highest-priority item is dequeued first, with ties broken by arrival order. It is the structure behind scheduling and behind Dijkstra's shortest-path algorithm, where the next node to settle is always the closest unvisited one. Both stacks and queues are ADTs and can be implemented over either an array (simple, fixed capacity) or a linked list (grows dynamically) - the choice of implementation does not change the LIFO/FIFO promise.

\text{rear} \leftarrow (\text{rear} + 1)\ \text{MOD}\ n

Circular queue advance

Modulo the capacity $n$ wraps the pointer from the last cell back to the first, reusing freed space.

Worked example

Tracing a stack

A stack is empty. Trace push(4), push(7), pop(), push(2), push(9), pop(), giving the contents (base to top) and the value returned by each pop.

push 4, push 7
Contents base-to-top: [4, 7]. The stack pointer is at 7.
pop
Removes and returns the top, 7. Contents: [4].
push 2, push 9
Contents: [4, 2, 9].
pop
Removes and returns the top, 9. Contents: [4, 2].

Result: The pops return 7 then 9; the stack finishes as [4, 2]. The most recently pushed item is always the first popped (LIFO).

Typical mistakes

Muddling LIFO (stack) with FIFO (queue): a stack removes the most recently added item, a queue the least recently added.
Forgetting the wrap-around in a circular queue, or failing to distinguish full from empty when front and rear coincide.

Active revision

A circular queue has capacity 5 (indices 0-4) and is empty. Trace enqueue(A), enqueue(B), enqueue(C), dequeue(), enqueue(D), enqueue(E), enqueue(F), giving the front and rear pointers and contents after each step.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

Linked lists#

StandardAQA 7517 4.2.5DfE GCE Computer Science - linked lists

A singly linked list

Fig. 2The head points to the first node. Each node stores a value and a pointer to the next; the final node points to null. Inserting or deleting a node only redirects pointers - no elements are shifted.

A linked list is a dynamic structure built from nodes, each holding a data field and a pointer to the next node. A separate head pointer identifies the first node, and the last node's pointer holds a special null value marking the end. Unlike an array, a linked list is not stored contiguously and has no fixed size - nodes live wherever memory is free, threaded together by their pointers (shown opposite). To visit the list you follow the pointers from the head until you reach null - a traversal.

The great strength of the linked list is cheap insertion and deletion: to insert a node you create it and redirect two pointers - the new node points to where its predecessor pointed, and the predecessor now points to the new node - an

O(1)

operation once you are at the position, with no shuffling of other elements. Deletion is the mirror image: the predecessor's pointer is redirected past the removed node to its successor. This is exactly what an array cannot do cheaply, which is why lists underpin dynamic stacks, queues and the chaining used in hash tables.

The price paid is the loss of random access. There is no address arithmetic; to reach the

k

-th node you must start at the head and follow

k

pointers, an

O(n)

operation, and you cannot jump straight to the middle. A linked list is therefore the right choice when the workload is dominated by insertion and deletion and traversal is sequential, and the wrong choice when frequent indexed access is needed.

Implementations vary. A singly linked list has one forward pointer per node; a doubly linked list adds a backward pointer so it can be traversed both ways and a node deleted knowing only itself; a circular linked list has the last node point back to the first. In languages without built-in pointers a linked list is often simulated inside two parallel arrays - a data array and a 'next' array of indices - together with a free list that threads the unused cells, so that allocating and freeing a node is itself a pointer operation.

Worked example

Inserting into a linked list

A list holds 12 -> 30 -> 47 -> null. Insert 25 so the list becomes 12 -> 25 -> 30 -> 47. Describe the pointer changes in the correct order.

Create the node
Allocate a new node holding 25; call it P. Its next pointer is not yet set.
Attach forward first
Set P.next to the node holding 30 (the current successor of 12). The new node now points into the list; nothing is lost.
Redirect the predecessor
Set the next pointer of the node holding 12 to P. Order matters: attach P before changing 12's pointer, or the rest of the list would be orphaned.

Result: Two pointers change (P.next and 12.next); no other node moves. The list is now 12 -> 25 -> 30 -> 47 -> null.

Typical mistakes

Losing part of the list during insertion or deletion by redirecting the pointers in the wrong order (always attach the new node before detaching the old link).
Forgetting the null terminator, or assuming a linked list allows array-style random access by index.

Active revision

A singly linked list holds 12 -> 30 -> 47 -> null with head pointing at 12. Describe, in terms of pointers only, how to insert the value 25 between 12 and 30, and state how many pointers you must change.

Active recall

Recall the key points — then reveal.

Sources: GCE AS and A level subject content for computer science (Department for Education)

Graphs and trees#

AdvancedAQA 7517 4.2.6AQA 7517 4.2.7DfE GCE Computer Science - graphs and trees

An undirected graph

Fig. 3Four vertices A, B, C, D with edges A-B, A-C, B-C and C-D. Its adjacency matrix is shown in the next figure; because the graph is undirected the matrix is symmetric about the diagonal.

A graph is a set of vertices (nodes) joined by edges, modelling any network of relationships - roads between towns, links between web pages, friendships, dependencies. Edges may be directed (one-way, an arc) or undirected (two-way), and weighted (carrying a cost such as distance or time) or unweighted. Graphs are the most general of the structures in this chapter: trees and linked lists are special cases of them.

A graph is stored in one of two standard ways. An adjacency matrix is a

V \times V

grid whose entry

[i][j]

is 1 (or the edge weight) if there is an edge from

i

j

and 0 otherwise; for an undirected graph the matrix is symmetric (shown opposite alongside its graph). It gives

O(1)

edge lookup but uses

O(V^2)

space, wasteful for a sparse graph with few edges. An adjacency list instead stores, for each vertex, a list of its neighbours; it uses space proportional to the number of edges, which is far more efficient for sparse graphs, at the cost of slower lookup of a specific edge.

A tree is a connected, acyclic graph: any two vertices are joined by exactly one path and there are no cycles. A rooted tree singles out one vertex as the root; every other vertex has exactly one parent and zero or more children, and a vertex with no children is a leaf. Trees model hierarchy - a file system, an organisation chart, the structure of an HTML document, and the class hierarchy of a program - and their recursive shape (each subtree is itself a tree) makes recursion the natural way to process them.

A binary tree restricts each node to at most two children, a left and a right. The most important use is the binary search tree (BST), whose ordering invariant is that for every node all keys in its left subtree are smaller and all keys in its right subtree are larger. This invariant makes searching, inserting and finding the minimum or maximum take time proportional to the tree's height -

O(\log n)

for a balanced tree - and it makes an in-order traversal emit the keys in sorted order. Binary trees also express Huffman codes and arithmetic expressions, met in the algorithms chapter.

The adjacency matrix of the graph

Fig. 4Entry [row][col] is 1 when an edge joins those vertices. The matrix is symmetric - entry [A][B] equals entry [B][A] - because the graph is undirected. A sparse graph makes most entries 0, which is why an adjacency list can save space.

Worked example

Building a binary search tree

Insert the keys 5, 3, 8, 1, 4 into an empty binary search tree, in that order. Describe where each key lands.

Insert 5
The tree is empty, so 5 becomes the root.
Insert 3, then 8
3 < 5 so it goes to the left of 5; 8 > 5 so it goes to the right of 5.
Insert 1, then 4
1 < 5 (go left to 3), 1 < 3 so it becomes 3's left child. 4 < 5 (go left to 3), 4 > 3 so it becomes 3's right child.

Result: Root 5; left child 3 (with children 1 and 4); right child 8. An in-order traversal reads 1, 3, 4, 5, 8 - sorted order, as the BST invariant guarantees.

Typical mistakes

Forgetting that the adjacency matrix of an undirected graph is symmetric, or entering a directed edge in both cells.
Confusing a general tree with a binary search tree - only the BST carries the smaller-left/larger-right ordering invariant.

Active revision

Draw the adjacency matrix for the undirected graph with vertices A, B, C, D and edges A-B, A-C, B-C, C-D. Then insert the keys 5, 3, 8, 1, 4 into an initially empty binary search tree, in that order, and draw the result.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

Hash tables and dictionaries#

AdvancedAQA 7517 4.2.8DfE GCE Computer Science - hash tables

A hash table with separate chaining

Fig. 5Keys are hashed by

h(k)=k\bmod 7

. 15 hashes to 1 and 8 also hashes to 1, so they are chained in a short linked list at slot 1. 22 hashes to 1 as well (

22\bmod 7=1

) and joins the chain; 4 hashes to 4. Lookups hash to a slot then scan its short chain.

A hash table stores key-value pairs so that a value can be found from its key in, on average, constant time - dramatically faster than searching a list. The trick is a hash function

h

that maps a key directly to an index in an underlying array: instead of searching for the key, you compute where it must be. A simple hash for integer keys is

h(k) = k\ \text{MOD}\ m

, where

m

is the table size; for a string key the character codes are combined into a number first. A good hash function is fast, deterministic, and spreads keys as evenly as possible across the table.

Because a hash function maps a large space of possible keys onto a small array, two different keys can hash to the same index - a collision. Collisions are inevitable (the pigeonhole principle guarantees them once there are more possible keys than slots), so every hash table needs a collision-resolution strategy. In separate chaining each slot holds a linked list of all the items that hashed there, and a collision simply appends to that list. In open addressing (for example linear probing) a collision instead searches forward for the next free slot. The load factor - items divided by slots - governs performance: as it approaches 1, collisions pile up and lookups slow, so the table is resized (rehashed) when it grows too full.

The figure opposite shows separate chaining: keys are hashed by

k\ \text{MOD}\ 7

, and 15 and 8 both land in slot 1, so they are chained together. To look up a key you hash it to find the slot, then scan that slot's short chain for the exact key; to insert, you hash and append; to delete, you hash and unlink. With a good hash and a low load factor the chains stay short and all three operations are close to

O(1)

; in the worst case (every key colliding) they degrade to

O(n)

, the length of a single long chain.

A dictionary (also called a map or associative array) is the abstract data type of a collection of key-value pairs with the operations add, look up, and remove by key. The hash table is its usual concrete implementation, which is why dictionaries offer near-instant lookup. Dictionaries are ubiquitous - symbol tables in compilers, caches, database indexes, word-frequency counts and the built-in dict/map types of modern languages all rest on hashing.

h(k) = k \bmod m

Modulo hash function

Maps an integer key $k$ to an index in a table of size $m$ . Choosing $m$ prime helps spread keys evenly.

\text{load factor} = \dfrac{\text{number of items}}{\text{number of slots}}

Load factor

As it approaches 1 collisions become frequent and lookups slow; the table is usually resized before then.

Worked example

Hashing with chaining

Insert 15, 8, 22, 4 into a table of size 7 using $h(k)=k\bmod 7$ and separate chaining. Give each key's slot and the final chains.

Hash each key
$15\bmod 7 = 1$ ; $8\bmod 7 = 1$ ; $22\bmod 7 = 1$ ; $4\bmod 7 = 4$ .
Place with chaining
15 goes to slot 1. 8 collides at slot 1 and is chained after 15. 22 also hashes to 1 and is chained after 8. 4 goes to the empty slot 4.

Result: Slot 1 holds the chain 15 -> 8 -> 22; slot 4 holds 4; all other slots are empty. Looking up 22 hashes to slot 1 and scans the chain to the third node.

Typical mistakes

Believing a hash table lookup is always $O(1)$ - it is $O(1)$ on average but degrades to $O(n)$ when many keys collide or the load factor is too high.
Confusing the dictionary ADT (the key-value interface) with the hash table (one way of implementing it).

Active revision

Using the hash function $h(k) = k\ \text{MOD}\ 7$ and separate chaining, insert the keys 15, 8, 22, 1 into an empty table of size 7. State the slot each occupies and which keys share a chain.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Computer Science 7517 specification (AQA)

References & sources

Sources

Department for Education

GCE AS and A level subject content for computer science

AQA

AQA A-level Computer Science 7517 specification

Fundamentals of data structures

5 sections~19 min reading time3 competenciesLevel Foundation 1 · Standard 2 · Advanced 2

Fundamentals of data structures

Key points

Addressing a 2-D array in row-major order

Key points

Tracing a stack

Key points

Inserting into a linked list

Key points

Building a binary search tree

Key points

Hashing with chaining

Sources

Fundamentals of data structures

Key points

Addressing a 2-D array in row-major order

Key points

Tracing a stack

Key points

Inserting into a linked list

Key points

Building a binary search tree

Key points

Hashing with chaining

Sources