Doubly Linked Lists and the Sentinel Header That Removes the Null Checks

A singly linked node can only be unlinked through its predecessor, which means any cursor-based removal has to search backwards from the head. A doubly linked node stores both neighbours, so a pointer to the node is enough to detach it. The price is one extra machine word per element and two pointer updates per splice instead of one. Whether that trade is worth making depends almost entirely on whether the program removes elements by reference or by position.

The two-pointer invariant

The representation is a node with prev and next, and a list that maintains the relation n->next->prev == n and n->prev->next == n for every node in it.

struct dnode {
    int value;
    struct dnode *prev;
    struct dnode *next;
};

On a 64-bit target this struct is 24 bytes for a 4-byte payload: eight for prev, eight for next, four for the value, and four bytes of padding. Against the 16 bytes of the singly linked version, that is 50 percent more memory per element, and the traversal touches a line per node either way, so the extra word does not by itself make traversal slower. What it does change is the number of independent loads: the backward pointer can be followed while the forward pointer is still in flight, so a bidirectional walk can overlap two chains.

Removal becomes symmetric and requires no search:

void unlink(struct dnode *n) {
    n->prev->next = n->next;
    n->next->prev = n->prev;
}

That is the whole operation, and it is O(1). Insertion before a known node is equally direct. The catch is that the two assignments dereference n->prev and n->next unconditionally, so the code above is only correct if neither neighbour is null. Handling the ends of the list is what forces every naive implementation to grow a set of if branches.

Why the ends are the problem

In a null-terminated doubly linked list, the first node has prev == NULL and the last has next == NULL. Each of the four operations, insert at head, insert at tail, remove at head, remove at tail, needs its own case, and the list header must hold both a head and a tail pointer to keep tail operations constant time. That gives six fields to keep consistent (head, tail, and the four boundary links), and every operation must reason about the case where the list is empty and head and tail are both null.

The number of distinct code paths is small but the interactions are not. A typical bug is removing the only element: both head and tail must be set to null, and a handler that updates only the head leaves a dangling tail that later appends will link to freed memory. A second common bug is inserting into an empty list, where the new node must be both head and tail and its own two pointers must be set consistently.

The sentinel makes the list circular

The alternative representation drops null entirely. The header is a node that holds no payload and is permanently linked into the ring: head.next is the first element, head.prev is the last, and the first element’s prev and the last element’s next both point back at the header.

struct dlist {
    struct dnode head;   /* sentinel: value unused */
};

static void init(struct dlist *l) {
    l->head.prev = &l->head;
    l->head.next = &l->head;
}

static void insert_before(struct dnode *pos, struct dnode *n) {
    n->prev = pos->prev;
    n->next = pos;
    pos->prev->next = n;
    pos->prev = n;
}

static void unlink(struct dnode *n) {
    n->prev->next = n->next;
    n->next->prev = n->prev;
}

Every node, including the sentinel, has non-null neighbours. unlink has no branches. insert_before has no branches and works at the head, in the middle, and at the tail identically. The empty list is a sentinel pointing at itself in both directions, which is a valid ring of length zero, so the same code handles it without a test. Iteration is bounded by comparing the cursor to the sentinel address rather than by testing for null:

for (struct dnode *n = l->head.next; n != &l->head; n = n->next) {
    /* visit n */
}

This is the layout used by the Linux kernel’s list_head, by the BSD queue.h macros for LIST_ and TAILQ_ entries, and by most hand-written intrusive lists. The reason is not elegance for its own sake. Branch-free unlink is what makes it safe to call the operation from a signal handler, from an interrupt context, or from a destructor where the list may already be in a partially updated state.

The cost is one node’s worth of memory per list, which is irrelevant for lists of any size, plus a subtle obligation: the sentinel is a struct dnode embedded in the list header, so the header cannot be copied by value. Copying a struct dlist duplicates the sentinel and produces two headers whose neighbours still point at the original. Lists of this shape must be initialised in place, never assigned.

Removal during iteration

The branch-free unlink makes the traversal idiom safe in the way that matters most: removing the current element while walking. With a null-terminated list, the loop must save next before freeing the node, and the last element needs special handling because next is null. With a ring, saving the successor is still required before the free, but the loop condition remains valid because the sentinel is never removed.

struct dnode *n = l->head.next;
while (n != &l->head) {
    struct dnode *next = n->next;   /* save before any free */
    if (should_remove(n)) unlink(n);
    n = next;
}

Reading n->next after unlink(n) is not safe in general. The pointer values in the node are still intact immediately after unlinking, since unlink writes only the neighbours, so the saved-successor discipline is not strictly necessary for that specific ordering. It becomes necessary as soon as the node is freed or recycled, which is the common case, and code that relies on the narrower guarantee is one refactor away from a use-after-free.

A second idiom removes the current node and continues from the previous node, which avoids the saved pointer entirely. It works because unlink leaves n->prev intact and still linked into the list. Both idioms appear in real code; the saved-successor form is easier to review.

What the second pointer does not fix

Doubly linked lists do not make indexing cheap. Reaching the k-th element is still O(k), and the only improvement over the singly linked case is that a search can start from whichever end is closer, halving the expected walk. A structure that needs both positional access and cheap splicing needs an index on top of the chain, which is what the unrolled layout in Unrolled Linked Lists and the Cost of a Cache Miss provides, or a tree.

They also do not make concurrent modification safe. Two threads unlinking adjacent nodes can each read a consistent pair of neighbours and then write an inconsistent combination, leaving the ring inconsistent. Making the updates atomic per pointer is not sufficient; the pair must change as a unit, which is why lock-free doubly linked lists are substantially harder than lock-free singly linked ones and why most lock-free designs in Lock-Free Linked Lists and the Reclamation Problem use a singly linked spine with a separate logical-deletion mechanism.

Memory overhead is the third limit. At 24 bytes per node for a 4-byte payload, a contiguous array of a million 4-byte integers occupies roughly 4 MB, and a list of the same integers occupies roughly 24 MB of node storage plus allocator metadata. The overhead ratio falls as payload size grows: a 64-byte payload yields an 80-byte node, so the link fields are a quarter of the total rather than five sixths.

Splice as the primitive that justifies the layout

The operations that a doubly linked list makes trivial are the ones that move existing nodes rather than create them. Splicing an entire ring into another is six pointer writes regardless of how many elements the ring holds:

/* Move all nodes of src between pos and pos->next. */
static void splice_before(struct dnode *pos, struct dlist *src) {
    if (src->head.next == &src->head) return;      /* empty source */
    struct dnode *first = src->head.next;
    struct dnode *last  = src->head.prev;
    struct dnode *before = pos->prev;

    before->next = first;  first->prev = before;
    last->next = pos;      pos->prev = last;

    init(src);             /* source becomes an empty ring */
}

The equivalent operation on an array copies every element, and on a singly linked list requires finding the predecessor of the insertion point and then walking to the tail of the moved range. This is the operation that appears in schedulers moving a batch of runnable threads between queues, in LRU caches moving a page from the middle of the list to the front, and in allocators coalescing free blocks. In each case the elements already exist and only their ownership changes, which is exactly what pointer relinking does cheaply.

The LRU case is worth stating precisely because it is the canonical use. A cache that must evict the least recently used entry keeps entries in a doubly linked list ordered by recency and a hash table for lookup. A hit unlinks the entry and reinserts it at the front, which is four pointer writes plus two hash operations, all O(1). Doing the same with an array requires shifting, and doing it with a singly linked list requires a search for the predecessor, which is O(n) and defeats the purpose.

When to choose the simpler node

The singly linked layout remains correct when removal always happens through a cursor that already tracks the predecessor, when memory density matters more than removal convenience, and when the list is short enough that the traversal cost is dominated by fixed overhead. The extra word is small in absolute terms and large relative to a small payload, and the branch-free sentinel ring saves branches that a modern predictor handles well in the common case.

The deciding question is not asymptotic. Both layouts give O(1) insertion at a known position. The question is whether the code ever holds a reference to an element and later needs to remove it without having retained its predecessor. If it does, the second pointer is the cheapest way to answer that need, and the sentinel is the cheapest way to make the answer branch-free.