First exams 2027 · HL only

B4.1.2 · Fundamentals of ADTs

Evaluating linked lists

A linked list trades an array's fast lookup for fast insertion and deletion, by giving up contiguous storage in favour of a chain of pointers.

HL only Typically 3 marks · AO3 Command term: evaluate

Explainer

Think of a treasure hunt where each clue tells you where the next one is hidden. You can’t jump straight to clue 5; you have to follow the chain from clue 1, one step at a time. That’s a linked list: no shortcuts, just pointers leading to the next thing.

Df

A linked list is a chain of nodes. Each node holds a value and a pointer to the next node in the chain. The list itself only needs to remember one thing: the head, a pointer to the first node. Everything else is found by following pointers, one node at a time.

This is the opposite trade-off to an array. An array stores every element in one contiguous block, so jumping straight to element 50 is instant. A linked list scatters its nodes wherever there's free memory, so reaching the 50th node means following 50 pointers, one after another, from the head.

Array

Real example: a class register, seat by seat. The seating plan is fixed at the start of term, and you can jump straight to seat 27 without counting through the rest.

Advantage

  • O(1) access by index (jump straight to any position, no need to follow anything first)

Disadvantage

  • Fixed size (the size is set when created, growing past it means building a whole new, bigger array)
  • O(n) insertion or deletion (every element after the gap has to shift along to close or open the space)
Linked list

Real example: the treasure hunt above. Nothing is reserved in advance, each clue only exists once the previous one leads to it, and the hunt can grow by any number of clues without disturbing the ones already placed.

Advantage

  • Dynamic size (grows and shrinks freely, no space reserved upfront the way an array reserves its full size immediately)
  • O(1) insertion or deletion (once you're already at the right node, it's a single pointer reassignment, nothing shifts)

Disadvantage

  • O(n) access, sequential only (no index to jump to; reaching node 50 means following 50 pointers from the head, one at a time, so a binary search is impossible on a linked list, only a linear search works)
  • Extra memory per node (every node stores a pointer as well as its value, which adds up, and can risk running out of available memory at large scale)

Worked example

A chain of four nodes

Each node below stores a value and a pointer to the next node. The last node's pointer is None, which is how code recognises the end of the list.

Click a node to see what it points to.

→ → → → None

Amir.next points to Beth. That's the only way to reach Beth from the head: there's no shortcut, no index, just this one pointer.

?

What is node.next? It's not a value. It's a reference to another node object, the next one in the chain, or None if this is the last node. Writing node.next.value gets you the next node's value; node.next alone just gets you the next node itself.

# Node holds one value and a pointer to the next node
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

# Building Amir -> Beth -> Chen by hand, one pointer at a time
head = Node("Amir")
head.next = Node("Beth")
head.next.next = Node("Chen")

# Traversal: start at head, follow .next until it's None
current = head
while current is not None:
    print(current.value)
    current = current.next
// Node holds one value and a pointer to the next node
class Node {
    String value;
    Node next;
    Node(String value) {
        this.value = value;
        this.next = null;
    }
}

// Building Amir -> Beth -> Chen by hand, one pointer at a time
Node head = new Node("Amir");
head.next = new Node("Beth");
head.next.next = new Node("Chen");

// Traversal: start at head, follow .next until it's null
Node current = head;
while (current != null) {
    System.out.println(current.value);
    current = current.next;
}

The guide's current generator only produces Python. Java is shown here as a reference for schools teaching that track; both build the chain the same way, one pointer assignment at a time.

Check your understanding

Beth needs to be removed from the chain Amir → Beth → Chen → Dara. Which single change does that?

Common mistake

Markers reported this pattern for B4.1.2 / B4.1.3

RecurringMarkers reported candidates losing marks on insertion and deletion questions for describing the outcome in general terms without naming which pointer actually changes and what it now points to. A linear, value-based description ("search through the list to find Beth, then remove her") reads like an array explanation, not a linked-list one.

The stronger responses were consistently the ones written in terms of pointers: which node's next field is being read, checked, or reassigned, at every step.

✕

What a weak answer looks like: "Find Beth in the list and delete her." No pointer named, no node named as the one being changed.

✓

What it should say: "Traverse from head until the current node's next is Beth. Set that node's next to Beth's next, skipping Beth entirely." Names the pointer, names what it's set to.

Revision questions

Past-paper style. Write an answer, then reveal the marking points and mark yourself.

Question 1 · 1 mark

[1]State what a node's next pointer contains when that node is the last one in the list.

Question 2 · 3 marks

[3]Evaluate the use of a linked list, rather than an array, for a playlist that songs are frequently added to and removed from.

Question 3 · 4 marks

[4]Describe, in terms of pointers, the steps needed to insert a new node between Beth and Chen in the chain above.

Flashcards

Active recall for this statement's key terms.