Sentinel & Dummy-Head Nodes

## The node that has no predecessor A singly-linked list is a chain of heap-allocated nodes, each holding a payload and a reference to the next node; the list object itself holds one reference — the head — to the first node. Every node in that chain is reachable from its predecessor, except one: the first. That single asymmetry is the source of nearly every edge case people write in list code. Unlinking a node means giving its predecessor a new `next`. Position zero has no predecessor, so the routine must do something structurally different: reassign the head reference stored in the list object. Inserting at position zero has the same shape. A hand-written delete therefore grows three paths — one for the empty list, one for "the target is the first node", and one general scan. ## What the sentinel changes A dummy head (sentinel) is a permanently allocated node placed before the first real element. It carries no payload the application cares about, it is never returned to callers, and it is never removed. The list holds a reference to the sentinel rather than to the first element; the first real element is `sentinel.next`; the empty list is exactly the state `sentinel.next == null`. Now position zero has a predecessor. Delete becomes: start `prev` at the sentinel, walk while `prev.next != null`, and when `prev.next` is the target, set `prev.next = prev.next.next`. That one line handles a first, middle or last element identically, and it handles the empty list with no test at all, because the loop body simply never runs. Insertion is the same story: `fresh.next = prev.next; prev.next = fresh`, with `prev = sentinel` for a prepend. ## Why this is a bug class, not a style preference Three arguments, in ascending order of how much an interviewer cares: 1. **Branch count.** Three code paths become one, so the path that used to be exercised only by two rare input shapes is now exercised by every input. 2. **Duplication.** The head branch is not written once — it reappears in delete, insert-at, splice, filter and every other mutating routine. Each copy is a fresh chance to forget one of the two updates it owes. 3. **The head reference.** The head branch is the only one that writes state outside the chain. Forgetting that write, or ordering it wrongly, leaves the list pointing at a node that has already been unlinked — the classic "the deleted entry is still there" or "the list suddenly looks empty" defect. Consider an append-only ledger of signed amounts with timestamps, kept newest-first. Reversing the most recent entry always removes the first node, so the head branch is not a rare corner — it is the hot path, while the general loop that collects all the incidental testing almost never runs on real traffic. A sentinel deletes that asymmetry outright. ## What it costs One node's worth of memory per list — negligible for a few long lists, real if you keep millions of two-element lists. One extra dereference to reach the first element. And a discipline: everything that walks, counts or reports on the list must begin at `sentinel.next`, and the sentinel must never escape the structure. A length routine that starts at the sentinel returns n+1; a search that compares the sentinel's default payload can return a phantom match. ## Design variants - **Head-only sentinel, null-terminated.** Removes the empty-list and head branches; reaching the tail still costs a scan. - **Head and tail sentinels.** Every real node has both a predecessor and a successor, so insert-before, insert-after and remove are uniform at both ends, at the cost of two permanent nodes per list. - **Sentinel ring** (doubly linked, both ends wrapping through one sentinel). No null appears anywhere in the structure; iteration terminates by arriving back at the sentinel instead of by hitting null. ## Trace the single-element case once With a sentinel and exactly one real node X: `sentinel.next == X` and `X.next == null`. Deleting X runs the general loop, matches with `prev == sentinel`, sets `sentinel.next = X.next` which is null, and the list is empty — a state the code already understands. Without a sentinel, that same delete must notice both that the head is going away and that the list becomes empty; two conditions inside one branch is precisely where single-element bugs are born.