jsschools

Doubly Linked List

A linked list where each node holds pointers to both its next and previous nodes, enabling O(1) insertion and deletion at both ends.

Spec ↗

Syntax

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

Parameters

NameTypeRequiredDescription
head DNode | null No The sentinel or first real node; null for an empty list.
tail DNode | null No The last node; null for an empty list.

Returns

DoublyLinkedList — A new doubly linked list instance.

Examples

class DNode {
  constructor(val) { this.val = val; this.prev = null; this.next = null; }
}
class DoublyLinkedList {
  constructor() { this.head = null; this.tail = null; this.size = 0; }
  pushBack(val) {
    const node = new DNode(val);
    if (!this.tail) { this.head = this.tail = node; }
    else { node.prev = this.tail; this.tail.next = node; this.tail = node; }
    this.size++;
  }
  popBack() {
    if (!this.tail) return undefined;
    const val = this.tail.val;
    this.tail = this.tail.prev;
    if (this.tail) this.tail.next = null; else this.head = null;
    this.size--;
    return val;
  }
}
const dl = new DoublyLinkedList();
dl.pushBack(1); dl.pushBack(2); dl.pushBack(3);
console.log(dl.popBack());
console.log(dl.size);
Output 
3
2

// O(1) remove given reference to the node
function removeNode(list, node) {
  if (node.prev) node.prev.next = node.next; else list.head = node.next;
  if (node.next) node.next.prev = node.prev; else list.tail = node.prev;
  list.size--;
}
Output 
(no output — mutates the list in place)

Notes

| Operation | Best | Avg | Worst | Space | |-------------------|------|------|-------|-------| | Access by idx | O(n) | O(n) | O(n) | O(n) | | Insert (head/tail) | O(1) | O(1) | O(1) | O(1) | | Delete (head/tail) | O(1) | O(1) | O(1) | O(1) | | Delete (node ref) | O(1) | O(1) | O(1) | O(1) | | Search | O(1) | O(n) | O(n) | O(1) | Each node uses twice the pointer memory compared to a singly linked list. The `prev` pointer is what makes LRU Cache O(1) deletions possible — store a Map from key → node reference.

See also