JavaScript Snippet

Doubly Linked List Template

Difficulty: Medium

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.

Code Snippets
/

Doubly Linked List Template

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.

JavaScript
Medium
3 snippets
data-structures
linked-list
code-template
algorithms

256 views

7

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.