Doubly Linked List

A doubly linked list is a linked list where every node holds two pointers — one to the next node and one to the previous node. That single addition unlocks backward traversal and makes several operations that cost O(n) in a singly linked list drop to O(1).

Structure of a node

Node layout

Text

┌──────┬───────┬──────┐
│ prev │  val  │ next │
└──────┴───────┴──────┘
   │               │
   ▼               ▼
 prev            next
 node            node

A 4-node doubly linked list

Text

null ◀─┬──────┬─▶ ┌──────┐ ◀─▶ ┌──────┐ ◀─▶ ┌──────┐ ◀─┬──────┬─▶ null
       │  10  │    │  20  │     │  30  │     │  40  │    │  40  │
       └──────┘    └──────┘     └──────┘     └──────┘    └──────┘
          ▲                                                  ▲
         head                                              tail

The list maintains a head pointer (first node) and a tail pointer (last node). Both insertions at the ends are O(1) because we have direct references to both ends. Deletion of a node whose reference we already hold is also O(1) because we can reach both neighbors directly via prev and next.

Singly vs doubly linked list

Property	Singly Linked	Doubly Linked
Pointers per node	1 (next)	2 (prev + next)
Memory per node	Lower	Higher (one extra pointer)
Insert at head	O(1)	O(1)
Insert at tail (with tail ptr)	O(1)	O(1)
Delete by value	O(n)	O(n)
Delete node by reference	O(n) — must find prev	O(1) — prev is stored
Traverse forward	O(n)	O(n)
Traverse backward	Not possible	O(n)
Typical use cases	Simple stacks/queues	LRU cache, browser history, deque

Implementing the Node class

Node

class Node {
  constructor(val) {
    this.val = val;
    this.prev = null; // pointer to the previous node
    this.next = null; // pointer to the next node
  }
}

Full DoublyLinkedList implementation

DoublyLinkedList — skeleton

class DoublyLinkedList {
  constructor() {
    this.head = null; // first node
    this.tail = null; // last node
    this.size = 0;
  }
}

Insert at head — O(1)

To insert at the head we create a new node, point its next at the current head, and update the current head's prev to point back at the new node. Then we reassign head. If the list is empty the new node becomes both head and tail.

insertAtHead

insertAtHead(val) {
  const node = new Node(val);

  if (this.head === null) {
    // list is empty — node is both head and tail
    this.head = node;
    this.tail = node;
  } else {
    node.next = this.head; // new node points forward to old head
    this.head.prev = node; // old head points back to new node
    this.head = node;       // head moves to new node
  }

  this.size++;
  return this;
}

Insert at tail — O(1)

insertAtTail

insertAtTail(val) {
  const node = new Node(val);

  if (this.tail === null) {
    this.head = node;
    this.tail = node;
  } else {
    node.prev = this.tail; // new node points back to old tail
    this.tail.next = node; // old tail points forward to new node
    this.tail = node;       // tail moves to new node
  }

  this.size++;
  return this;
}

Insert after a given node — O(1)

When you already have a reference to a node, inserting immediately after it is O(1) — no traversal needed. This is one of the key advantages over an array (which would require shifting elements).

insertAfter

// nodeRef must be an actual Node object in this list
insertAfter(nodeRef, val) {
  if (nodeRef === null) throw new Error('nodeRef is null');

  // Special case: inserting after the tail is the same as insertAtTail
  if (nodeRef === this.tail) {
    return this.insertAtTail(val);
  }

  const node = new Node(val);
  const successor = nodeRef.next; // the node currently after nodeRef

  // Wire up the new node
  node.prev = nodeRef;     // new node's prev → nodeRef
  node.next = successor;   // new node's next → successor

  // Wire up neighbors
  nodeRef.next = node;     // nodeRef now points to new node
  successor.prev = node;   // successor now points back to new node

  this.size++;
  return this;
}

Delete by value — O(n)

We must traverse to find the node. Once found, removal is O(1) because we have prev and next directly on the node.

deleteByValue

deleteByValue(val) {
  if (this.head === null) return false; // empty list

  let current = this.head;

  while (current !== null) {
    if (current.val === val) {
      this._unlink(current);
      return true; // deleted
    }
    current = current.next;
  }

  return false; // value not found
}

Delete node by reference — O(1)

If you already hold a reference to the node (as you do in an LRU cache, for example), you can remove it in constant time. This is the core reason doubly linked lists power LRU caches.

_unlink (internal helper)

// Removes a node from the list given a direct reference.
// Called by both deleteByValue and deleteNode.
_unlink(node) {
  const prev = node.prev;
  const next = node.next;

  if (prev !== null) {
    prev.next = next; // skip over the node
  } else {
    // node is the head
    this.head = next;
  }

  if (next !== null) {
    next.prev = prev; // skip over the node
  } else {
    // node is the tail
    this.tail = prev;
  }

  // Clean up dangling pointers (good practice)
  node.prev = null;
  node.next = null;

  this.size--;
}

deleteNode(nodeRef) {
  if (nodeRef === null) return;
  this._unlink(nodeRef);
}

Traversal — forward and backward

toArray / toArrayReverse

// Forward traversal — O(n)
toArray() {
  const result = [];
  let current = this.head;
  while (current !== null) {
    result.push(current.val);
    current = current.next;
  }
  return result;
}

// Backward traversal — O(n), only possible because of prev pointers
toArrayReverse() {
  const result = [];
  let current = this.tail;
  while (current !== null) {
    result.push(current.val);
    current = current.prev;
  }
  return result;
}

Complete implementation (copy-paste ready)

DoublyLinkedList — full

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

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

  // --- Insertion ---

  insertAtHead(val) {
    const node = new Node(val);
    if (this.head === null) {
      this.head = node;
      this.tail = node;
    } else {
      node.next = this.head;
      this.head.prev = node;
      this.head = node;
    }
    this.size++;
    return this;
  }

  insertAtTail(val) {
    const node = new Node(val);
    if (this.tail === null) {
      this.head = node;
      this.tail = node;
    } else {
      node.prev = this.tail;
      this.tail.next = node;
      this.tail = node;
    }
    this.size++;
    return this;
  }

  insertAfter(nodeRef, val) {
    if (nodeRef === null) throw new Error('nodeRef is null');
    if (nodeRef === this.tail) return this.insertAtTail(val);

    const node = new Node(val);
    const successor = nodeRef.next;

    node.prev = nodeRef;
    node.next = successor;
    nodeRef.next = node;
    successor.prev = node;

    this.size++;
    return this;
  }

  // --- Deletion ---

  _unlink(node) {
    const prev = node.prev;
    const next = node.next;

    if (prev !== null) prev.next = next;
    else this.head = next;

    if (next !== null) next.prev = prev;
    else this.tail = prev;

    node.prev = null;
    node.next = null;
    this.size--;
  }

  deleteByValue(val) {
    let current = this.head;
    while (current !== null) {
      if (current.val === val) {
        this._unlink(current);
        return true;
      }
      current = current.next;
    }
    return false;
  }

  deleteNode(nodeRef) {
    if (nodeRef !== null) this._unlink(nodeRef);
  }

  // --- Traversal ---

  toArray() {
    const result = [];
    let current = this.head;
    while (current !== null) {
      result.push(current.val);
      current = current.next;
    }
    return result;
  }

  toArrayReverse() {
    const result = [];
    let current = this.tail;
    while (current !== null) {
      result.push(current.val);
      current = current.prev;
    }
    return result;
  }

  // Convenience
  get length() { return this.size; }
}

Usage example

Usage

const dll = new DoublyLinkedList();

dll.insertAtTail(10)
   .insertAtTail(20)
   .insertAtTail(30)
   .insertAtHead(5);

console.log(dll.toArray());        // [5, 10, 20, 30]
console.log(dll.toArrayReverse()); // [30, 20, 10, 5]

// Insert 15 after the node holding 10
let cur = dll.head;
while (cur && cur.val !== 10) cur = cur.next;
dll.insertAfter(cur, 15);

console.log(dll.toArray()); // [5, 10, 15, 20, 30]

dll.deleteByValue(15);
console.log(dll.toArray()); // [5, 10, 20, 30]

// O(1) delete with a reference
dll.deleteNode(dll.head);   // remove head (5)
console.log(dll.toArray()); // [10, 20, 30]

Complexity summary

Operation	Time	Notes
Insert at head	O(1)	Direct head pointer update
Insert at tail	O(1)	Direct tail pointer update
Insert after node (by ref)	O(1)	No traversal needed
Delete node (by ref)	O(1)	prev/next on the node
Delete by value	O(n)	Must scan to find the node
Search	O(n)	No random access
Traverse forward	O(n)	Follow next pointers
Traverse backward	O(n)	Follow prev pointers
Space	O(n)	Two pointers per node vs one

Real-world use cases

Browser history (back / forward)

Each visited page is a node. The current page is a pointer into the list. Pressing Back follows prev; pressing Forward follows next. Navigating to a new URL while in the middle discards everything after the current node — equivalent to chopping off the tail.

BrowserHistory backed by a doubly linked list

class BrowserHistory {
  constructor(homepage) {
    this.current = new Node(homepage);
  }

  visit(url) {
    const node = new Node(url);
    node.prev = this.current;
    this.current.next = node; // discard old forward history
    this.current = node;
  }

  back(steps) {
    while (steps > 0 && this.current.prev !== null) {
      this.current = this.current.prev;
      steps--;
    }
    return this.current.val;
  }

  forward(steps) {
    while (steps > 0 && this.current.next !== null) {
      this.current = this.current.next;
      steps--;
    }
    return this.current.val;
  }
}

const h = new BrowserHistory('google.com');
h.visit('github.com');
h.visit('leetcode.com');
console.log(h.back(1));    // github.com
console.log(h.back(1));    // google.com
console.log(h.forward(1)); // github.com

LRU Cache — O(1) get and put

An LRU (Least Recently Used) cache evicts the least recently accessed item when capacity is reached. A doubly linked list combined with a hash map achieves O(1) for both get and put:

Hash map — key → node reference, for O(1) lookup.
Doubly linked list — orders items by recency; most recent at the head.
On get: move the accessed node to the head in O(1) via _unlink + insertAtHead.
On put when full: remove the tail node (least recently used) in O(1).

LRUCache

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();       // key → node
    this.list = new DoublyLinkedList();
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    // Move to head (most recently used)
    this.list.deleteNode(node);
    this.list.insertAtHead(node.val);
    // Update the map to point to the new head node
    this.map.set(key, this.list.head);
    return node.val.value;
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.list.deleteNode(this.map.get(key));
    } else if (this.list.size >= this.capacity) {
      // Evict LRU (tail)
      const lru = this.list.tail;
      this.map.delete(lru.val.key);
      this.list.deleteNode(lru);
    }
    this.list.insertAtHead({ key, value });
    this.map.set(key, this.list.head);
  }
}

Text editor cursor

Many text editors model a document as a doubly linked list of lines (or characters). The cursor position is a pointer into the list. Inserting a character is O(1) at the cursor; deleting is O(1). Undo/redo is implemented by maintaining a separate history list of edit nodes.

When to prefer an array over a doubly linked list

If your workload is mostly random access by index (e.g., jump to line 500), arrays win — O(1) vs O(n). Doubly linked lists shine when you need frequent insertions and deletions at arbitrary positions given a reference, and when you need to traverse in both directions.

Tip

In competitive programming, doubly linked lists appear in problems that ask for "remove element, then do something with its neighbors" — the classic pattern is to keep node references in a separate array for O(1) deletion.

Key takeaways

Every node stores prev and next — the only structural difference from a singly linked list.
Inserting at head or tail is O(1) with maintained head/tail pointers.
Deleting a node whose reference you hold is O(1) — the killer feature vs singly linked lists.
Backward traversal is possible; singly linked lists cannot go backward.
The extra pointer doubles the per-node memory overhead compared to singly linked.
LRU cache and browser history are the two canonical interview problems that use doubly linked lists.