What data structures does 4.2 cover?

Arrays (one, two and three dimensional) and records, queues (linear, circular and priority), stacks, graphs (with adjacency matrix and list representations), trees including binary search trees, hash tables, and dictionaries. You need to know how each works, trace its operations, and choose the right one for a problem.

What is the difference between a stack and a queue?

A stack is last-in first-out (LIFO): items are pushed and popped at one end, the top. A queue is first-in first-out (FIFO): items are added at the rear and removed from the front. Stacks suit reversing data and the call stack for subroutine calls and recursion; queues suit serving items in arrival order, such as a print spooler.

What is the difference between a static and a dynamic data structure?

A static data structure has a fixed size set when the program is compiled, with memory reserved in advance, such as a standard array. A dynamic data structure can grow and shrink at run time using the heap, such as a linked list. Static is simple and predictable but can waste memory or overflow; dynamic uses memory efficiently but has pointer and allocation overhead.

How does a hash table achieve fast look-up?

A hashing algorithm turns a key into an array index, so an item can be stored and retrieved directly without searching, giving average constant-time access. When two keys hash to the same index a collision occurs, resolved by rehashing (probing for another slot) or chaining (a linked list at each index). Dictionaries are usually implemented with a hash table for this reason.

What makes a binary search tree useful?

A binary search tree orders nodes so that smaller values go to the left subtree and larger to the right of every node. This lets you search, insert and delete in about O(log n) time on a balanced tree by halving the remaining nodes at each step, and an in-order traversal outputs the values in sorted order. If items are inserted in sorted order the tree becomes unbalanced and degrades to O(n).

EnglandComputer Science

AQA A-Level Computer Science 4.2 Fundamentals of data structures: arrays, queues, stacks, graphs, trees, hash tables and dictionaries

A deep-dive AQA A-Level Computer Science guide to 4.2 Fundamentals of data structures. Covers arrays and records, queues, stacks, graphs, trees, hash tables and dictionaries, with how each works, its operations, and when to use it.

Generated by Claude Opus 4.818 min read4.2Updated 2026-06-02

Reviewed by: AI editorial process; not yet individually human-reviewed

Jump to a section

What 4.2 actually demands
Arrays and records
Stacks and queues
Graphs and trees
Hash tables and dictionaries
Check your knowledge

What 4.2 actually demands

Data structures are the containers algorithms work on. AQA expects you to know how each structure works, to trace its operations by hand, and to choose the right structure for a problem, justifying the choice. This module runs from simple arrays and records up to graphs, trees and hash tables, and pairs directly with the algorithms module.

Arrays and records

An array holds many items of the same type accessed by index, in one, two or three dimensions. A record groups fields of different types under one name. The key distinction here is static versus dynamic structures: a static structure has a fixed size, a dynamic one grows and shrinks at run time using the heap.

Stacks and queues

A stack is LIFO (push and pop at the top), used for reversing data, expression evaluation and the call stack that handles subroutine calls and recursion. A queue is FIFO (enqueue at the rear, dequeue at the front); a circular queue reuses freed slots with modulo arithmetic and a priority queue serves the highest-priority item first.

Graphs and trees

A graph is vertices joined by edges, directed or undirected, weighted or not, stored as an adjacency matrix (fast lookup, more memory) or an adjacency list (memory-efficient for sparse graphs). A tree is a connected acyclic graph with a root; a binary search tree orders values left-smaller, right-larger for fast searching and a sorted in-order traversal.

Hash tables and dictionaries

A hash table stores key-value pairs by hashing the key to an index, giving average constant-time access, with collisions resolved by rehashing or chaining. A dictionary is the abstract data type of unique key-value pairs, usually implemented with a hash table.

Check your knowledge

State the difference between a static and a dynamic data structure. (2 marks)
State the order in which items leave a stack and a queue. (2 marks)
Explain one advantage of a circular queue over a linear queue. (2 marks)
Give one reason to use an adjacency list rather than an adjacency matrix. (2 marks)
State what an in-order traversal of a binary search tree produces. (1 mark)
Define a collision in a hash table. (1 mark)
Describe how chaining resolves collisions. (2 marks)
State what a dictionary stores and how it is usually implemented. (2 marks)

Solutions

Q1: A static structure has a fixed size set at compile time with memory reserved in advance (an array); a dynamic structure can grow and shrink at run time using the heap (a linked list).
Q2: A stack is last-in first-out (LIFO); a queue is first-in first-out (FIFO).
Q3: A circular queue wraps its pointers with modulo arithmetic, so the slots freed by dequeuing are reused; a linear queue leaves those slots unusable and can report full while space remains.
Q4: For a sparse graph an adjacency list uses far less memory because it stores only the edges that exist, rather than an $O(n^2)$ matrix.
Q5: The stored values in ascending sorted order.
Q6: When two different keys are hashed to the same array index.
Q7: Each array index holds a pointer to a linked list, and any items that hash to that index are appended to the list at that position.
Q8: A dictionary stores key-value pairs with unique keys, and is usually implemented using a hash table so look-up by key is close to constant time.

Sources & how we know this

AQA A-level Computer Science (7517) specification — AQA (2015)