Skip to content

level 5 · Linked structures

Doubly Linked List

One extra pointer per node — and the singly linked list's worst flaw disappears.

9 min 70 XP

what is it

Start here

The singly linked list had one deeply annoying flaw: to delete a node, you needed the node *before* it — because the arrows only pointed forwards. So you had to walk from the head just to find out who was standing behind you.

A doubly linked list fixes it by giving every node a second pointer: `prev`, aimed at the node behind. Now a node knows both its neighbours. Deleting it costs one step — re-aim two arrows and it's out. No walking, O(1).

It also means you can walk the list backwards, which a singly linked list simply cannot do at any price.

The cost is real, though: one extra pointer per node (more memory), and two arrows to keep correct on every single insert and delete. Forget to update a `prev` and the list quietly corrupts — walking forwards still works, so the bug hides for a long time.

This is the structure behind an LRU cache and your browser's back/forward buttons — anywhere you need to yank something out of the middle instantly, or move in both directions.

real-life analogy

Picture it

A conga line where everyone holds on both ways

In a normal conga line you hold the person in front. If someone leaves, the person behind them has no idea who to grab — they have to look. Now have everyone hold both the person in front and the person behind. Someone leaves, and their two neighbours simply join hands. Nobody has to search for anybody.

interactive visualization

Watch it run

Walk forwards, then backwards, then delete from the middle in one step.

  1. head
  2. 4
  3. 8
  4. 15
  5. 16
  6. 23
  7. NULL

A doubly linked list gives every node a second pointer: one to the next node, one to the previous. That's one extra arrow, and it changes everything.

step 01/15

  • comparing
  • moving
  • in final place
  • found it
1class Node {
2 constructor(value) {
3 this.value = value;
4 this.prev = null; // the extra pointer
5 this.next = null;
6 }
7}
8
9function remove(node) {
10 // No walk needed — the node knows who is behind it.
11 if (node.prev) node.prev.next = node.next;
12 if (node.next) node.next.prev = node.prev;
13 node.prev = null;
14 node.next = null;
15}

variables right now

length
5
comparisons 0moves 0

the dry run · every step, in words

15 steps

complexity

What it costs

best case
O(1) delete a known node
average
O(n) to find
worst case
O(n) to find
extra memory
O(n)

Finding a node still costs O(n) — no indexes, same as before. But once you're holding it, deleting is O(1) instead of requiring a walk. And you can traverse in both directions. The price: an extra pointer per node.

  • O(1)
  • O(log n)
  • O(n) · this one
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Updating `next` but forgetting `prev`.

    The nastiest bug in this structure. Walking forwards still works, so everything looks fine — until someone walks backwards and falls off a broken chain.

  • Forgetting the edge cases at the head and tail.

    The head has no prev and the tail has no next. Deleting either means null-checking before you dereference, or you crash on the very first or last node.

  • Reaching for it when a singly linked list would do.

    It costs an extra pointer per node and doubles the bookkeeping. Only pay that if you actually need backward traversal or O(1) deletion of a node you already hold.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+70 XP

01What does the extra `prev` pointer buy you?

02Does a doubly linked list make *finding* a node faster?

03What's the sneakiest bug in a doubly linked list?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.