First exams 2027 · HL only

B4.1.3 · Fundamentals of ADTs

Singly and doubly linked lists

A doubly linked list is a singly linked list that also remembers where it came from, at the cost of a second pointer on every node.

HL only Typically 4–5 marks · AO3 Command term: construct, apply

Explainer

Think of a phone book you can only flip forward through, never back, versus one where every page also says what page you just came from. Both let you read the entries in order; only the second lets you retrace your steps without starting over.

Df

A singly linked list node stores a value and one pointer, next. You can only travel forward through it, head to tail. A doubly linked list node stores a value and two pointers, next AND prev, so you can travel in either direction from any node.

That second pointer is not free. Every insertion or deletion in a doubly linked list has to keep both directions consistent: the new node's own next and prev, plus the next of the node before it and the prev of the node after it. Miss one, and the list still looks fine walking forward, but breaks walking backward.

"State one advantage and one disadvantage of using a doubly linked list instead of a singly linked list" is one of the most reliably asked questions on this statement. The mark scheme awards one mark for naming the advantage or disadvantage, and a second mark for expanding on why, so both parts matter. This is also B4's own guiding question in miniature, which ADT is most appropriate for a given situation: the two real examples below are exactly how that question gets answered, by matching a structure's trade-offs to what a specific situation actually needs.

Singly linked list

Real example: a simple undo button with no redo, like closing a dialog box. You only ever need to step backward through history once, never forward again, so one pointer per step is enough.

Advantage

  • Uses less memory per node (only one pointer to store and update, not two)

Disadvantage

  • Cannot traverse backward (finding "the node before X" means restarting from head and counting forward)
Doubly linked list

Real example: a music player's next/previous buttons, or a web browser's back/forward history. Both directions are needed equally often, so every node needs to know its neighbour on both sides.

Advantage

  • Can traverse both directions (supports "previous track" as easily as "next track", with no restart needed)

Disadvantage

  • Uses more memory per node, and every insertion or deletion has more pointers to keep correct (miss one, and only one direction of traversal breaks)

Worked example

A doubly linked chain of three nodes

Each node below stores a value and two pointers. The head node's prev is None; the tail node's next is None. Every node in between points both ways.

Click a node to see both of its pointers.

None
→←
→←
→←
→←
None
next: the forward pointer prev: the backward pointer

Beth.next points to Chen, and Beth.prev points to Amir. Both pointers exist on every middle node, and both have to stay correct at once.

?

What is node.prev? The mirror of node.next: a reference to the node before this one in the chain, or None if this is the head. A singly linked list has no way to answer "what comes before this node?" without starting over from the head and counting. A doubly linked list just reads node.prev.

# Node now holds a value, plus a pointer BOTH ways
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.prev = None

# Inserting Beth between Amir and Chen: FOUR pointers change
new_node = Node("Beth")
new_node.next = chen
new_node.prev = amir
amir.next = new_node
chen.prev = new_node
// Node now holds a value, plus a pointer BOTH ways
class Node {
    String value;
    Node next;
    Node prev;
    Node(String value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

// Inserting Beth between Amir and Chen: FOUR pointers change
Node newNode = new Node("Beth");
newNode.next = chen;
newNode.prev = amir;
amir.next = newNode;
chen.prev = newNode;

Compare this to a singly linked list insertion, which only ever changes two pointers. Doubly linked lists always update in pairs.

Click through: inserting a new node so the list stays sorted

This is the step markers reported candidates struggling with most: not the insertion itself, but correctly finding where to insert. Watch Beau get inserted into Amir ↔ Beth ↔ Chen, in alphabetical order, one atomic step at a time.

None
→←
Amirprevnext
→←
Beauprevnext
→←
→←
Bethprevnext
→←
Chenprevnext
→←
None

Beau needs to be inserted in sorted order. Compare it against the list, starting from the head.

Step 1 of 6

Notice step 4: Beau's own pointers are set FIRST, before either neighbour knows about it. Only after that do Amir and Beth get updated, one at a time, same order every time.

Check your understanding

Inserting a new node between two existing nodes in a doubly linked list requires updating how many pointers in total?

Common mistake

Markers reported this pattern for B4.1.3

RecurringMarkers reported real difficulty on questions asking candidates to insert a new node into a linked list while keeping it in sorted order, rather than just at the head or tail. The hard part isn't the insertion itself, it's correctly finding where to insert: comparing the new value against each node in turn until the right position is found, then only inserting.

Markers also noted that answers written as a numbered sequence of algorithmic steps scored consistently higher than answers written as a single descriptive paragraph, even when both described the same idea.

✕

What a weak answer looks like: "Insert the new customer into the linked list in the correct alphabetical position." Restates the goal, describes no method for finding that position.

✓

What it should say: "Starting at head, compare the new name to each node's name in turn. Stop at the first node whose name comes after the new one. Insert the new node immediately before that node, updating its next and prev, and the next of the node before it." A method, not just a goal.

Worked example

Circular linked lists

Take a singly linked list and change exactly one pointer: instead of the last node's next sitting empty at None, aim it at the head and nowhere else. That single change removes the concept of an "end" from the structure entirely, a circular linked list is a loop, not a line.

Think of a group passing a ball around a circle: whoever has it just passes to the next person, and eventually it comes back to whoever started, with no "last" person who keeps it.

Click a node to see where its next pointer goes.

→ →

Amir.next points to Beth. Keep following .next from any node and you visit every node forever, Amir, Beth, Chen, Amir, Beth, Chen…, never reaching None.

!

The gotcha a circular list creates: the usual traversal loop, while current is not None, never stops on a circular list, because None never appears. It has to check against the head instead, and only after the first step, or it would stop immediately at the start.

# Last node's next points back to head, not None
tail.next = head

# Traversal must check against head, not None, or it never stops
current = head.next
while current is not head:
    print(current.value)
    current = current.next
// Last node's next points back to head, not null
tail.next = head;

// Traversal must check against head, not null, or it never stops
Node current = head.next;
while (current != head) {
    System.out.println(current.value);
    current = current.next;
}

Real applications lean on exactly this looping property: round-robin CPU scheduling (give every process a turn, then start again), or a music player set to repeat a playlist.

Combining both: a doubly circular linked list

Nothing stops the two variants above from being combined: every node keeps its prev AND next (doubly), and BOTH ends wrap around instead of pointing to None (circular). This is exactly the kind of combination B4's guiding question is really asking about, which ADT is most appropriate for a given situation often means combining traits, not just picking one named type off a list.

Click a node to see both of its pointers, including the wrap-around ones.

→←
→←
next: the forward pointer prev: the backward pointer

Amir.next points to Beth, and Amir.prev points to Chen, the wrap-around backward pointer. Every node has both directions, and both directions wrap.

# Both wrap-around pointers set, not just one
tail.next = head
head.prev = tail

# Forward traversal wraps on next, exactly like the singly circular version
current = head.next
while current is not head:
    print(current.value)
    current = current.next

# Backward traversal is now possible too, starting from the tail
current = tail
while current is not head:
    print(current.value)
    current = current.prev
// Both wrap-around pointers set, not just one
tail.next = head;
head.prev = tail;

// Forward traversal wraps on next, exactly like the singly circular version
Node current = head.next;
while (current != head) {
    System.out.println(current.value);
    current = current.next;
}

// Backward traversal is now possible too, starting from the tail
current = tail;
while (current != head) {
    System.out.println(current.value);
    current = current.prev;
}

Two extra lines over a plain circular list (head.prev = tail), but they buy a real capability: traversing backward from any point without ever restarting from the head.

Revision questions

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

Question 1 · 2 marks

[2]State two consequences of using a doubly linked list instead of a singly linked list.

Question 2 · 5 marks

[5]Describe, in algorithmic steps, how to insert a new node into a doubly linked list so that it stays sorted by value.

Question 3 · 3 marks

[3]A programmer updates a node's next pointer during an insertion but forgets to update the following node's prev pointer. Explain the effect this has.

Flashcards

Active recall for this statement's key terms.