↩ back to Linear

Doubly Linked List

A singly linked list gives each node one pointer: next. A doubly linked list gives it two: next and prev. That one extra pointer per node looks like a small change, but it buys two things a singly linked list can't do at all — walk the chain backward from the tail, and unlink any node you already have a reference to in O(1), with no search required first.

That second point is the real payoff, and it's worth being precise about why the singly linked version can't match it. Given a direct reference to some node n in a singly linked list, removing n still means finding its predecessor — the node whose next currently points at n — and the only way to find that predecessor is to walk from the head comparing curr.next === n until it matches. The node you're deleting doesn't know who points at it. A doubly linked node does: n.prev is the predecessor, already in hand, no walk needed. See Pitfalls for the classic trick that tries to fake this in a singly linked list, and exactly where it breaks.

Try it

Insert at the front or back, delete a value by walking from the head, or fetch a node by index — watch which end get starts from. Every node also has a × that removes it directly, no search: that's the operation a hash map + doubly linked list combination leans on for O(1) eviction.

Core operations

• insertFront(x) / insertBack(x) — same as a singly linked list, O(1), except now the new node's neighbor also needs its prev pointer fixed up, not just its next.
• getNodeAt(i) — walk from whichever end is closer: from the head if i < size / 2, otherwise backward from the tail. Still O(n) worst case (the middle is still size/2 hops from either end), but it's a real option a singly linked list simply doesn't have — that one only ever has a way in from the head.
• findValue(x) — walk forward from the head comparing values, O(n), identical to the singly linked version; knowing where a value is ahead of time isn't possible, so there's no "closer end" to start from here the way there is for an index.
• removeNode(node) — given a direct reference, relink node.prev.next and node.next.prev around it (or fix up the head/tail pointer if node was an end). O(1), full stop, no search of any kind — this is the operation the intro paragraph is about.
• deleteValue(x) — findValue(x) then removeNode on what it returns. O(n) overall, same as a singly linked list: having prev pointers doesn't help you find x any faster, only remove it faster once found.

Reference implementation

class DoublyLinkedList {
  #head = null;
  #tail = null;
  #size = 0;

  get size() { return this.#size; }
  isEmpty() { return this.#size === 0; }

  insertFront(x) {
    const node = { value: x, prev: null, next: this.#head };
    if (this.#head !== null) this.#head.prev = node;
    this.#head = node;
    if (this.#tail === null) this.#tail = node;
    this.#size++;
    return node;
  }

  insertBack(x) {
    const node = { value: x, prev: this.#tail, next: null };
    if (this.#tail !== null) this.#tail.next = node;
    this.#tail = node;
    if (this.#head === null) this.#head = node;
    this.#size++;
    return node;
  }

  getNodeAt(i) {
    if (i < 0 || i >= this.#size) return null;
    if (i < this.#size / 2) {
      let curr = this.#head, hops = 0;
      for (let k = 0; k < i; k++) { curr = curr.next; hops++; }
      return { node: curr, hops, from: 'head' };
    } else {
      let curr = this.#tail, hops = 0;
      for (let k = this.#size - 1; k > i; k--) { curr = curr.prev; hops++; }
      return { node: curr, hops, from: 'tail' };
    }
  }

  findValue(x) {
    let curr = this.#head, i = 0;
    while (curr !== null) {
      if (curr.value === x) return { node: curr, index: i };
      curr = curr.next;
      i++;
    }
    return null;
  }

  removeNode(node) {
    if (node.prev !== null) node.prev.next = node.next;
    else this.#head = node.next; // node was the head
    if (node.next !== null) node.next.prev = node.prev;
    else this.#tail = node.prev; // node was the tail
    node.prev = node.next = null;
    this.#size--;
  }

  deleteValue(x) {
    const found = this.findValue(x);
    if (found === null) return false;
    this.removeNode(found.node);
    return true;
  }
}

removeNode is the whole point of the structure: four pointer fix-ups (two on each live neighbor, or a head/tail pointer if there wasn't one) and nothing else, regardless of where in the list node sits or how large the list is. Verified against a plain-array model over 30,000 randomized operations — inserts, deletes by value, direct removeNode calls by reference, and getNodeAt calls checked for both the returned value and the exact expected hop count and starting end — plus the getNodeAt hop counts for a 5-node list by hand (index 0: 0 hops from head; index 2: 2 hops from head; index 4: 0 hops from tail). See /tmp/dll_test/verify.js, not committed, it's scratch.

Pitfalls

The "copy trick" doesn't actually give a singly linked list O(1) deletion. A common trick for faking O(1) removal of a node n you have a reference to, without a prev pointer: copy n.next's value into n, then splice out n.next instead of n itself — the list ends up one node shorter and missing the right value, without ever walking from the head. It works right up until n is the last node: there's no n.next to copy from, so the trick has nothing to fall back on. Confirmed directly: running it on a middle node of a 3-node chain (1 → 2 → 3) correctly produces 1 → 3, but running it on the tail node returns false and leaves the chain untouched — there's no way to satisfy the caller's request without an actual predecessor reference, which is exactly what prev provides unconditionally.

Only relinking one direction. Every insert and delete now touches two pointers per affected neighbor, not one. Fixing up next but forgetting the new or surviving neighbor's prev (or vice versa) leaves the list looking correct when walked forward but broken when walked backward — a bug that a test suite checking only toArray() from the head would never catch. The stress test above checks a tail-to-head walk after every single operation for exactly this reason, not just a head-to-tail one.

Where doubly linked lists show up

• LRU caches. The hash map stores node references directly, so evicting or promoting an entry is a removeNode call on a node the map already handed back — no search, which is exactly why the eviction is O(1) instead of O(n).
• Undo/redo history and browser back/forward. The current position is a node with a real neighbor in both directions; moving back or forward is one pointer hop either way, not a walk from a fixed end.
• Deques. A double-ended queue needs O(1) push/pop at both ends and, for some implementations, O(1) removal of an arbitrary element by reference — a doubly linked list is a natural backing structure for exactly that combination.

Complexity

Time: insertFront and insertBack are O(1). removeNode given a reference is O(1) — the structure's whole reason to exist. findValue and deleteValue are O(n), no better than a singly linked list, since there's still no way to know where a value lives without looking. getNodeAt(i) is O(min(i, size − i)): still linear, but never worse than half the list. Space: O(n) for n nodes, plus two pointers per node instead of one — the structure's one real cost, paid on every node whether or not backward traversal or O(1) removal-by-reference ever gets used.

This site's guide, Choosing a Linear Data Structure, compares this entry against the other six Linear structures side by side.