Doubly & Circular Linked Lists

The 10-second versionCopy Anchor Link

A doubly linked list gives every node a second link — prev — pointing to the node before it. That one extra pointer buys you the operation the singly linked list can't do: delete a node you already hold in O(1), with no walk back to the head to find its predecessor. A circular list is the same structure with the tail's next pointing back at the head instead of at null, so there's no "end" — you start somewhere and go around forever. Together they power LRU caches, OS run queues, media playlists, and browser history. And once you have links that can form cycles, you need Floyd's tortoise-and-hare to tell a loop from a straight line.

Why this existedCopy Anchor Link

By the mid-1960s linked lists were everywhere, and a specific pain kept surfacing: the singly linked list can only walk forward. If your caches, editors, and schedulers all needed to remove a node they were pointing at — an evicted cache entry, a deleted line, a finished process — they had to remember the node before it, or re-scan from the head every time. The fix was almost embarrassingly simple: store the predecessor link too.

• 1968 — Donald Knuth's The Art of Computer Programming, Volume 1 catalogs the family in full: singly linked, doubly linked, and circular lists, each with its trade-offs.
• 1969 — Robert Floyd shows that a tortoise-and-hare pair of pointers detects a cycle in O(n) time and O(1) space — the price of admission once lists can loop.
• 1991 — the Linux kernel runs ready tasks off circular run queues, so the scheduler can rotate through them without ever "running out."
• 2000s — LRU caches everywhere pair a hash map with a doubly linked list, because "touch this entry" and "evict the oldest" both become O(1).

Why it mattered then: operating systems and editors ran into the forward-only wall constantly. A doubly linked list turned "find the predecessor, then unlink" into plain "unlink," and a circular list turned "we've reached the end" into "we're back at the start." Both are about removing special cases from hot paths.

Inside the inventor's headCopy Anchor Link

Picture a scheduler holding a pointer to the process that just finished. It wants to unlink that process's node. With a singly linked list, the node knows only where to go next — it has no idea who points at it. So the code has to drag the head along, hopping one node at a time until it finds the one whose next is the victim.

The naive attempt — the one everybody writes first — pays the walk every single time:

// Singly linked: each node knows only `next`.class SNode {  constructor(value, next = null) { this.value = value; this.next = next; }}// Delete a node you hold — must walk to its predecessor first: Θ(n).function removeSingly(head, target) {  if (head === target) return target.next;  let prev = head;  while (prev && prev.next !== target) prev = prev.next;  if (prev) prev.next = target.next;      // now unlink  return head;}// Doubly linked: the target knows its predecessor — Θ(1).function removeDoubly(list, target) {  if (target.prev) target.prev.next = target.next;  else             list.head = target.next;  if (target.next) target.next.prev = target.prev;}

The pivot generalizes beyond deletion: with a back-pointer, you can insert before a node you hold in O(1) too, and you can walk backward. The cost is honest — one extra pointer per node, more care when updating links (you now fix four pointers on every splice instead of two), and a little more memory.

The final approachCopy Anchor Link

The shapesCopy Anchor Link

Doubly linked — every node points both ways, so you can leave from either end:

Circular — the tail's next wraps to the head, so there is no null terminator and no special "end":

(A doubly circular list does both at once: last.next = first and first.prev = last, so every node has a well-defined predecessor and successor with no null checks at the ends.)

The invariantsCopy Anchor Link

• Doubly: for every node n with a successor m, m.prev points back at n; and for every node with a predecessor p, p.next points forward at it. The links come in consistent pairs — update one without the other and the list tears.
• Circular: following next from any node eventually returns to it; the tail's next is the head, and (if doubly circular) the head's prev is the tail. No node has a null link, so traversal must stop by recognising the start again, not by hitting null.

A flow: delete a node you hold (doubly)Copy Anchor Link

A worked trace: delete 7 from 3 ↔ 7 ↔ 9Copy Anchor Link

Two writes, no matter whether the list has 3 nodes or 3 million. Compare the singly list: to delete 7 there, you'd first have to walk from the head to find 3. That walk is the difference the extra pointer buys away.

It in codeCopy Anchor Link

class Node {  constructor(value) { this.value = value; this.prev = null; this.next = null; }}// Insert `value` immediately after `node` — O(1).function insertAfter(node, value) {  const n = new Node(value);  n.prev = node;  n.next = node.next;  if (node.next) node.next.prev = n;       // fix the far side's back-link  node.next = n;  return n;}// Delete a node we already hold — O(1), no search, no predecessor walk.function removeNode(list, node) {  if (node.prev) node.prev.next = node.next;  else           list.head = node.next;    // it was the head  if (node.next) node.next.prev = node.prev;}

ComplexityCopy Anchor Link

Operations on a doubly linked list, starting from a handle into it:

And the doubly-versus-singly trade, made concrete:

You're paying one pointer per node — on a 64-bit machine, 8 bytes — to delete every special case out of the hot path.

Floyd's tortoise-and-hareCopy Anchor Link

Circular lists are wonderful and dangerous: a traversal that expects a null terminator will spin forever. The classic guard is Floyd's cycle detection — walk one pointer one step at a time (the tortoise) and a second pointer two steps at a time (the hare). If there's a loop, the hare laps the tortoise and they meet; if there's an end, the hare reaches it first. O(n) time, O(1) space, no extra memory. (Here the list is an array of next-indices so the exact same code runs in all three languages — and that's genuinely how kernels encode these.)

// next[i] is node i's successor, or -1 for the end.const hasCycle = (next, start = 0) => {  let slow = start, fast = start;  while (fast !== -1 && next[fast] !== -1) {    slow = next[slow];            // tortoise: +1 step    fast = next[next[fast]];      // hare:     +2 steps    if (slow === fast) return true; // they met → there's a loop  }  return false;                   // hare hit the end → no loop};

There's a beautiful bonus: once the two pointers meet, walking one of them from the head and the other from the meeting point, one step at a time, finds the start of the cycle. That's the full Floyd algorithm, and it's the standard interview follow-up.

Where you meet it todayCopy Anchor Link

• LRU caches. A HashMap plus a doubly linked list: the map finds the entry in O(1), and "move to front" / "evict the tail" are O(1) relinks. This is the classic design behind Redis's and every browser's cache.
• OS scheduling. Ready processes sit on a circular run queue; the scheduler picks the next, runs it for a slice, and rotates. No "end of the line" to special-case.
• Media players. A playlist is a doubly circular list: next and previous both wrap, so "shuffle" and "repeat" are just different walk orders.
• Undo / redo and browser history. A doubly linked list of states where the current node can move both ways — back and forward without losing the branch.

// next[i] gives i's successor; the last node wraps to index 0.const runRound = (next) => {  let i = 0;  do {    handle(i);    i = next[i];  } while (i !== 0);         // stop when we loop back to the start};

The do … while matters: in a circular list you must visit the start before you can recognise it again, so the check lives at the bottom of the loop, not the top.

RecapCopy Anchor Link

• Add prev to every node and any node you hold can be unlinked in O(1) — no walk to a predecessor ever again.
• It costs one pointer per node and demands you keep link pairs consistent (fix both sides on every splice).
• A circular list's next wraps tail→head, so there's no null end; stop by recognising the start, and always check at the bottom of the loop.
• Floyd's tortoise-and-hare detects a cycle in O(n) time and O(1) space — and can even find where the loop begins.
• These two upgrades are exactly what make LRU caches, OS run queues, and playlists tick.

Next up: Stacks — the first abstract structure, where the discipline is in how you're allowed to touch the list, not in how it's wired.