# Doubly Linked Lists

> Bidirectional node chain — O(1) insert/delete at both ends, backward traversal included.

- **Category**: Data Structures
- **Subcategory**: Sequential Access
- **Canonical URL**: https://designpattern.fyi/patterns/doubly-linked-lists/

---

## Description
Clean, reusable architecture pattern.


## Use Cases
LRU Cache — hash map gives O(1) lookup, doubly linked list gives O(1) eviction of the least recently used node. Browser history — back and forward navigation. Text editor cursor movement — character nodes with prev/next for O(1) insert at cursor position.



## Implementation Example

```javascript
class DLNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

// Doubly Linked List with sentinel head/tail (cleaner edge-case handling)
class DoublyLinkedList {
  constructor() {
    // Dummy sentinels — never removed, simplify all insertions/deletions
    this.head = new DLNode(null, null); // Sentinel head
    this.tail = new DLNode(null, null); // Sentinel tail
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.size = 0;
  }

  // O(1) — Insert node right after head sentinel (most-recently-used position)
  insertFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
    this.size++;
  }

  // O(1) — Remove any node given its pointer (no traversal)
  remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = null;
    node.next = null;
    this.size--;
  }

  // O(1) — Remove the node just before tail sentinel (least-recently-used)
  removeLast() {
    if (this.tail.prev === this.head) return null; // Empty
    const node = this.tail.prev;
    this.remove(node);
    return node;
  }
}

// ─── LRU Cache built on DLL + HashMap ─────────────────────────
class LRUCache {
  #capacity;
  #map = new Map();  // key → node  (O(1) lookup)
  #list = new DoublyLinkedList(); // ordered by recency

  constructor(capacity) { this.#capacity = capacity; }

  // O(1) — Get and mark as most recently used
  get(key) {
    if (!this.#map.has(key)) return -1;
    const node = this.#map.get(key);
    this.#list.remove(node);      // Splice out
    this.#list.insertFront(node); // Move to front (most recent)
    return node.value;
  }

  // O(1) — Put and evict LRU if over capacity
  put(key, value) {
    if (this.#map.has(key)) {
      this.#list.remove(this.#map.get(key));
    } else if (this.#list.size === this.#capacity) {
      const lru = this.#list.removeLast(); // Evict least recently used
      this.#map.delete(lru.key);
    }
    const node = new DLNode(key, value);
    this.#list.insertFront(node);
    this.#map.set(key, node);
  }
}

const cache = new LRUCache(3);
cache.put('a', 1); cache.put('b', 2); cache.put('c', 3);
cache.get('a');    // Moves 'a' to front
cache.put('d', 4); // Evicts 'b' (LRU) — cache is now {a,c,d}

```



## Trade-offs


### Advantages

- O(1) insert and delete at both ends — not just the head

- O(1) node removal given a direct node pointer (no traversal needed)

- Bidirectional traversal — iterate forwards and backwards

- Sentinel nodes eliminate null-check complexity in implementation




### Considerations & Drawbacks

- Double the pointer overhead — 16 bytes per node (next + prev on 64-bit) vs 8 bytes for singly linked

- More complex to implement correctly — four pointer updates per insertion

- Still O(n) for index-based access and search by value

- Scattered heap allocation — worse cache performance than arrays







---
**Reference**: [Original Source](https://www.bigocheatsheet.com)