Doubly Linked Lists

Lesson 1 of 3

A pointer in each direction

A doubly linked node holds its value, a next pointer and a prev pointer. The head's prev is empty and the tail's next is empty, which is how you know you have reached either end. Because each node knows both neighbours, the list can be walked in either direction from anywhere in it.

The immediate consequence is that a node is now self-sufficient. Given only a reference to a node, you can remove it: you have its predecessor and its successor already. On a singly linked list the same operation needs a walk from the head to find the predecessor, because the node cannot see behind itself.

Interactive lab

Doubly linked list

Insert at either end, delete a value, and walk in both directions. Each pointer write gets its own frame, with next in teal and prev in gold.

Doubly linked list

insert at head or tail O(1) · access O(n)

value

head

tail

→ next← prev

1 / 4

Start

Walking forwards from the head, following next pointers.

Continue

Lesson 2 of 3

Two writes, every time

Every link now has two halves that must agree: if A.next is B, then B.prev must be A. Step the visualizer through an insert and watch the two writes happen in separate frames. Perform only the first and the list is still walkable forwards, which is exactly why this bug survives casual testing and then corrupts a backward traversal much later.

This is the real cost of the structure, and it is not the memory. A pointer per node is cheap; an invariant that must be maintained by hand in every insert, delete and splice is not. Production implementations often use a sentinel node at each end so that no operation has to special-case an empty list or a missing neighbour.

Continue

Lesson 3 of 3

When to reach for it

Choose a doubly linked list when you need to move both ways, remove nodes you already hold a reference to, or insert at both ends cheaply. An LRU cache is the standard example: it keeps a hash map from key to node and, on every access, unlinks that node and moves it to the front. That unlink is O(1) only because the node knows its predecessor.

Stay with a singly linked list when you only ever traverse forwards and memory matters, and remember that for most everyday work a dynamic array beats both, because contiguous memory is dramatically faster to scan than pointers scattered across the heap.

Continue

Worked examples

Read the code, then change it

Copy any example into the playground and break it on purpose. That is the fastest way to learn what each line is holding up.

Insert at head, both pointersJavaScript

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  insertHead(value) {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
      this.tail = node;
      return node;
    }
    node.next = this.head;   // write 1: forwards
    this.head.prev = node;   // write 2: backwards, the one people forget
    this.head = node;
    return node;
  }

  // O(1): the node already knows both neighbours.
  unlink(node) {
    if (node.prev) node.prev.next = node.next;
    else this.head = node.next;
    if (node.next) node.next.prev = node.prev;
    else this.tail = node.prev;
    node.prev = null;
    node.next = null;
  }

  toArray(fromTail = false) {
    const out = [];
    let cursor = fromTail ? this.tail : this.head;
    while (cursor) {
      out.push(cursor.value);
      cursor = fromTail ? cursor.prev : cursor.next;
    }
    return out;
  }
}

const list = new DoublyLinkedList();
[40, 30, 20].forEach((value) => list.insertHead(value));
console.log(list.toArray());          // forwards
console.log(list.toArray(true));      // backwards, impossible when singly

Doubly Linked Lists

A pointer in each direction

Two writes, every time

When to reach for it

Read the code, then change it

Work these out yourself

Check your understanding

Finished this topic?