---
title: "Doubly Linked List"
description: "prev + next — O(1) delete, both ways"
source: https://vizlearn.app/algorithms/data-structures/doubly-linked-lists
---

# 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

| Operation | Cost | Why |
|---|---|---|
| Access by index | O(n) | follow `next` (or `prev`) from an end |
| Insert at head | O(1) | three pointer writes, no walk |
| Insert at tail | O(1) | the `tail` pointer skips the walk |
| Insert at index k | O(k) | walk to the predecessor, then O(1) splice |
| Delete a held node | O(1) | `node.prev` / `node.next` give both neighbours |
| Delete by value | O(n) | the *find* is O(n); the unlink is O(1) |
| Search / Search back | O(n) | compare node by node, either direction |
| Space | O(n) | one value plus **two** pointers per node |

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.