What is the difference between a stack and a queue?

A stack follows Last In, First Out (LIFO) – the last item added is the first removed, like a pile of plates. A queue follows First In, First Out (FIFO) – the first item added is the first removed, like a line at a supermarket till. Stacks are used for undo operations and function calls; queues are used for task scheduling and breadth-first search.

How do you traverse a binary tree in pre-order?

Pre-order traversal visits the root node first, then recursively traverses the left subtree, and finally the right subtree. The order is: root, left, right. For example, for a tree with root A, left child B, right child C, pre-order gives A, B, C. This is useful for copying a tree or evaluating prefix expressions.

What is a hash table and how does it work?

A hash table is a data structure that maps keys to values using a hash function. The hash function computes an index into an array of buckets, where the value is stored. Ideally, each key maps to a unique index, but collisions (two keys mapping to the same index) can occur. Collisions are resolved using techniques like chaining (linked list at each bucket) or open addressing (probing for the next empty slot). Hash tables offer average O(1) lookup, insertion, and deletion.

When should I use a linked list instead of an array?

Use a linked list when you need frequent insertions and deletions at arbitrary positions, especially at the beginning or middle, because these operations are O(1) if you have a pointer to the node. Arrays are better for random access (O(1) indexing) and when memory locality is important. Also, linked lists use more memory per element due to storing pointers.

What is the difference between a tree and a graph?

A tree is a special type of graph that is connected and acyclic (no cycles). Trees have a hierarchical structure with a root node and parent-child relationships. Graphs can have cycles, multiple connections, and no root. Trees are used for hierarchical data (file systems, HTML DOM), while graphs model networks (social networks, maps).

How do I choose the right data structure for an exam question?

First, identify the operations needed (e.g., frequent insertions, fast search, order preservation). Then consider constraints like memory or time. For example, if you need fast search and order doesn't matter, a hash table is good. If you need to maintain sorted order, use a binary search tree or a sorted array. Always justify your choice by linking the structure's properties to the problem's requirements.

Fundamentals of data structures

AQA

A-Level

This topic covers the fundamental principles of data structures, focusing on how data is organized and stored for efficient access and manipulation. It includes the study of arrays, records, and files, as well as more complex abstract data types like queues, stacks, graphs, trees, hash tables, dictionaries, and vectors.

Objectives

Exam Tips

Pitfalls

Key Terms

Mark Points

Topic Overview

Data structures are fundamental building blocks in computer science, providing organised ways to store, manage, and retrieve data efficiently. In the AQA A-Level Computer Science specification, you'll explore static and dynamic structures, including arrays, records, lists, tuples, stacks, queues, trees, graphs, and hash tables. Understanding these structures is crucial because they directly impact algorithm performance and memory usage—choosing the wrong structure can make a program slow or even unworkable.

This topic builds on your GCSE knowledge of simple arrays and lists, extending into more complex structures like binary trees and graphs. You'll learn not only how each structure works but also when to apply them, such as using a stack for expression evaluation or a queue for breadth-first search. Mastery of data structures is essential for tackling algorithms, databases, and even object-oriented programming, as many real-world systems rely on efficient data organisation.

By the end of this topic, you should be able to implement key operations (insertion, deletion, traversal) for each structure, analyse their time and space complexity, and justify your choices in exam questions. This knowledge forms the backbone of problem-solving in computer science, from operating systems to artificial intelligence.

Key Concepts

Core ideas you must understand for this topic

→Static vs dynamic structures: Static structures (e.g., arrays) have fixed size, while dynamic structures (e.g., linked lists) can grow/shrink at runtime.
→Abstract Data Types (ADTs): Stacks (LIFO), queues (FIFO), trees (hierarchical), graphs (networked) – understand their properties and typical operations.
→Traversal algorithms: For trees (pre-order, in-order, post-order) and graphs (depth-first, breadth-first) – know the order and use cases.
→Hash tables and collision resolution: How hashing works, handling collisions via chaining or open addressing (linear probing, quadratic probing).
→Complexity analysis: Big O notation for insertion, deletion, search, and traversal of each structure (e.g., O(1) for stack push/pop, O(n) for array search).

What You Need to Demonstrate

Key skills and knowledge for this topic

Correct identification and application of data structures to solve problems.
Ability to distinguish between static and dynamic data structures.
Correct implementation of operations for queues (linear, circular, priority) and stacks (push, pop, peek).
Understanding of graph representations (adjacency matrix vs adjacency list) and tree traversal methods (pre-order, post-order, in-order).
Application of hashing algorithms and collision handling via rehashing.
Understanding of vector operations including addition, scalar multiplication, and dot products.

Marking Points

Key points examiners look for in your answers

Correct identification and application of data structures to solve problems.
Ability to distinguish between static and dynamic data structures.
Correct implementation of operations for queues (linear, circular, priority) and stacks (push, pop, peek).
Understanding of graph representations (adjacency matrix vs adjacency list) and tree traversal methods (pre-order, post-order, in-order).
Application of hashing algorithms and collision handling via rehashing.
Understanding of vector operations including addition, scalar multiplication, and dot products.

Examiner Tips

Expert advice for maximising your marks

💡Practice tracing algorithms for stack and queue operations to ensure you understand the state changes.
💡Be prepared to draw and interpret diagrams for graphs and trees.
💡Ensure you can explain the advantages and disadvantages of different data structures for specific scenarios.
💡Memorize the standard operations for each abstract data type (e.g., push/pop for stacks, enqueue/dequeue for queues).
💡Use clear, annotated diagrams when explaining graph or tree traversals.
💡Always draw diagrams when answering questions about data structures. A clear sketch of a stack pushing/popping or a tree traversal can earn method marks even if your explanation is slightly off.
💡When comparing structures, explicitly mention time complexity for key operations (e.g., 'Array insertion at the front is O(n) because elements must shift, whereas linked list insertion is O(1) if you have a pointer').
💡For algorithm questions, state which data structure you would use and justify it with two reasons – one about efficiency and one about the nature of the problem (e.g., 'I would use a queue because it processes tasks in the order they arrive, and enqueue/dequeue are O(1)').

Common Mistakes

Pitfalls to avoid in your exam answers

Confusing the properties of static and dynamic data structures.
Incorrectly implementing circular queue logic, particularly handling the wrap-around.
Failing to distinguish between different graph traversal algorithms and their specific applications.
Misunderstanding the difference between an adjacency matrix and an adjacency list in terms of space and time complexity.
Errors in calculating the dot product of vectors or applying vector operations in the wrong context.
Misconception: 'A stack and a queue are the same thing.' Correction: Stacks are LIFO (Last In, First Out) – like a pile of plates; queues are FIFO (First In, First Out) – like a line at a till.
Misconception: 'Binary trees are always sorted.' Correction: Not all binary trees are binary search trees (BSTs). A BST has the property that left child < parent < right child, but a general binary tree has no such ordering.
Misconception: 'Hash tables guarantee O(1) lookup.' Correction: In the worst case (many collisions), lookup can degrade to O(n). Good hash functions and load factor management are essential.

Frequently Asked Questions

Common questions students ask about this topic

Before You Start

Prior knowledge that will help with this topic

•Basic programming concepts: variables, loops, conditionals, and functions (preferably in Python or pseudocode).
•Understanding of arrays and lists from GCSE Computer Science.
•Familiarity with Big O notation and algorithm efficiency (covered earlier in the A-Level course).

Likely Command Words

How questions on this topic are typically asked

Describe

Explain

Compare

Trace

Construct

Apply

Ready to test yourself?

Practice questions tailored to this topic

Fundamentals of data structures

Topic Overview

Key Concepts

What You Need to Demonstrate

Marking Points

Examiner Tips

Common Mistakes

Frequently Asked Questions

Before You Start

Likely Command Words

Ready to test yourself?

Related Topics in AQA A-Level Computer Science

Big Data

Consequences of uses of computing

Fundamentals of algorithms

Fundamentals of communication and networking

Topic Synopsis

Key Concepts & Core Principles

Exam Tips & Revision Strategies

Common Misconceptions & Mistakes to Avoid

Examiner Marking Points

Fundamentals of data structures

Topic Overview

Key Concepts

What You Need to Demonstrate

Marking Points

Examiner Tips

Common Mistakes

Frequently Asked Questions

What is the difference between a stack and a queue?

How do you traverse a binary tree in pre-order?

What is a hash table and how does it work?

When should I use a linked list instead of an array?

What is the difference between a tree and a graph?

How do I choose the right data structure for an exam question?

Before You Start

Likely Command Words

Ready to test yourself?

Related Topics in AQA A-Level Computer Science

Big Data

Consequences of uses of computing

Fundamentals of algorithms

Fundamentals of communication and networking