Doubly Linked Lists

A doubly linked list gives every node a second pointer. Alongside next, each node keeps a prev pointing back at the node before it, and the list tracks both ends — head and tail. That extra pointer buys two things a singly list can't do: walk the chain backward, and delete a held node in O(1) without first finding its predecessor.

The cost is bookkeeping. Where a singly insert rewires one or two pointers, a doubly insert between two nodes touches four — the new node's prev and next, plus a next and a prev on its neighbours. At an end, one neighbour is missing and head or tail takes its write. Nothing here is hard; there's just twice as much of it, and getting the order wrong corrupts the chain in both directions instead of one.

How a Doubly Linked List Works

Picture each node as a train car with a coupling at both ends: one reaching forward to the next car, one reaching back to the previous. The locomotive is head; the caboose is tail. Because the couplings point both ways, you can walk the train from either end — and to remove a car you uncouple it on both sides and clasp its two neighbours together, no walking required once you've found it.

Every structural operation maintains the symmetry. insert between pred and succ does four writes: newNode.prev = pred, newNode.next = succ, then pred.next = newNode and succ.prev = newNode. The animation plays this as two beats — the new node reaching out to both neighbours, then both neighbours reaching back — so the four writes read as two symmetric pairs.

delete is where the second pointer earns its keep. A singly list, having found the target, still doesn't know what came before it, so it must walk again (or look ahead the whole way) to reach the predecessor the rewire needs. A doubly list already holds both neighbours: node.prev and node.next are right there. The unlink is node.prev.next = node.next and node.next.prev = node.prev — two O(1) writes, no second walk. Finding the node by value is still O(n); the deletion itself is O(1).

search walks forward from head following next; search_back walks from tail following prev. Same comparison, opposite direction — the clearest proof that the backward links are real and usable.

One honest disclosure: the capacity slider (4–10 nodes, default 7) exists only because the canvas fits so many boxes. The code mirrors it with a max field, but a real linked list has no capacity.

Doubly Linked List Operations Step by Step

The list starts empty. Run this sequence from the Inputs panel:

1. Insert Head 5 — the first node. With nothing on either side, 5.prev and 5.next are both null, and head and tail both land on it. List: 5.
2. Insert Head 8 — node 8 stages above slot 0. It reaches out: 8.next = 5, 8.prev = null. Then 5 reaches back: 5.prev = 8, and head swings to 8. List: 8 ⇄ 5.
3. Insert Tail 3 — no walk. The tail pointer puts us at 5 immediately (O(1); a singly list that keeps only head must walk to the end). Node 3 links: 3.prev = 5, 3.next = null; then 5.next = 3 and tail swings to 3. List: 8 ⇄ 5 ⇄ 3.
4. Insert At Index 1, value 7 — curr walks forward to the predecessor at index 0 (node 8). Node 7 links to both neighbours: 7.prev = 8, 7.next = 5; then 8.next = 7 and 5.prev = 7. List: 8 ⇄ 7 ⇄ 5 ⇄ 3.
5. Search → 7 — forward from the head: index 0 is 8 ≠ 7; index 1 is 7 = 7. Found at index 1.
6. Search ← 5 — backward from the tail, following prev: index 3 is 3 ≠ 5; index 2 is 5 = 5. Found at index 2. Same list, opposite direction.
7. Delete 7 — forward walk lands curr on node 7 at index 1 (not on its predecessor). Now hold it: 7.prev is 8 and 7.next is 5, so the unlink is immediate — 8.next = 5 and 5.prev = 8. Node 7 lifts out and the chain closes from both sides. List: 8 ⇄ 5 ⇄ 3.

On the canvas, the forward next links ride the upper lane and the backward prev links ride the lower lane, so the two directions never tangle. A staged node hovers above its slot until its pointer writes land; on a delete, the cursor sits on the node you're removing while the bypass arrows swing past it on both lanes at once.

Time and Space Complexity

Against a singly list that keeps only head, this lesson adds prev links and a tail pointer. The prev links (more memory, more writes per op) buy backward traversal and O(1) deletion of a held node; O(1) tail insertion comes from tail, which a singly list can keep too.

Edge Cases

• Insert into an empty list — head and tail insertion collapse into the same move: the lone node becomes both head and tail, with prev and next both null.
• Delete the head — node.prev is null, so instead of prev.next = … the code sets head = node.next; if a new head exists, head.prev = null.
• Delete the tail — symmetric: tail = node.prev; if a new tail exists, tail.next = null.
• Delete the only node — both neighbours are null, so head and tail both become null and the list is empty again.
• Delete or search a missing value — the forward (or backward) walk runs off the end and returns gracefully (False / -1). No exception.
• insert_at(k, v) with k past the end — the shown code has no bounds check and would walk off the chain; the visualization stops and says so instead. (k = 0 delegates to insert_head, k = size to insert_tail.)

Common Mistakes

• Updating only one direction. After splicing in a node you must fix both a next and a prev on the neighbours. Set pred.next = newNode but forget succ.prev = newNode and a forward walk looks fine while a backward walk skips the new node — a bug that hides until someone calls search_back.
• Forgetting the end pointers. Deleting the head without reassigning head, or the tail without reassigning tail, leaves the list pointing at a node that's no longer in it. The head/tail/only branches exist precisely to catch these.
• Walking to find the predecessor on delete. That's the singly habit. In a doubly list the node already carries prev — re-walking to find what comes before it throws away the whole reason the structure costs an extra pointer.
• Reaching for a doubly list by default. The extra pointer is dead weight unless you actually delete held nodes or traverse backward. If you only push, pop, and walk forward, a singly list — or a plain array — is leaner.