Data structures — AQA A-Level Computer Science

Data structures in AQA A-Level Computer Science provide systematic ways of organising, managing, and storing data to enable efficient access and modification. Master static vs dynamic allocations, abstract data types including stacks, queues, graphs, trees, hash tables, and dictionaries, alongside their practical implementations and algorithmic complexities.

Data structures explained

A data structure is a way of organising and storing data so that it can be accessed and modified efficiently for a particular purpose.

Read the full explanation

Being familiar with the concept means understanding that the same data can be held in different structures, and that the choice affects how easily data can be inserted, searched, sorted or retrieved. Common examples include arrays, which store items in a fixed-size sequence accessed by index; lists, which can grow and shrink; stacks, which follow last-in first-out order; queues, which follow first-in first-out order; and trees and graphs, which represent hierarchical or networked relationships. A learner should be able to recognise what kind of structure suits a given problem, such as a stack for reversing a sequence or a queue for scheduling tasks in arrival order.

Your focus

Be familiar with the concept of data structures.

Which command word is this?

Set out the causes, reasons, or inner workings of a structure or algorithm clearly. Marks are awarded for linked technical steps, not standalone definitions.

Data structures exam tips

Topic Overview

Data structures form the foundational architecture for managing and manipulating information inside computer systems. This unit covers basic primitive types, arrays, composite records, and abstract data types (ADTs) such as stacks, queues, linked lists, trees, graphs, and hash tables.

Understanding the mechanics, memory footprints, and access patterns of these structures is essential for designing efficient algorithms in Paper 1 and Paper 2. AQA requires students to distinguish between static and dynamic allocations and to trace operations on ADTs using both dry-run tables and formal pseudo-code.

Key Concepts

→Static vs Dynamic structures: Static structures (e.g., fixed-size arrays) have predetermined memory allocations at compile-time, while dynamic structures (e.g., linked lists, binary trees) allocate heap memory at runtime via pointers.
→LIFO vs FIFO protocols: Stacks operate under Last-In, First-Out using push/pop with a stack pointer; queues operate under First-In, First-Out using enqueue/dequeue with front/rear pointers.
→Non-linear ADTs: Graphs represent arbitrary pairwise relationships using adjacency matrices (dense) or adjacency lists (sparse); trees are connected, acyclic, directed/undirected graphs with unique paths between nodes.
→Collision handling in Hash Tables: Hashing transforms keys into indices; collisions are resolved using open addressing (linear probing) or closed addressing (chaining with linked lists).

Marking Points

States that a data structure organises data so it can be used efficiently.
Identifies the order or access rule that distinguishes at least two structures, such as LIFO for a stack and FIFO for a queue.
Explains that the choice of structure affects operations such as insertion, search and retrieval.
Matches a suitable structure to a described problem.

Examiner Tips

💡Learn the access rule for each common structure, since multiple-choice items often test this.
💡When matching a structure to a problem, identify the required order of processing first.
💡Keep the concept separate from any single programming language's implementation.
💡Always check edge conditions when tracing stacks or queues: verify stack overflow (top == max_size) or stack underflow (top == -1 or 0 depending on base index) before executing operations.
💡When drawing binary search trees after insertions, retain the canonical BST invariant: values strictly smaller go left, values strictly greater go right.
💡In pseudo-code questions, clearly show pointer movements before dereferencing or updating pointers to prevent dangling references and memory leaks.

Common Mistakes

Treats a data structure as only a variable type; correct it by explaining the organisation and access rules it provides.
Confuses stacks and queues; correct it by stating a stack is last-in first-out and a queue is first-in first-out.
Assumes one structure is always best; correct it by linking the choice to the operations the problem needs.
Assuming dynamic data structures are always superior to static data structures; dynamic structures incur pointer overheads (extra memory) and slower, non-contiguous access times due to cache misses.
Believing that an adjacency matrix is always better than an adjacency list; an adjacency matrix consumes O(V^2) memory regardless of edge count, making it wasteful for sparse graphs compared to adjacency lists.
Thinking that deleting a node from an array automatically shrinks its allocated memory size; arrays retain their fixed block unless explicitly reallocated by a higher-level abstraction.

Revision Plan

1Day 1-3: Review static vs dynamic memory; implement and trace stack and linear/circular queue operations using arrays and pointers.
2Day 4-6: Master linked lists (singly and doubly linked); write algorithms for node insertion, traversal, and deletion.
3Day 7-9: Study non-linear structures: Binary Search Trees (in-order, pre-order, post-order traversals) and Graphs (adjacency matrix vs list).
4Day 10-12: Practise hash tables, hashing functions, load factors, linear probing, and collision handling techniques.
5Day 13-14: Complete timed past-paper questions from AQA Paper 1 and Paper 2 covering pointer-based pseudo-code questions.

Exam Question Types

📋Algorithm trace tables: Step-by-step tracing of enqueue/dequeue, push/pop, or tree traversals tracking pointer states.
📋Pseudo-code implementation: Writing subroutines to traverse linked lists, add items to binary trees, or check queue states.
📋Compare and contrast essays: Evaluating trade-offs between adjacency matrices vs lists, or static arrays vs linked lists in specific contextual scenarios.

Command Word Expectations (AQA)

Explain

Set out the causes, reasons, or inner workings of a structure or algorithm clearly. Marks are awarded for linked technical steps, not standalone definitions.

Compare

Identify both similarities and differences between two data structures (e.g., array vs linked list), linking points back to memory usage, time complexity, or access mechanics.

Trace

Follow the execution of an algorithm dry-run line-by-line, updating index pointers, memory cell values, and conditional flags in a structured trace table.

How Students Lose Marks (Examiner Pitfalls)

Pitfall: Confusing the physical memory layout of dynamic data structures with their logical organisation, particularly claiming that linked lists require contiguous memory allocations like arrays.

❌ Weak Answer (Loses Marks):A linked list is dynamic so it can grow, whereas an array has a fixed size and stores items next to each other.

Example improved answer:An array is a static data structure occupying a contiguous block of memory allocated at compile time. Conversely, a linked list is a dynamic data structure where nodes containing data and memory pointers can be allocated non-contiguously in the heap at runtime, allowing the structure to grow or shrink without requiring memory reallocation or shifting elements.

Examiner Tip: Explicitly contrast compile-time vs runtime memory allocation and mention whether elements occupy contiguous memory addresses or rely on pointer references.

Pitfall: Mishandling circular queue pointer updates by forgetting the modulo arithmetic operation when wrapping pointers back to index 0.

❌ Weak Answer (Loses Marks):When rear reaches the end, you set rear back to the start if there is empty space.

Example improved answer:To update the rear pointer upon an enqueue operation in a circular queue of capacity max_size, use modulo arithmetic: rear = (rear + 1) MOD max_size. This wraps the index to 0 when rear reaches max_size - 1, provided the queue is not full.

Examiner Tip: Use the modulo operator ('MOD') in pseudo-code questions involving circular queues to guarantee credit for wrap-around boundary conditions.

Step-by-Step Worked Solutions

Question: A circular queue of capacity 5 is implemented using an array Q[0..4], with variables front = 0, rear = -1, and size = 0. Trace the values of front, rear, and size after the following operations: Enqueue('A'), Enqueue('B'), Dequeue(), Enqueue('C'), Enqueue('D'), Enqueue('E'), Enqueue('F'). Explain what happens on the final operation.

1.Step 1: Enqueue('A'): rear = ( -1 + 1 ) MOD 5 = 0; Q[0] = 'A'; size = 1.
2.Step 2: Enqueue('B'): rear = ( 0 + 1 ) MOD 5 = 1; Q[1] = 'B'; size = 2.
3.Step 3: Dequeue(): front = ( 0 + 1 ) MOD 5 = 1; size = 1 ('A' is removed logically).
4.Step 4: Enqueue('C'): rear = ( 1 + 1 ) MOD 5 = 2; Q[2] = 'C'; size = 2.
5.Step 5: Enqueue('D'): rear = ( 2 + 1 ) MOD 5 = 3; Q[3] = 'D'; size = 3.
6.Step 6: Enqueue('E'): rear = ( 3 + 1 ) MOD 5 = 4; Q[4] = 'E'; size = 4.
7.Step 7: Enqueue('F'): rear would be ( 4 + 1 ) MOD 5 = 0; Q[0] = 'F'; size = 5 (Queue is now full).
8.Step 8: Check boundary conditions: Array length is 5 and current size = 5. All items successfully enqueued because Dequeue opened index 0 for circular reuse.

Final Answer: Final state: front = 1, rear = 0, size = 5. Q contains ['F', 'B', 'C', 'D', 'E']. The final operation Enqueue('F') wraps to index 0 via modulo arithmetic without overflow because size < capacity before the call.

Question: Explain the process of inserting the value 17 into an existing Binary Search Tree (BST) with root 15, left child 8 (which has right child 12), and right child 23 (which has left child 19). Write down the comparison steps and the final pointer assignment.

1.Step 1: Compare 17 with root node 15. Because 17 > 15, traverse to the right subtree (node 23).
2.Step 2: Compare 17 with node 23. Because 17 < 23, traverse to the left subtree (node 19).
3.Step 3: Compare 17 with node 19. Because 17 < 19, examine the left pointer of node 19.
4.Step 4: Identify that the left child pointer of node 19 is null (empty).
5.Step 5: Allocate memory for a new node with key 17, and set node 19's left child pointer to reference this new node.

Final Answer: Comparisons: 17 > 15 (go right), 17 < 23 (go left), 17 < 19 (go left). The new node containing 17 is attached as the left child of node 19.

Active Recall Memory Test

What are the two pointer conditions that define an empty linear queue implemented via an array where front and rear start at 0 and -1?

Key Fact: A linear queue is empty when front > rear, or when size == 0.

State the tree traversal order that outputs keys from a Binary Search Tree in ascending numerical order.

Key Fact: In-order traversal (Left, Root, Right).

Which graph representation is most space-efficient for a sparse graph with V vertices and E edges?

Key Fact: An adjacency list, which consumes O(V + E) memory space compared to O(V^2) for an adjacency matrix.

What primary problem occurs in a linear queue that is resolved by implementing a circular queue?

Key Fact: The shuffle problem (or false overflow), where empty slots at the front left by dequeued items cannot be reused by incoming items.

Frequently Asked Questions

What is the difference between an abstract data type (ADT) and a data structure?

An Abstract Data Type (ADT) is a conceptual model that specifies what operations can be performed on data and how it behaves from the user perspective, without defining how it is implemented in memory (e.g., Stack, Queue, Map). A data structure is the concrete, physical implementation of that model in programming code and memory (e.g., implementing a stack using a 1D array or a singly linked list). In exams, ensure you do not conflate the interface of an ADT with its underlying storage medium.

Why is an adjacency matrix preferred over an adjacency list in some graph applications?

An adjacency matrix allows constant-time O(1) edge lookup between any two vertices by directly querying matrix[i][j]. It is also computationally faster and simpler to implement for dense graphs where the number of edges approaches V^2. Conversely, an adjacency list requires O(degree(V)) time to verify whether an edge exists, though it saves substantial memory when edges are sparse.

How does linear probing resolve collisions in a hash table?

When a calculated hash value maps to a bucket that is already occupied, linear probing searches sequentially through subsequent indices (index + 1, index + 2, ...) until an empty bucket is encountered. The item is then placed into that free location, wrapping back to the beginning of the array if the end is reached. However, excessive linear probing can lead to primary clustering, which degrades lookup performance towards O(n).

Why do dynamic data structures risk causing stack or heap overflow?

Dynamic data structures allocate storage at runtime from the system heap. If nodes are created continuously without deallocation, or if uncontrolled recursion exhausts call-stack frames, the process exhausts the finite virtual memory allotted by the operating system, resulting in an out-of-memory or stack overflow exception.

What is a dictionary data structure in AQA A-Level Computer Science?

A dictionary is an abstract data type consisting of an associative collection of key-value pairs, where each unique key maps to a specific value. Keys must be unique and hashable or comparable, allowing values to be retrieved, added, or deleted via their associated key. Under the hood, dictionaries are most frequently implemented using hash tables or self-balancing search trees to maintain average O(1) or O(log n) lookup operations.

Data structures explained

Your focus

Which command word is this?

Data structures exam tips

More AQA A-Level Computer Science topics

Cookies on MasteryMind