Lesson 8.2 · Linked Lists

The Dummy Head

A fake node before the real head means the first node is never a special case when building, inserting or deleting.

10 min

Think of it like this

A bookend at the start of a shelf: you always have something to lean the first book against, so adding or removing the first book works exactly like any other book.

1.Why the head is special without it

Deleting the first node changes head itself; deleting any other node changes a previous node's next. Two code paths, twice the bugs. With dummy.next = head, every real node has a predecessor, so one code path handles everything. Return dummy.next at the end.

Main.java

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Main {
    // remove every node with value v, including at the head
    static ListNode removeAll(ListNode head, int v) {
        ListNode dummy = new ListNode(0, head), prev = dummy;
        while (prev.next != null) {
            if (prev.next.val == v) prev.next = prev.next.next;   // skip it
            else prev = prev.next;
        }
        return dummy.next;
    }
    public static void main(String[] args) {
        ListNode head = new ListNode(6, new ListNode(6, new ListNode(1, new ListNode(6, new ListNode(2)))));
        for (ListNode n = removeAll(head, 6); n != null; n = n.next) System.out.print(n.val + " ");
    }
}

Output

1 2

Quick check

In removeAll, why don't we move prev forward after removing a node?

Remember

dummy.next = head; work with prev pointers; return dummy.next.
Removes all special cases for the head.
Also the standard way to build a new list (tail pointer from the dummy).

Common mistakes

Returning dummy instead of dummy.next.
Returning the old head after it may have been deleted.

Command Palette

The Dummy Head

1.Why the head is special without it