cf.completefrontend
LINKED LISTS · CORE

Doubly linked list

A linked list whose nodes link both to the next node and the previous one, so any node you hold can be removed in one step.

Time O(1) per insert or removeSpace O(n)6 practice problemsStep-through picture

The idea

In a plain linked list, each node only knows the node after it. To remove a node you need the node before it, and finding that means walking from the head. A doubly linked list gives every node two links: next and prev. Now any node you hold can unhook itself, because it knows both of its neighbors.

Most implementations add two placeholder nodes, head and tail, that always stay at the two ends. Real nodes live between them. Because every real node always has a node before and after it, adding and removing never need special cases for an empty list or for the ends.

This structure is the backbone of caches that move used items to the front, of deques (lists you can add to and remove from at both ends), and of browser-style back and forward history.

An everyday example

A train of carriages

In a train, each carriage is coupled to the one in front and the one behind. To take a carriage out of the middle, the crew uncouples it and joins its two neighbors to each other. They don't need to start at the engine and walk the whole train, because the carriage itself is attached to both of its neighbors.

How the example maps to the code
In the exampleIn the code
The engine and the last car, which never leavethe head and tail placeholders
A carriagea node with val, prev, and next
The coupling to the carriage in frontnode.prev
Joining the two neighbors directlynode.prev.next = node.next

From the slow way to doubly linked list

  1. Start with a plain linked list. Suppose you already hold a node, maybe found through a hash map, and want to remove it. You must change the next of the node before it, and the only way to find that node is to walk from the head. So removal costs O(n), even though only one link changes. An array is no better: removing from the middle shifts every later item.
  2. The walk is wasted effort, because the node before was known when the node was linked in. So store it: give every node a prev link as well as next. Now a node can reach both neighbors in one step, and removing it means joining those two neighbors to each other: node.prev.next = node.next and node.next.prev = node.prev.
  3. The two links bring new trouble at the ends. The first node's prev is null and the last node's next is null, so inserting into an empty list, removing the only node, or removing either end each needs its own branch. Four special cases for two operations is how bugs get in.
  4. Placeholders fix it. Two nodes, head and tail, sit at the ends forever and are never removed. Every real node lives between them, so every real node always has a real prev and a real next. Inserting is four link writes and removing is two, the same every time. That structure is a doubly linked list.

How it works

  1. Create the two placeholders and link them: head.next = tail and tail.prev = head.
  2. To insert a value before a node node, make added with prev = node.prev and next = node.
  3. Point the neighbors at it: node.prev.next = added and node.prev = added.
  4. To add at the back, insert before tail. To add at the front, insert before head.next.
  5. To remove node, link its neighbors to each other: node.prev.next = node.next and node.next.prev = node.prev.
  6. To read the list, walk from head.next until you reach tail.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. class DoublyLinkedList {
  2. constructor() {
  3. this.head = { val: null, prev: null, next: null };
  4. this.tail = { val: null, prev: this.head, next: null };
  5. this.head.next = this.tail;
  6. this.size = 0;
  7. }
  9. insertBefore(node, val) {
  10. const added = { val, prev: node.prev, next: node };
  11. node.prev.next = added;
  12. node.prev = added;
  13. this.size++;
  14. return added;
  15. }
  17. pushBack(val) {
  18. return this.insertBefore(this.tail, val);
  19. }
  21. pushFront(val) {
  22. return this.insertBefore(this.head.next, val);
  23. }
  25. remove(node) {
  26. node.prev.next = node.next;
  27. node.next.prev = node.prev;
  28. this.size--;
  29. return node.val;
  30. }
  32. toArray() {
  33. const values = [];
  34. for (let node = this.head.next; node !== this.tail; node = node.next) values.push(node.val);
  35. return values;
  36. }
  37. }

How fast it is

TimeO(1) per insert or remove
Extra memoryO(n)

Insert and remove change at most four links and never walk the list. Reading every value with toArray is O(n). Each of the n nodes stores its value and two links.

  • Best caseO(1)

    pushBack, pushFront, insertBefore, or remove on a node you already hold: at most four link writes and no walk.

  • Average caseO(1)

    Any mix of inserts and removes at the ends or next to held nodes, as in a cache that moves a used item to the front.

  • Worst caseO(n)

    You need a node by value or position and don't hold it, or you call toArray: both walk the list from head.next.

Common mistakes

  • Updating only one direction of links. The list then looks different when walked forward and backward.
  • Running node.prev = added before node.prev.next = added. By then node.prev is already the new node, so the old neighbor never learns about it.
  • Removing a placeholder by mistake, for example popping from an empty list. Check size before removing from an end.
  • Using a doubly linked list where an array works. If you only add and remove at the end, a plain array is simpler and faster.

When to use it

Look for these clues in a problem:

  • You need to remove an item from the middle in O(1) time when you already hold it, for example after finding it in a hash map.
  • Items must be added or removed at both ends.
  • You move back and forward through a sequence, like browser history or a text cursor.
  • The task asks for a cache or list where a used item moves to the front.

Check yourself

Answer each one in your head first, then open it.

Why must node.prev.next = added run before node.prev = added?

After node.prev = added, node.prev is the new node, so the other line would set added.next = added and the old neighbor would never point to the new node.

How many links does remove write, and why does it need no search?

Two: node.prev.next and node.next.prev. The node already knows both neighbors, so nothing has to be found.

What would break without the head and tail placeholders?

The first and last real nodes would have null neighbors, so inserting into an empty list and removing an end node would each need their own branch to avoid reading null.

Why does an LRU cache need both a Map and this list?

The map finds a key's node in O(1) but can't tell you which key was used least recently. The list keeps that order, and moves or removes a held node in O(1).

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 6 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Every operation keeps one rule: starting at head and following next reaches tail, and for every node x on the way except tail, x.next.prev === x. In other words, the forward chain and the backward chain are the same chain. size counts the real nodes on it. The constructor makes it true with head.next = tail and tail.prev = head.

insertBefore(node, val) places added between P = node.prev and node. It sets added.prev = P and added.next = node when it creates the node, then P.next = added and node.prev = added. Those are all four links between the two pairs P, added and added, node, so the rule holds again. Line 11 must run before line 12, because line 12 changes what node.prev means.

remove(node) joins its two neighbors, P and N, with P.next = N and N.prev = P, so the pair P, N satisfies the rule and node is no longer on the chain. Because head and tail are never removed, a real node's prev and next are never null, so neither operation can read a property of null.

Going deeper

3 more ideas

Why the placeholders remove special cases

Without placeholders, adding to an empty list, removing the only node, or removing the first or last node each need their own code, because one of the neighbors would be null. With head and tail always present, every real node has a real prev and next, so insert and remove are each the same four or two lines every time.

Cost

Insert and remove change a fixed number of links, so they are O(1). Finding a node by value is still O(n), which is why caches pair the list with a hash map from key to node: the map finds the node in O(1), and the list removes or moves it in O(1). Each node stores two links, so it uses a bit more memory than a plain linked list.

Keep both directions in sync

Every change must update links in both directions. If you set node.prev.next but forget node.next.prev, walking forward looks correct but walking backward still reaches the removed node. A good self-check: after any change, for every node x, x.next.prev === x.

Work it by hand

Every step in a table, with why

Run six calls on a new list and watch the links written by each one. Reading the list in both directions shows that the two kinds of links agree.

pushBack(4), pushFront(9), pushBack(6), insertBefore(node6, 2), remove(node4), remove(node9)

StepCallNeighbor links writtenForward from headBackward from tailsizeWhy
1pushBack(4)head.next = 4, tail.prev = 4441pushBack inserts before tail. The new node gets prev = head and next = tail, then both placeholders point to it.
2pushFront(9)head.next = 9, 4.prev = 99, 44, 92pushFront inserts before head.next, which is 4. No branch was needed even though 9 becomes the first real node.
3pushBack(6)4.next = 6, tail.prev = 69, 4, 66, 4, 93The new node takes tail.prev, which is 4, as its own prev, before tail.prev is changed.
4insertBefore(node6, 2)4.next = 2, 6.prev = 29, 4, 2, 66, 2, 4, 94Inserting in the middle uses the same lines. node.prev.next runs first, while node.prev is still 4.
5remove(node4)9.next = 2, 2.prev = 99, 2, 66, 2, 934 knows both neighbors, so removing it is two writes and no search. It returns 4.
6remove(node9)head.next = 2, 2.prev = head2, 66, 22Removing the first real node is no different, because its prev is the head placeholder, not null.

toArray() returns [2, 6] and size is 2. After every call, walking forward and walking backward gave the same nodes in opposite order, which means both directions of links were updated.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Doubly linked listO(1)O(n)You remove or move nodes you already hold, or add and remove at both ends, and need each step to be constant time.
Singly linked listO(n)O(n)You only add or remove at the front or right after a node you hold. It uses one fewer link per node.
Array with spliceO(n)O(n)Changes are rare and you need fast access by index or tight memory. Each middle insert or remove shifts items.
Map insertion orderO(1)O(n)In JavaScript, a cache can delete and re-set a key to move it to the end of a Map, which avoids writing the list yourself.

Extra memory: O(n): each of the n nodes stores its value and two links, plus two placeholder nodes. That is one more link per node than a plain linked list.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Doubly linked list and the other approaches, on a scale where each line up is 10 times more steps.
  • Doubly linked list, Map insertion order O(1)
  • Singly linked list, Array with splice O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Doubly linked list111
Singly linked list101,0001 million
Array with splice101,0001 million
Map insertion order111

Inputs that need care

5 tricky inputs
Removing from an empty list: remove(list.head.next)
head.next is the tail placeholder, so the code sets head.next = null and then throws a TypeError on null.prev. The list is already broken by then. Check size > 0 before removing from an end.
Removing the same node twice
The removed node still has its old prev and next. The second call rewrites links that are already correct but still lowers size: on [1, 2, 3], removing 2 twice leaves [1, 3] with size = 1. Clear node.prev and node.next after removing, or track whether the node is still in a list.
Removing the only real node
Its neighbors are head and tail, so the two writes link the placeholders back together. The list is empty again with no special code.
insertBefore(list.head, value)
head.prev is null, so node.prev.next throws. Only real nodes and tail are valid targets for insertBefore.
A node that belongs to a different list
The links are rewired correctly in the other list, but this.size changes in the wrong list. Keep track of which list owns each node.

Variations and follow-ups

Twists interviewers add

Least recently used cache

Pair a Map from key to node with this list. A read finds the node in the map, removes it, and inserts it after head, so the most recently used item is first. When the cache is full, remove tail.prev, the least recently used node, and delete its key from the map. Every operation is O(1).

Deque

With pushFront, pushBack, and remove(head.next) or remove(tail.prev), the list becomes a double-ended queue: add and remove at both ends in O(1), with no array shifting.

Circular list with one placeholder

Use a single placeholder whose next is the first real node and whose prev is the last. The list is a ring, and inserting at either end is insertBefore(placeholder.next) or insertBefore(placeholder).

Move to front

Many structures need "take this node and put it first". That is remove(node) followed by inserting the same node before head.next. Reusing the node object keeps any map entries that point at it valid.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "remove in O(1)", "move to the front", "least recently used", "add and remove at both ends", or "back and forward" navigation.
  • Explain the placeholders first: "head and tail are never removed, so every real node has two real neighbors, and insert and remove need no special cases." Interviewers often ask why there are no null checks.
  • Write insertBefore with care and say the order out loud: link the new node to both neighbors, then make node.prev.next point to it, then change node.prev.
  • Test by hand: insert into an empty list, remove the only node, then insert again. Check x.next.prev === x on every node after each step.
  • Expect the follow-up "build an LRU cache". Pair a Map from key to node with this list, move a node to the front on every read, and evict tail.prev when full.

Where frontend code uses it

The same idea in real UI code
  • DOM nodes are doubly linked among their siblings: previousSibling and nextSibling let node.remove() unhook a node without scanning its parent's children.
  • Least recently used caches, such as one for decoded images or fetched pages, pair a Map with a doubly linked list (or rely on the Map's own insertion order) to move and evict entries in O(1).
  • Browser-style back and forward history, and an editor's text cursor that moves left and right, are naturally a doubly linked list or two stacks.

Related algorithms