Doubly Linked List Template
A doubly linked list adds a `prev` pointer to every node, which unlocks O(1) removal of a known node and O(1) traversal in both directions. This is the structural backbone of LRU caches, browser back / forward stacks, and skip-list-adjacent designs. This snippet covers the Node + List skeleton with sentinel head and tail, the unlink-known-node operation that makes LRU possible, and a forward / backward iteration helper.
257 views
7
class DLNode {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = new DLNode(null);
this.tail = new DLNode(null);
this.head.next = this.tail;
this.tail.prev = this.head;
this.size = 0;
}
pushBack(value) {
const node = new DLNode(value);
node.prev = this.tail.prev;
node.next = this.tail;
this.tail.prev.next = node;
this.tail.prev = node;
this.size++;
return node;
}
toArray() {
const out = [];
for (let n = this.head.next; n !== this.tail; n = n.next) out.push(n.value);
return out;
}
}
const d = new DoublyLinkedList();
d.pushBack(1); d.pushBack(2); d.pushBack(3);
console.log(d.toArray()); // [1, 2, 3]Sentinel head and tail nodes (with value: null) eliminate every 'is this the first or last node?' branch from the rest of the API. Insert and remove both become four pointer assignments with no special cases. The trade-off is two extra nodes in memory, which is negligible for any list big enough to care about doubly-linked semantics. Returning the inserted node from pushBack lets callers cache a handle for O(1) removal later, which is the operation LRU caches depend on.
class DLN { constructor(v) { this.value = v; this.prev = null; this.next = null; } }
function unlink(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = null;
node.next = null;
return node;
}
// Build a tiny list and remove the middle node.
const sentinel = new DLN(null);
const a = new DLN('a'), b = new DLN('b'), c = new DLN('c');
sentinel.next = a; a.prev = sentinel;
a.next = b; b.prev = a;
b.next = c; c.prev = b;
c.next = sentinel; sentinel.prev = c;
unlink(b);
const out = [];
for (let n = sentinel.next; n !== sentinel; n = n.next) out.push(n.value);
console.log(out); // ['a', 'c']When you already have a reference to the node (e.g. from a Map<key, node> index), removal is four pointer reassignments and runs in O(1). The doubly linked structure is what makes this possible: a singly linked list cannot remove a known node without scanning to find its predecessor. Pair this with a hash table that maps keys to nodes and you have the kernel of an LRU cache (see the dedicated LRU template entry for the full story). Setting the removed node's prev / next to null is bookkeeping that helps GC and prevents accidental traversal.
class DLN2 { constructor(v) { this.value = v; this.prev = null; this.next = null; } }
function* iterateForward(head, tail) {
for (let n = head.next; n !== tail; n = n.next) yield n.value;
}
function* iterateBackward(head, tail) {
for (let n = tail.prev; n !== head; n = n.prev) yield n.value;
}
const h = new DLN2(null), t = new DLN2(null);
h.next = t; t.prev = h;
for (const v of [10, 20, 30]) {
const n = new DLN2(v);
n.prev = t.prev; n.next = t;
t.prev.next = n; t.prev = n;
}
console.log([...iterateForward(h, t)]); // [10, 20, 30]
console.log([...iterateBackward(h, t)]); // [30, 20, 10]Walking the list backwards is the second feature that comes free with a doubly linked structure. Wrapping each direction in a generator lets callers use for..of, spread, or destructuring without exposing the raw nodes. This is useful for editor cursors (next / previous word), browser history (back / forward), and any sequence where the user can traverse both ways. The same generators work for partial walks (start / end at any non-sentinel node), since the loop condition is just 'not the sentinel'.