SLIDE 1 / 10
CSZone.co.uk
Click anywhere to advance · Arrow keys also work
AQA 7517 · Paper 1 · 4.2.3

Linked
Lists

AQA A-Level Computer Science · Section 4.2 Fundamentals of Data Structures

WHAT YOU'LL LEARN
Node structure · Singly & doubly linked · Add/delete/traverse operations
AQA SPEC LINK
4.2.3 — Linked lists as dynamic data structures
Node Structure

Anatomy of a Linked List

A linked list is a dynamic data structure where each element (node) stores:
1. Data — the value stored
2. Pointer/Next — memory address of the next node
Alice
→
→
Bob
→
→
Carol
→
→
NULL
∅
Head pointer → first node; last node points to NULL (end of list)
Singly vs Doubly

Types of Linked Lists

SINGLY LINKED
Each node has one pointer: next. Can only traverse forwards.
A → B → C → NULL
DOUBLY LINKED
Each node has two pointers: next and prev. Can traverse forwards and backwards.
NULL ← A ↔ B ↔ C → NULL
Doubly linked lists use more memory (extra pointer per node) but enable bidirectional traversal — used in browser history, undo/redo.
Adding a Node

Inserting into a Linked List

INSERTING "Dave" AFTER "Bob"
Before: A → Bob → Carol → NULL
1. Create new node "Dave"
2. Set Dave's next pointer to Carol
3. Update Bob's next pointer to Dave
After: A → Bob → Dave → Carol → NULL
Key advantage over arrays: inserting into a linked list is O(1) once you have the correct position — no shifting of elements needed.
Deleting a Node

Removing from a Linked List

DELETING "Bob" FROM A → Bob → Carol
1. Find node before Bob (node A)
2. Update A's next pointer to Bob's next (Carol)
3. Bob is now unreferenced — memory can be freed
After: A → Carol → NULL
⚠️ You cannot directly access the node before a target in a singly linked list — you must traverse from the head.
Traversal

Traversing a Linked List

current ← head
WHILE current ≠ NULL
  OUTPUT current.data
  current ← current.next
ENDWHILE
Traversal is O(n) — must visit each node sequentially. Unlike arrays, linked lists do not support random access — you cannot jump directly to index i.
Linked List vs Array

When to Use Each

FeatureArrayLinked List
SizeFixed (static)Dynamic
Random accessO(1) by indexO(n) — must traverse
Insert/DeleteO(n) — shift elementsO(1) with pointer
MemoryContiguous blockScattered + pointer overhead
Best forFixed size, fast lookupFrequent insertions/deletions
Applications

Real-World Uses

Browser history — doubly linked list (back/forward navigation)
Music playlists — singly linked (next track) or doubly (prev/next)
Undo/redo — doubly linked list of actions
OS scheduling — ready queue of processes as linked list
Memory allocation — free block list in heap management
AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style
A singly linked list stores the names: Alice → Carol → Dave → NULL. The name "Bob" needs to be inserted between Alice and Carol.

Describe the steps needed to insert "Bob" correctly.
[3 marks]
1 mark
Create a new node containing "Bob"
1 mark
Set Bob's next pointer to point to Carol
1 mark
Update Alice's next pointer to point to Bob
Summary

Key Points to Remember

Node = data + pointer to next node; last node points to NULL
Singly — one direction; Doubly — next AND prev pointers
Insert/delete — O(1) with pointer; Traverse — O(n) sequential
No random access — cannot do list[3] directly
Dynamic size — grows/shrinks as nodes are added/removed
🎉 Lesson complete — move to the quiz!