Cambridge 9618 · International A Level Computer Science · ~15 min read
Notes
Video
Slides
Quiz
Worksheet
What is a Linked List?
A linked list is a dynamic data structure consisting of a sequence of nodes. Each node contains two parts:
Data field — stores the actual data value (integer, string, record, etc.)
Pointer field — stores the address (pointer) of the NEXT node in the list
Unlike arrays, linked list nodes are NOT stored in contiguous memory locations — they can be scattered anywhere in memory, held together only by the pointers. A special head pointer (also called start pointer) stores the address of the first node. The last node's pointer is set to NULL (or NIL) to indicate the end of the list.
Singly Linked List — Visual
HEAD → (points to node containing 10)
10
→
→
20
→
→
30
→
→
40
→
→NULL
Each node: [DATA | NEXT POINTER] — last node points to NULL
Doubly Linked List — Visual
A doubly linked list adds a second pointer to each node — a prev pointer pointing to the PREVIOUS node. This allows traversal in BOTH directions.
HEAD → A TAIL → C
NULL←
←
A
→
⇄
←
B
→
⇄
←
C
→
→NULL
Yellow ← = prev pointer | Blue → = next pointer | First prev = NULL | Last next = NULL
Node Structure in Cambridge 9618 Pseudocode
// Define a node using a record type TYPEListNode DECLAREData : INTEGER DECLARENextPointer : INTEGER// stores index of next node ENDTYPE
// Array-based linked list (static implementation) DECLARENodeList : ARRAY[1:10] OFListNode DECLAREHeadPointer : INTEGER// index of first node (0 = empty) DECLAREFreePointer : INTEGER// index of next available slot
Traversing a Linked List
// Start at head, follow pointers until NULL (0) CurrentPointer ← HeadPointer WHILECurrentPointer ≠ 0 OUTPUTNodeList[CurrentPointer].Data CurrentPointer ← NodeList[CurrentPointer].NextPointer ENDWHILE
Inserting a Node (at the Head)
1
Get a free node
NewNode ← FreePointer. Advance FreePointer to next free slot.
2
Set the data
NodeList[NewNode].Data ← value to insert.
3
Link new node → old head
NodeList[NewNode].NextPointer ← HeadPointer. The new node points to where head used to point.
4
Update head
HeadPointer ← NewNode. Head now points to the newly inserted node.
✓
Result
New node is now the head. Its next pointer leads to the old head. No items needed to shift.
!
Order matters!
ALWAYS link the new node to the list BEFORE updating HeadPointer — otherwise you lose the rest of the list.
Inserting a Node (in the Middle)
// Insert value after a given node (PrevPointer) NewNode ← FreePointer NodeList[NewNode].Data ← NewValue // New node → rest of list NodeList[NewNode].NextPointer ← NodeList[PrevPointer].NextPointer // Previous node → new node NodeList[PrevPointer].NextPointer ← NewNode
Deleting a Node
// Delete node at CurrentPointer (PrevPointer points to it) // Step 1: bypass the node to be deleted NodeList[PrevPointer].NextPointer ← NodeList[CurrentPointer].NextPointer // Step 2: return the freed slot to the free list NodeList[CurrentPointer].NextPointer ← FreePointer FreePointer ← CurrentPointer
Singly vs Doubly Linked List
Feature
Singly Linked
Doubly Linked
Pointers per node
1 (next only)
2 (next + prev)
Traversal
Forward only
Forward AND backward
Memory usage
Less (1 pointer per node)
More (2 pointers per node)
Delete node
Need previous node's pointer
Can delete with just current node
Insertion complexity
Simpler
More pointer updates needed
Advantages & Disadvantages vs Arrays
✅ Advantages of Linked Lists
• Dynamic size — grows and shrinks at runtime; no wasted pre-allocated space
• Efficient insertion/deletion — O(1) once position is found; no shifting of elements
• Memory efficient — allocates exactly what is needed
• Easy to implement queues/stacks dynamically
• Items don't need to be contiguous in memory
❌ Disadvantages of Linked Lists
• No random access — must traverse from head to reach element N; O(n) access
• Extra memory — each node stores a pointer in addition to data
• Cache inefficiency — nodes scattered in memory (poor cache locality vs arrays)
• More complex code — pointer manipulation is error-prone
• Cannot use binary search (requires random access)
Cambridge 9618 exam tip: In the array-based linked list implementation, two pointers are maintained: HeadPointer (index of the first data node) and FreePointer (index of the next available empty slot). Deletion returns the freed slot to the free list — NOT physical deletion from the array. When inserting, always update the new node's pointer BEFORE updating any existing pointer to it — otherwise you lose access to the rest of the list. Exam questions often ask you to trace through insert/delete operations showing pointer changes — draw a table tracking HeadPointer, FreePointer, and each node's Data and NextPointer columns.
⚠️ Common Mistakes
Wrong pointer update order during insertion — when inserting, set the new node's NextPointer FIRST (so it points to what comes after it), THEN update the previous node's NextPointer to point to the new node. Doing it the other way round loses the rest of the list.
Confusing HeadPointer and FreePointer — HeadPointer = first real data node; FreePointer = first empty/free slot available. They serve completely different purposes and must both be maintained correctly.
Not handling the empty list case — when the list is empty (HeadPointer = 0 or NULL), inserting at the head requires setting HeadPointer to the new node AND setting the new node's NextPointer to NULL. Don't forget the null pointer.
Thinking linked lists have O(1) access — they do NOT. To access element at position n, you must traverse n nodes from the head (O(n) time). Only insertion/deletion at a known position is O(1).
Forgetting to return freed nodes — when deleting a node, its slot must be added back to the free list (by updating its NextPointer to FreePointer and then updating FreePointer to point to it). Failing to do this creates a memory leak in the array implementation.
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 4.3.2 Linked Lists
8 questions · Cambridge 9618 standard
Q1Describe the structure of a node in a singly linked list. Explain the role of the head pointer and the NULL pointer.[4]
✅ Mark scheme
Each node has two fields: a DATA field storing the actual data value (integer, string, record, etc.) and a NEXT POINTER (NextPointer) field storing the memory address/index of the next node in the list [1]; the HEAD POINTER (HeadPointer) is a separate variable (not a node itself) that stores the address/index of the FIRST node in the list — it is the entry point used to access the list [1]; NULL (or 0 in array implementations) is stored in the NextPointer of the LAST node in the list — it indicates that there is no next node and the end of the list has been reached [1]; when the list is empty, HeadPointer = NULL/0 — there are no nodes [1].
Q2State two advantages and two disadvantages of linked lists compared to arrays.[4]
✅ Mark scheme
Advantage 1: dynamic size — linked lists grow/shrink at runtime; no need to declare a maximum size in advance; no wasted memory from unused pre-allocated slots [1]; Advantage 2: efficient insertion/deletion — once the position is found, inserting or deleting a node requires only a small number of pointer changes (O(1)); no need to shift other elements as with an array [1]; Disadvantage 1: no random access — to reach the nth element, all preceding nodes must be traversed from the head (O(n) access time); cannot use index-based access like arrays [1]; Disadvantage 2: extra memory overhead — each node stores a pointer in addition to the data; for small data items this pointer overhead can be significant; also poor cache locality (nodes scattered in memory) compared to arrays [1].
Q3Describe the steps to insert a new node at the HEAD of a linked list. State the critical rule about pointer update order and why it matters.[4]
✅ Mark scheme
Steps: (1) obtain a free node (NewNode ← FreePointer; advance FreePointer); (2) store the data value in the new node's Data field; (3) set NewNode's NextPointer to the CURRENT HeadPointer — so the new node points to what was previously the first node; (4) update HeadPointer to NewNode — the new node is now the head [1 per step, max 3]; critical rule: ALWAYS set the new node's NextPointer BEFORE updating HeadPointer [1]; reason: if HeadPointer is updated first to point to the new node, the address of the old first node is lost — there is no other reference to it, so the entire rest of the list becomes inaccessible (effectively a memory leak) [implied]. Award 4 marks total: 3 for correct steps + 1 for critical ordering rule.
Q4State two differences between a singly linked list and a doubly linked list. Give one advantage of a doubly linked list over a singly linked list.[3]
✅ Mark scheme
Difference 1: a singly linked list has ONE pointer per node (NextPointer only); a doubly linked list has TWO pointers per node (NextPointer AND PrevPointer) [1]; Difference 2: a singly linked list can only be traversed in ONE direction (forwards from head); a doubly linked list can be traversed in BOTH directions (forwards using NextPointer, backwards using PrevPointer) [1]; Advantage of doubly: when deleting a node, a doubly linked list can find the previous node directly via PrevPointer — in a singly linked list you must traverse from the head to find the predecessor node before deletion [1]. Also accept: implementing a deque/double-ended queue is easier with doubly linked list.
Q5In an array-based linked list implementation, a node is deleted. Explain what should happen to the freed node's array slot. Why is this important?[3]
✅ Mark scheme
The freed slot must be returned to the FREE LIST — this is done by: setting the deleted node's NextPointer to the current FreePointer value (linking it into the free list), then updating FreePointer to point to the newly freed slot [1]; this means the slot can now be reused by future insert operations [1]; importance: if freed slots are not returned to the free list, the FreePointer only ever advances — eventually all slots fill up even if most contain deleted (logically empty) nodes; returning slots prevents this and allows efficient reuse of array space [1].
Q6Write pseudocode to traverse a singly linked list and output every data value. State what the loop condition checks and why.[4]
✅ Mark scheme
CurrentPointer ← HeadPointer [1]; WHILE CurrentPointer ≠ 0 [or ≠ NULL] [1]; OUTPUT NodeList[CurrentPointer].Data [1]; CurrentPointer ← NodeList[CurrentPointer].NextPointer [1]; ENDWHILE. Loop condition: CurrentPointer ≠ 0 (or ≠ NULL) — checks whether the current node is the last in the list; the last node's NextPointer is always 0/NULL; when CurrentPointer becomes 0/NULL there are no more nodes to visit and the loop exits. Award 1 per correct line: initialisation + loop condition + OUTPUT + pointer advance.
Q7A singly linked list stores integers. HeadPointer = 3. The array Node contains: Node[1] = (10, 4), Node[2] = (30, -1), Node[3] = (5, 1), Node[4] = (20, 2), where each entry is (Data, NextPointer) and -1 means null. List the integers in linked list order. Then state the steps required to delete the node containing 20 from the list.[5]
✅ Mark scheme
Follow pointers: start Node[3]=5 → Node[1]=10 → Node[4]=20 → Node[2]=30 → null; order: 5, 10, 20, 30 [1]; To delete 20 (Node[4]): traverse to find node before 20, which is Node[1] (data=10) [1]; set Node[1].NextPointer = Node[4].NextPointer = 2 [1]; Node[4] is now disconnected from the list [1]; Node[4] should be added to the free list for reuse [1].
Q8Give two advantages of a linked list over an array for storing an ordered collection of data. Explain why insertion into a linked list does not require shifting other elements, with reference to pointers.[4]
✅ Mark scheme
Advantage 1: dynamic size — linked list grows and shrinks at runtime without pre-allocating a fixed block of memory [1]; Advantage 2: insertion and deletion are O(1) once the position is found — no elements need to be shifted [1]; Insertion: to insert between node A and node B, create a new node, set its NextPointer to B's address, then update A's NextPointer to point to the new node [1]; only two pointer values change regardless of list length, so no shifting is needed [1].
Topic Quiz
Question 1 of 10
You scored
out of 10
Card 1 of 8
Click to reveal definition
🎉
All cards reviewed!
Term
Definition
🎯
Mini Test — 4.3.2 Linked Lists
10 questions · 10 marks · 10 minutes
⏱ 10:00
Section A — Multiple Choice [5 marks]
Q1What does a node in a singly linked list contain?
Q2What does the NULL pointer in the last node of a linked list indicate?
Q3When inserting a new node at the head of a linked list, in what order should pointers be updated?
Q4What is the time complexity of accessing the nth element in a linked list?
Q5How does a doubly linked list differ from a singly linked list?
Section B — Short Answer [5 marks]
Q6Write pseudocode to traverse a linked list and count how many nodes contain a value greater than 50. Assume NodeList array with HeadPointer and each node has Data and NextPointer fields. Return the count.
Mark schemeFUNCTION CountAbove50() RETURNS INTEGER; count ← 0 [1]; CurrentPointer ← HeadPointer [1]; WHILE CurrentPointer ≠ 0 [1]; IF NodeList[CurrentPointer].Data > 50 THEN count ← count + 1; ENDIF [1]; CurrentPointer ← NodeList[CurrentPointer].NextPointer [1]; ENDWHILE; RETURN count; ENDFUNCTION. Award 1 per: initialise count, start at head, correct loop condition, correct comparison, advance pointer. Full 5 marks for complete correct solution.
Q7Explain what happens to the FreePointer when a node is deleted from an array-based linked list. Why must this step not be omitted?
Mark schemeWhen a node is deleted: its array slot is returned to the free list by: (1) setting the deleted node's NextPointer ← FreePointer (linking it into the free list chain), then (2) setting FreePointer ← deleted node's index [1]; this must not be omitted because: if freed slots are not returned, the FreePointer only ever increments forward through the array; when it reaches the end, no more insertions are possible even though many deleted (logically empty) slots exist in the middle — effectively a memory leak [1]; returning freed slots means future INSERT operations can reuse those slots, preventing premature "full" conditions [1].
Q8State the steps to insert a new node with value 25 between two existing nodes (PrevNode and NextNode) in a singly linked list.
Mark scheme(1) NewNode ← FreePointer; advance FreePointer to next free slot [1]; (2) NodeList[NewNode].Data ← 25 [1]; (3) NodeList[NewNode].NextPointer ← NodeList[PrevNode].NextPointer [— the new node points to what comes after PrevNode] [1]; (4) NodeList[PrevNode].NextPointer ← NewNode [— PrevNode now points to the new node] [1]. Critical: step 3 MUST come before step 4 — if step 4 is done first, the address of NextNode is overwritten and permanently lost [1]. Award 4 marks for steps in correct order + 1 mark for explaining critical ordering requirement.
Q9Explain why a linked list cannot use binary search, even if all its data is stored in sorted order.
Mark schemeBinary search requires RANDOM ACCESS — the ability to jump directly to any element by its index in O(1) time (e.g. the middle element of a 100-element list) [1]; linked lists do NOT support random access — to reach the nth node, all n-1 preceding nodes must be traversed from the head sequentially (O(n) time) [1]; binary search relies on repeatedly halving the search space by jumping to the middle; this "jump" is not possible with a linked list since there is no way to compute and directly access the middle node without traversal [1]; therefore even if the data is sorted, binary search cannot be applied efficiently — linear search must be used instead.
Q10Compare linked lists and arrays in terms of: (a) memory allocation, (b) insertion efficiency, and (c) access speed.
Mark scheme(a) Memory allocation: arrays are statically allocated — a fixed maximum size is declared upfront; unused slots waste memory. Linked lists are dynamically allocated — memory is requested only when a new node is needed; no wasted space [1]; (b) Insertion efficiency: in an array, inserting in the middle requires shifting all subsequent elements (O(n)). In a linked list, once the insertion position is found, only a small number of pointer changes are needed regardless of list size (O(1)) [1]; (c) Access speed: arrays support O(1) random access by index — direct calculation of memory address. Linked lists require sequential traversal from the head (O(n)) — no index calculation is possible [1].