146. LRU Cache

Design a Least Recently Used cache with a fixed capacity. get(key) returns the value or −1; put(key, value) inserts or updates, evicting the least recently used key when over capacity. Both must run in O(1).

A doubly linked list keeps usage order (head = most recent, tail = least recent) and a hash map finds any node in O(1). Touching a node unlinks it and reinserts it after head.

1class Node { prev: Node | null = null; next: Node | null = null; constructor(public key = 0, public val = 0) {} }
2class LRUCache {
3  map = new Map<number, Node>(); head = new Node(); tail = new Node();
4  constructor(private capacity: number) { this.head.next = this.tail; this.tail.prev = this.head; }
5  private unlink(n: Node) { n.prev!.next = n.next; n.next!.prev = n.prev; }
6  private addFront(n: Node) { n.next = this.head.next; n.prev = this.head; this.head.next!.prev = n; this.head.next = n; }
7  get(key: number): number {
8    const n = this.map.get(key);
9    if (!n) return -1;
10    this.unlink(n); this.addFront(n);
11    return n.val;
12  }
13  put(key: number, value: number): void {
14    const old = this.map.get(key);
15    if (old) this.unlink(old);
16    const n = new Node(key, value);
17    this.map.set(key, n); this.addFront(n);
18    if (this.map.size > this.capacity) {
19      const lru = this.tail.prev!;
20      this.unlink(lru); this.map.delete(lru.key);
21    }
22  }
23}

op = LRUCache(2)capacity = 2size = 0

usage list (head = most recent)

→

→ ∅

output

null

Capacity 2. Sentinel head H and tail T.

1 / 0

Space: play/pause · ←/→: step