Linked lists (doubly)

The tab you closed

Right-click a browser tab and hit Close. The browser had a pointer to that exact tab the instant the menu opened — it didn't have to scan to find which tab you meant. It yanks the tab out and stitches its neighbours back together. Try that with the singly linked list from the last lesson, and you'll discover the missing piece: the tab you held onto didn't know who came before it. To remove it, you'd have to walk from head looking for the node whose next is your tab. That isn't "given a pointer, O(1)". That's O(n) hiding inside a O(1) claim. The doubly linked list is what makes the lie true.

A node that knows both neighbours

Add one field. That's it.

type DNode = {
  value: number;
  prev: DNode | null;
  next: DNode | null;
};

Every node now points two ways. The list itself still has head and tail references, but each node is independently aware of who came before it and who comes after. The shape on the heap hasn't changed — nodes still live at unrelated addresses, traversal is still pointer chasing, the cache still hates you. What's changed is the operation set. Given any node pointer, you can now splice it out, splice it in, or walk in either direction with no scan from head.

There's a second change worth pinning down before we look at anything else. Real implementations almost always use sentinel head and tail nodes — dummy nodes that never carry a value, that exist purely so every real node is guaranteed to have a non-null prev and next. Splice code that would otherwise be ten lines of if (node === null) collapses to four pointer rewrites with no edge cases. The Linux kernel's list_head does this. Java's LinkedList does this. The visualiser does this.

function construct() {
  const head = { value: null, prev: null, next: null };
  const tail = { value: null, prev: head, next: null };
  head.next = tail;
  return { head, tail, size: 0 };
}

The two ghosted boxes at the ends are the sentinels. Press append a few times and watch what happens — every append, regardless of list size, is the same four pointer rewrites: the new node's prev and next point at the sentinels' old neighbours, and those neighbours' pointers reach back. There's no "first node" edge case. There's no "empty list" edge case. The sentinels are always there, always non-null, always reachable.

The back-arrow doesn't make traversal faster. It doesn't enable random access by index. It doesn't prevent cycles. What it unlocks is exactly one thing: detach a node in O(1) without walking. Every other apparent feature of doubly linked lists — backward iteration, O(1) operations at both ends, cheap LRU touches — is downstream of that one capability.

Forward, then backward

function walkForward(list) {
  let cur = list.head.next;
  while (cur !== list.tail) {
    visit(cur);
    cur = cur.next;
  }
}

function walkBackward(list) {
  let cur = list.tail.prev;
  while (cur !== list.head) {
    visit(cur);
    cur = cur.prev;
  }
}

These two functions are mirror images. Each step is a single pointer dereference, no different in cost from the singly chain walk you saw last lesson. The difference is that walkBackward exists. In a singly linked list, walking backward from any node requires either restarting from head for every step (O(n²) total to traverse the list backward) or building a separate stack (O(n) extra space). Here it costs nothing extra to begin with — you paid for the prev pointers when you allocated the nodes.

Drive the visualiser through both walks. Same number of hops. Same constant-factor cost per hop. Direction is purely which arrow set you follow.

Detach: the operation that earns the prev pointer

Here is the function that justifies the entire structure.

function detach(node) {
  node.prev.next = node.next;
  node.next.prev = node.prev;
  node.prev = null;
  node.next = null;
}

Two lines do real work. Each one rewrites a neighbour's pointer to skip past the doomed node. There is no walk. There is no cursor. There is no head-to-here scan. The caller already holds the pointer to the node — typically because some other data structure handed it over — and detach runs in true O(1) time, regardless of where in the list the node lives.

Compare that to the singly version. Even with the doomed node's pointer in hand, you'd have to walk from head looking for the node whose next is the doomed one. That walk is O(n). The "two writes" are the same in both structures; the missing predecessor is what made the singly version dishonest about its O(1) claim.

The two pointer writes happen on the neighbours, not on the doomed node itself. The doomed node still has its old prev and next pointers lying around for a moment — and the third and fourth lines clear them. That's not optional hygiene. Code that later inspects the detached node and finds it still has prev and next set will assume it's still in the list. The cleanup writes are part of the operation, not polish.

The order matters because the node owns the only references to its neighbours during the splice. Null node.prev first, and the next line — node.prev.next = node.next — will throw on a null dereference. Rewrite both neighbours first, then clean up. This is the canonical sequence; every reference implementation in glibc, the Linux kernel, and the JDK does it in this order.

What the extra pointer actually costs

Adding a prev pointer doubles the per-operation pointer rewrites and slightly inflates each node's memory footprint. A doubly linked node holding a 32-bit integer carries the value plus two 8-byte pointers — versus the singly variant's value plus one pointer. On the surface that looks like the doubly version uses 2× the per-node memory.

It doesn't, because the heap allocator already imposes 16-or-so bytes of metadata per allocation, and the value itself takes space in both cases.

So the extra pointer is real, but the ratio of doubly to singly memory is closer to 1.15× — 1.3× than 2×. That's not nothing — 8 MB extra on a million-node list is a real cost in tight environments — but it's also not the catastrophe the misconception fears. If you're already paying for the linked-list shape, the doubly variant doesn't change the order of magnitude of your memory footprint.

What it does change is the per-mutation work. Every splice now does roughly twice the pointer writes. Every detach does two writes instead of one. Every insert does four writes instead of two. The throughput cost is real and visible in any tight loop that mutates a doubly linked list against a singly linked one. Doubly is slower per operation, in exchange for capabilities the singly version cannot provide.

That's the actual trade. Not "doubly is better." Not "singly is faster." It's: pick the structure whose capabilities you need.

Compose detach with insert: moveToFront

Here is what production systems actually do with this structure.

function moveToFront(list, node) {
  if (list.head.next === node) return;
  // unlink in place — 2 writes
  node.prev.next = node.next;
  node.next.prev = node.prev;
  // re-link at the head — 4 writes
  node.prev = list.head;
  node.next = list.head.next;
  list.head.next.prev = node;
  list.head.next = node;
}

Six pointer writes. Zero allocations. Zero walks. The node was somewhere in the list; now it's at the front. This function is the complete story of why LRU caches are O(1) on every operation — and why every production LRU cache you've ever used is built on a doubly linked list.

That sequence is wrong because it forgets the symmetric write on the prev side. Splice code that updates only the next side leaves the list in a state that is internally inconsistent: forward iteration works perfectly, backward iteration is broken. This is the single most common bug in handwritten doubly-linked-list code. It survives every test that only walks forward. It only fails when something — eventually — tries to walk backward and finds a prev pointer that doesn't reach where the next pointer says it should.

Splice operations don't compose visually — you have to track the list's state after each mutation. The most common stumble is forgetting that an earlier detach removed a node, and then assuming the node is still around for a later operation. A detached node is gone from the list. Subsequent operations see only what's currently linked.

The LRU cache, finally

A hash map gives you O(1) lookup of a node pointer by key. A doubly linked list gives you O(1) splice given a node pointer. Compose them and you have a cache where every operation — get, put, evict — runs in constant time.

function lruTouch(cache, key) {
  const node = cache.map.get(key);
  if (node) moveToFront(cache.list, node);
  return node?.value;
}

Drive the visualiser through a few lruTouch calls. The Map panel highlights the hit row, hands back the node pointer, and moveToFront runs the same six pointer writes you saw above. The whole touch is bounded by a handful of memory operations, regardless of cache size. A hundred entries or a hundred million entries — the touch cost is the same.

Eviction works the same way. When a put arrives at full capacity, the cache pulls tail.prev (the LRU node), removes its key from the hash map, and detaches it from the list. Two pointer writes plus a hash-map delete; both O(1). Then a fresh node is allocated and prepended at the head. The whole put-at-capacity is O(1).

This is what LinkedHashMap in Java does, with the access-order constructor and removeEldestEntry. It's what Memcached's slab allocator does for its LRU per slab class. It's what OrderedDict in Python does for move_to_end. The pattern is so common that intrusive variants exist specifically to skip the wrapper-node allocation: the prev/next pointers live inside the cached value's struct, and the "list" is a handle to wherever the head and tail of those embedded pointers happen to be.

When doubly is the wrong tool

Honest section. Doubly linked lists are the right structure when you actually need detach-given-pointer, backward iteration, or O(1) operations at both ends. They are the wrong structure — strictly worse than the singly variant — when you don't.

The free-list inside a malloc implementation pushes and pops at the head and never touches the middle of the list. Singly is enough; the prev pointer is dead weight on every free block. The hash-table chain off a bucket gets walked from the bucket pointer and rarely deleted by node reference. Singly is enough; the prev pointer wastes 8 bytes per entry. A LISP-style cons-cell list gets traversed forward only. Singly is enough; the prev pointer is purely overhead.

The rule isn't "doubly is more powerful, so use it by default." It's "use the structure whose operations you actually need." A doubly linked list that is only ever used as a singly linked list is a singly linked list with extra steps and a memory tax.

Every cache argument from the previous lesson still applies — pointer chasing serialises memory loads, the prefetcher cannot help, and an array beats both linked-list variants for almost every iteration-heavy workload below ten thousand elements. Doubly doesn't fix this. Doubly makes it slightly worse, because each node is bigger and fewer fit in a cache line.

Where this shows up in real systems

Doubly linked lists are everywhere a piece of software needs to hold a pointer to a thing and remove it instantly when the time comes. Four places worth knowing.

• The Linux kernel uses list_head — defined in include/linux/list.h — for almost every list it maintains: the task list, file descriptor tables, dirty page lists, network packet queues. The structure is a circular doubly linked list with a single sentinel; the prev/next pointers live inside the values that are being listed (intrusive style), so detaching a task from the runqueue is allocation-free.
• LinkedHashMap in Java layers a doubly linked list of entries on top of HashMap. Constructed with the access-order flag, it's the JVM's standard idiom for an LRU cache: every get runs moveToFront on the corresponding node; every put at capacity removes the eldest entry from the tail. Source: src/java.base/share/classes/java/util/LinkedHashMap.java.
• Memcached's LRU eviction is the textbook implementation: a hash table for O(1) lookup that returns a pointer into a doubly linked list ordered by recency. Touch a key, splice its node to the front; evict the tail. Source: items.c.
• Python's collections.OrderedDict is a hash map paired with a doubly linked list of keys. The doubly linked list is what makes move_to_end O(1), and it's why OrderedDict survived even after regular dict got insertion order in 3.7 — OrderedDict supports operations the compact-array dict does not.

The pattern is consistent across all four. Hash map for lookup; doubly linked list for ordering and O(1) splicing; the two paired together because neither alone is enough. That pairing is the dominant idiom for "I need to find by key and maintain an order and mutate the order in O(1)" — a surprisingly common requirement, once you start looking for it.

What to learn next

• Stacks — the simplest application of "use a linked list, but only at one end". Singly linked lists are enough; doubly is overkill.
• Queues — head-and-tail operations that singly linked lists handle if you keep both pointers, doubly linked lists handle without thinking about it.
• Deques — the structure that genuinely needs doubly linked lists in the general case, and the abstraction LinkedList in Java implements.
• Fast & slow pointers — a pattern that exploits chained structures to detect cycles and find midpoints, equally applicable to singly and doubly variants.