Doubly Linked List, in depth: the sentinel ring, constant-time unlink by handle, invariant tests and the real hardware cost

The model and its invariant

Each node holds a value and two references, prev and next. The list holds a way to reach the first and last nodes and, usually, a size. One invariant carries the whole structure: for every node n whose next is a node, n.next.prev == n, and symmetrically n.prev.next == n. If that holds and the size matches the number of nodes reachable from the front, the list is well formed. Insertion and removal each touch at most four pointers; write them in an order where you never read a pointer you have already overwritten.

Sentinel ring versus null ends

There are two common shapes. The null-ended list keeps head and tail fields; the first node's prev is null and the last node's next is null. Every insert and remove then branches: am I at the head, at the tail, or is the list empty? Each branch is a place to forget an update.

The sentinel list allocates one dummy node that never holds a value and links the list into a ring through it. The first element is sentinel.next, the last is sentinel.prev, and an empty list is a sentinel pointing at itself both ways. Because every real node now has a non-null neighbour on both sides, insert and remove have no branches at all. The diagram shows the ring and the two writes that unlink a node.

A complete implementation with node handles

The implementation below hands callers the node itself as a handle. That is the point of the structure: an external index, such as a hash map from key to node, gives you the node in constant time, and the list then moves or removes it in constant time. Every mutator goes through two private primitives, so the pointer logic exists in exactly one place.

public final class DList<T> {
    public static final class Node<T> {
        T val;
        Node<T> prev, next;
        Node(T val) { this.val = val; }
        public T value() { return val; }
    }

    private final Node<T> sentinel = new Node<>(null);
    private int size;

    public DList() { sentinel.prev = sentinel; sentinel.next = sentinel; }

    // Splice n in between 'at' and at.next. Read at.next before overwriting it.
    private void linkAfter(Node<T> at, Node<T> n) {
        Node<T> after = at.next;
        n.prev = at;
        n.next = after;
        after.prev = n;
        at.next = n;
        size++;
    }

    private void unlink(Node<T> n) {
        if (n == sentinel || n.next == null) throw new IllegalStateException("not a live node");
        n.prev.next = n.next;
        n.next.prev = n.prev;
        n.prev = null;            // detach: a second remove now fails loudly
        n.next = null;
        size--;
    }

    public Node<T> addFirst(T v)                { Node<T> n = new Node<>(v); linkAfter(sentinel, n); return n; }
    public Node<T> addLast(T v)                 { Node<T> n = new Node<>(v); linkAfter(sentinel.prev, n); return n; }
    public Node<T> insertAfter(Node<T> at, T v) { Node<T> n = new Node<>(v); linkAfter(at, n); return n; }

    public T remove(Node<T> n) { unlink(n); T v = n.val; n.val = null; return v; }

    public void moveToFront(Node<T> n) {
        if (sentinel.next == n) return;
        unlink(n);
        linkAfter(sentinel, n);
    }

    public T pollFirst() { return size == 0 ? null : remove(sentinel.next); }
    public T pollLast()  { return size == 0 ? null : remove(sentinel.prev); }
    public int size()    { return size; }
}

After the two neighbour writes, unlink nulls the removed node's own pointers. A node that still points into the list is a dangling handle; a later remove would rewrite live neighbours and silently corrupt the list, whereas now it throws. If callers juggle several lists, add an owner field so a node from another list is rejected too.

Why the textbook delete is incomplete

A common textbook version of delete looks like this, and it is worth seeing why each line is incomplete:

void delete(Node n) {                       // null-ended list with head and tail fields
    if (n.prev != null) n.prev.next = n.next;
    if (n.next != null) n.next.prev = n.prev;
}

Three things are missing. When n is first or last, the list's head or tail field still points at it, so the deleted value is still reachable. The removed node keeps its pointers, so a repeated delete rewrites neighbours that have moved on. And nothing updates the size. If you keep the null-ended shape, the correct version is:

void unlink(Node<T> n) {
    if (n.prev == null) head = n.next; else n.prev.next = n.next;
    if (n.next == null) tail = n.prev; else n.next.prev = n.prev;
    n.prev = n.next = null;
    size--;
}

Testing the invariant

Pointer bugs surface far from their cause, so test the invariant: walk the ring checking every back link, and drive random operations against an ArrayList model:

void checkInvariants() {
    int count = 0;
    Node<T> p = sentinel;
    do {
        if (p.next.prev != p) throw new AssertionError("back link broken after " + p.val);
        p = p.next;
        if (p != sentinel && ++count > size) throw new AssertionError("cycle or size drift");
    } while (p != sentinel);
    if (count != size) throw new AssertionError("size=" + size + " walked=" + count);
}

@Test void randomOpsMatchModel() {
    Random r = new Random(42);
    DList<Integer> list = new DList<>();
    List<DList.Node<Integer>> handles = new ArrayList<>();
    List<Integer> model = new ArrayList<>();
    for (int i = 0; i < 100_000; i++) {
        int k = handles.isEmpty() ? -1 : r.nextInt(handles.size());
        switch (k < 0 ? 0 : r.nextInt(3)) {
            case 0 -> { handles.add(list.addLast(i)); model.add(i); }
            case 1 -> { list.remove(handles.remove(k)); model.remove(k); }
            default -> { list.moveToFront(handles.get(k));
                         handles.add(0, handles.remove(k)); model.add(0, model.remove(k)); }
        }
        list.checkInvariants();
        assertEquals(model, list.values());     // values(): walk sentinel.next to sentinel
    }
}

The seed is fixed so a failure reproduces, and walking the invariant after every step, though quadratic, localises a bug to the exact operation that broke the ring.

What java.util.LinkedList gives you

java.util.LinkedList is a doubly linked list that implements both List and Deque, with null ends rather than a sentinel. First, it never gives you a node handle, so constant-time removal is only reachable through ListIterator.remove() and add(), while remove(Object) and get(int) walk the list; a loop of get(i) is quadratic.

Second, its iterators are fail-fast: structural changes made other than through the iterator cause the next iterator call to throw ConcurrentModificationException, on a best-effort basis that the Javadoc says not to rely on for correctness. Third, the ArrayDeque Javadoc says it is likely to be faster than LinkedList when used as a queue, so prefer it for stacks and queues. For a concurrent deque, use ConcurrentLinkedDeque rather than synchronising your own list.

Intrusive lists in the Linux kernel

The Linux kernel inverts the usual layout. Instead of a list node that points at a payload, the payload embeds the links: struct list_head { struct list_head *next, *prev; }; sits inside the structure being listed, and container_of (wrapped by list_entry) recovers the enclosing structure from the address of the embedded member by subtracting the member's offset.

struct task_req {
    int id;
    struct list_head link;      /* membership in one queue */
};

LIST_HEAD(ready);               /* sentinel, initialised to point at itself */

void enqueue(struct task_req *r) { list_add_tail(&r->link, &ready); }

void drain(void) {
    struct task_req *r, *tmp;
    list_for_each_entry_safe(r, tmp, &ready, link) {   /* _safe: tmp survives deletion of r */
        list_del(&r->link);
        handle(r);
    }
}

Intrusive lists need no separate node allocation, remove by object pointer in constant time, and let one object sit on several lists by embedding several list_head members. list_del poisons the removed entry's pointers so a later use faults recognisably, the same idea as nulling them in Java.

Worked example: six operations traced

Trace a short session on the sentinel list, writing S for the sentinel. Start empty: S.next = S, S.prev = S, size 0.

In step 2, linkAfter reads A.next before overwriting it. Step 4 is what makes an LRU cache constant time: a hash map hands over node C and two primitives move it. Step 6 is the detach paying for itself.

What it costs on real hardware

Asymptotic costs are the easy part: constant-time insert and remove at a known node, linear search and linear indexed access. The hardware cost is what decides whether to use the structure. Each node is a separate heap object. On a 64-bit HotSpot JVM with compressed references, a node with three reference fields is typically about 24 bytes including the object header, before counting the element it points to; without compressed references it is larger. An ArrayList spends about 4 bytes per element slot on the same JVM, plus growth slack.

Traversal is worse. Walking an array streams contiguous memory the prefetcher fetches ahead; walking a list is pointer chasing: the address of node k+1 is not known until node k has loaded, so each step can expose a full cache miss, on the order of a hundred nanoseconds when the node is in DRAM. A list built in one burst may sit nearly contiguous and look fine in a benchmark; after churn the nodes scatter. Measure with a realistic allocation history.

Where it earns its place

The structure earns its place in a handful of designs, all of which pair it with an external handle:

• LRU caches. A hash map from key to node plus a list ordered by recency: a hit is moveToFront, an eviction is pollLast. The LRU cache architecture article covers the concurrency cost of making every read a write.
• LFU caches. One list per frequency bucket, with nodes moving between buckets in constant time; see the LFU cache design.
• Schedulers and timer wheels. Cancelled tasks leave the middle of a queue.
• Allocator free lists. Coalescing a freed block removes its neighbours from the list.

Failure modes

• Stale head or tail. A null-ended list whose remove forgets to update the end fields. Symptom: a removed value reappears from peekFirst. Fix: use a sentinel or the branchy unlink above.
• Write-order bug on insert. Overwriting at.next before reading it, which links the new node to itself. Symptom: an infinite loop on traversal. Fix: read the neighbour into a local first.
• Double removal. A handle removed twice rewrites live neighbours. Fix: null or poison the removed node's pointers and check in unlink.
• Mutation during iteration. Removing the current node destroys the loop's next pointer. Fix: save next first, as the kernel's _safe macros do.
• Unsynchronised sharing. Interleaved inserts leave the ring half linked. Fix: a lock or a concurrent deque.

Trade-offs

Use a doubly linked list when your operations are removal and reinsertion of nodes you already hold and full traversals are rare. For indexed access use ArrayList, for ends-only work ArrayDeque, and for ordered search a balanced tree or skip list.

Compared with a singly linked list, the second pointer costs memory and write traffic but removes the need to find a predecessor, which is the operation that makes singly linked deletion awkward. Reversal is also simpler: swap prev and next in every node including the sentinel, compared with the three-pointer loop in reversing a singly linked list. Sorting is still best done with merge sort, as in sorting a linked list, fixing up the prev pointers in one pass at the end.

What to do next

1. Implement the sentinel DList above from memory, then run the randomized model test against it.
2. Break it on purpose: delete the line that nulls pointers in unlink and confirm the double-remove test no longer throws. Then reorder two writes in linkAfter and watch the invariant checker catch it.
3. Build an LRU cache on top of it with a HashMap<K, Node> and check every operation is constant time.
4. Audit your codebase for LinkedList used as a queue or with indexed get; replace with ArrayDeque or ArrayList and measure.
5. Benchmark traversal of a list against an array after shuffling allocation order, so you have your own numbers for the cache-miss cost.
6. If you write C, read the kernel's list header and use list_head instead of a hand-rolled list.