Sentinels, Dummy Heads & Tail Pointers

July 2026 · 20 min read

The previous post ended on a nagging asymmetry: every deletion had a special prev == nullptr branch for the head. That branch is not an accident of one algorithm — it is a symptom of a design choice. A naked head pointer treats the first node differently from every other node, and the cost is paid in edge cases scattered through your code. This post shows three ways to make that asymmetry disappear: a dummy head node, the pointer-to-pointer idiom, and a tail pointer for the other end.

The Edge Cases a Naked Head Creates

A raw Node* head is the leanest possible list — one pointer of state — and it makes exactly one node special: the first one. The first node is the only node not pointed at by some other node's next; it is pointed at by head, a variable that lives outside every node. Any operation that touches the boundary between “outside” and “inside” needs a branch. Four situations force one:

• The empty list. head == nullptr. Any code that dereferences head without checking first is an immediate crash.
• Deleting the head. There is no predecessor to rewire, so you must assign to head itself, not to some prev->next.
• Inserting before the head. A new first node means head changes — again a write to the outside variable, not to a node field.
• The single-element list. The one node is simultaneously first and last, so head-logic and tail-logic collide on the same node.

Every one of these is the same underlying problem: the head link does not live inside a node, so code that manipulates links has to special-case it. Fix that one fact and all four edge cases dissolve together.

The Dummy Head Node

Introduce a single extra node — a dummy (or sentinel) — that sits before the first real element and whose value is never read. Now the “head link” is dummy.next, which is a node field, so it can be rewired by exactly the same code that rewires any interior link. The real head is always dummy.next; you read it back at the end.

Node* remove_all(Node* head, int v) {
    Node dummy(0);            // value ignored; lives on the stack
    dummy.next = head;        // splice the real list behind the dummy
    Node* prev = &dummy;      // prev is NEVER null now

    while (prev->next != nullptr) {
        if (prev->next->val == v) {
            Node* victim = prev->next;
            prev->next = victim->next;   // the one-and-only unlink line
            delete victim;
        } else {
            prev = prev->next;
        }
    }
    return dummy.next;        // the head may have changed \u2014 read it back
}

Compare this with the naked-head version from the previous post: the if (prev == nullptr) head = cur->next; branch is gone. Deleting the first real node is now identical to deleting the fifth, because the first real node has a genuine predecessor — the dummy. The return dummy.next idiom is the standard way to write any function that might change the head: build a dummy, work through it uniformly, and hand back dummy.next.

Watch the Special Case Vanish

The same operation — delete the first real node A — on two lists. The naked head (top) must branch to reassign the head pointer; the dummy head (bottom) reaches A through dummy and deletes it with the ordinary interior-node line. Step through and watch the red branch box appear only on top.

The Pointer-to-Pointer Idiom

There is an even sharper tool that needs no extra node at all. The insight: instead of trailing a prev node, trail a pointer to the link that points at the current node. Call it pp, of type Node**. Initially pp = &head — the address of the head variable itself, because head is the link that points at the first node. Thereafter pp = &entry->next.

Node* remove_all(Node* head, int v) {
    Node** pp = &head;              // pp points AT the link that names the node
    while (*pp != nullptr) {
        Node* entry = *pp;
        if (entry->val == v) {
            *pp = entry->next;      // rewrite that link to skip 'entry'
            delete entry;
        } else {
            pp = &entry->next;      // advance to the next link slot
        }
    }
    return head;
}

Trace why the head case disappears. When the first node matches, pp still equals &head, so *pp = entry->next writes directly through head — the head update happens with the same statement that updates any interior link. There is no dummy, no branch, and the whole routine is six lines. The head variable is treated as just another link slot, which is exactly what it is.

Here is remove_all(head, 4) on head → 4 → 7 → 4 → 9. Watch pp point at a link (never at a node), and note that deleting the head in step 0 uses the identical *pp = entry->next as the interior delete in step 2:

After a match pp deliberately does not advance — the link it names now points at a new node that must itself be tested (crucial when duplicates are adjacent, as with the two 4s). After a non-match it steps forward to the next link slot. That is the entire control flow, head and interior handled by one line each.

The Tail Pointer

Dummies and pointer-to-pointer fix the front. The back has its own problem: push_back on a naked list is O(n) because the last node is only reachable by walking. Cache a tail pointer and appends become O(1) — but now you own a second invariant, and every structural change must maintain it.

struct List {
    Node* head = nullptr;
    Node* tail = nullptr;   // last node, or nullptr when empty

    void push_back(int v) {
        Node* n = new Node(v);
        if (head == nullptr) head = tail = n;   // empty: both change
        else { tail->next = n; tail = n; }       // link, then advance tail
    }
};

The tail invariant — “tail is the last node, or null iff the list is empty” — must be re-established in four distinct places, and each omission is a real bug:

That last row is the sting: in a singly linked list, fixing tail after erasing the last node costs O(n), because you must walk from head to find the new predecessor-of-null. So a tail pointer gives O(1) push_back but not O(1) pop_back — only a doubly linked list gets both. This asymmetry is precisely why std::forward_list has no push_back at all: it stores only a head to stay one pointer wide, and the library refuses to ship an operation that looks O(1) but is O(n), or to pay for a tail pointer most callers would not use.

insert_after, erase_after, and the Library's Choice

A forward iterator into a singly linked list can reach the node it names and everything after it — but never the node before it. So a conventional insert(pos, x) (“insert before pos”) is impossible in O(1): you would need pos's predecessor, which the iterator cannot supply. The standard library resolves this honestly by shifting the whole API one slot forward:

#include <forward_list>

std::forward_list<int> fl = {1, 2, 3};
auto it = fl.before_begin();      // a real iterator to the slot BEFORE the first
fl.insert_after(it, 0);           // O(1): now 0, 1, 2, 3
fl.erase_after(fl.begin());       // O(1): removes the 2 -> 0, 1, 3

before_begin() is the dummy head, promoted to a first-class API concept: it is an iterator to a notional node before the first element, so that inserting after it inserts at the front — uniformly, with no head special case. Every mutating operation comes in an _after flavour: insert_after, emplace_after, erase_after, splice_after. The lesson is that the dummy-head trick is not a hack; it is load-bearing enough that the standard library built its entire singly-linked container around it.

Four Designs Compared

These are not mutually exclusive: production lists combine a sentinel for the front edge cases with a tail (or a circular sentinel that is the tail) for O(1) append. That combination — one sentinel node that is both before-the-first and after-the-last — is the layout the doubly linked list uses, and it makes almost every operation branch-free.

Check Yourself

Each item is a situation; pick the statement that is actually correct.

Practice

• LeetCode 203 — Remove Linked List Elements dummy the canonical return dummy.next problem.
• LeetCode 19 — Remove Nth Node From End of List dummy a dummy makes deleting the head a non-case.
• LeetCode 82 — Remove Duplicates from Sorted List II dummy delete whole runs, head included.
• LeetCode 2 — Add Two Numbers tail build the result behind a dummy, appending at a tail pointer.
• LeetCode 21 — Merge Two Sorted Lists dummy+tail the archetype: dummy head, moving tail.
• LeetCode 707 — Design Linked List tail add a tail pointer and keep its invariant across every method.