Doubly Linked List

A doubly linked list adds a prev reference to every node and keeps both a head and tail pointer on the list. The two extra pointers unlock operations that a singly linked list cannot do in constant time.

Node with Prev

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
    this.prev = null;
  }
}

Dummy Sentinel Nodes

Instead of special-casing empty-list conditions on every operation, create two dummy (sentinel) nodes that act as permanent bookends.

class DoublyLinkedList {
  constructor() {
    this.dummy_head = new ListNode(-Infinity);
    this.dummy_tail = new ListNode(-Infinity);
    this.dummy_head.next = this.dummy_tail;
    this.dummy_tail.prev = this.dummy_head;
    this.size = 0;
  }
}

Real nodes are always inserted between the two sentinels. You never need to check if (!this.head) again.

Insert After a Given Node — O(1)

_insertAfter(node, newNode) {
  newNode.prev = node;
  newNode.next = node.next;
  node.next.prev = newNode;
  node.next = newNode;
  this.size++;
}

prepend(val) {
  this._insertAfter(this.dummy_head, new ListNode(val));
}

append(val) {
  this._insertAfter(this.dummy_tail.prev, new ListNode(val));
}

Both prepend and append are now O(1) because we have direct references to the sentinels.

Remove a Given Node — O(1)

This is the operation that makes doubly linked lists essential for LRU caches and similar structures. Given a reference to a node, splice it out in four pointer updates:

_remove(node) {
  node.prev.next = node.next;
  node.next.prev = node.prev;
  node.prev = null;  // help GC by dropping dangling refs
  node.next = null;
  this.size--;
  return node.val;
}

removeHead() {
  if (this.size === 0) return null;
  return this._remove(this.dummy_head.next);
}

removeTail() {
  if (this.size === 0) return null;
  return this._remove(this.dummy_tail.prev);
}

Why O(1) Removal Matters

In a singly linked list you need the previous node to remove a target node — so you must either store it yourself or walk from the head in O(n). With prev pointers, any node can be unlinked in four assignments, no traversal required. This is exactly the internal operation that powers an LRU cache’s constant-time eviction.

Operation Complexity

Up Next

Close the chain by pointing the tail back at the head to form a circular linked list.