Linked List crash course ↗ · 122

146. LRU Cache

Design a cache that evicts the Least Recently Used entry when full. The trick: pair a Map for O(1) key lookup with a doubly-linked list for O(1) move-to-front and eviction — both get and put run in constant time.

● MediumDoubly Linked ListHash MapDesignTypeScript

PROBLEM What we're solving

Implement an LRU cache with a fixed capacity. get(key) returns the value or -1 if absent; put(key, value) inserts or updates the pair. When the cache exceeds capacity, evict the least recently used entry.

Worked example — capacity 2:

  • put(1,1) → cache: [1:1]
  • put(2,2) → cache: [2:2, 1:1] (2 is MRU)
  • get(1) → 1; cache: [1:1, 2:2] (1 promoted to MRU)
  • put(3,3) → evict key 2 (LRU); cache: [3:3, 1:1]
  • get(2) → -1 (evicted)

KEY IDEA Map the key to a node; keep nodes in recency order via a doubly-linked list

Insight → a Map<key, node> gives O(1) lookup, but a plain map has no notion of order. A doubly-linked list gives O(1) move-to-front and O(1) evict-from-tail — but only if you already hold a pointer to the node. Combining them: the map holds the pointer, the list enforces recency order. Add dummy head (MRU side) and tail (LRU side) sentinels to eliminate every null-pointer edge case.

RECIPE The four O(1) operations

  • 0 · Constructor. Allocate the Map and two dummy sentinel nodes (head ↔ tail) so the list is never truly empty — every real node lives between them.
  • 1 · get(key). Look up the node in the map. If absent return -1. Otherwise call remove(node) then insertFront(node) to promote it to MRU, and return its value.
  • 2 · put(key, value) — existing key. Retrieve the node, update its value, then move to front exactly as in get.
  • 3 · put(key, value) — new key. Create a new node, insert into the map, call insertFront. If map.size > capacity, evict by calling remove(tail.prev) and deleting its key from the map.
  • 4 · remove(node). Splice out: node.prev.next = node.next and node.next.prev = node.prev.
  • 5 · insertFront(node). Wire the node right after the dummy head. Four pointer assignments; sentinels ensure no null checks.
Classic confusion → forgetting to delete the evicted node from the map. The list eviction is invisible to get— the map is the source of truth for "is key in cache?". Skip the map.delete and stale keys silently return wrong values.

COST Complexity & alternatives

Array / sorted list
O(n)
Shifting or searching to maintain order costs O(n) per op.
Map + doubly-linked list
O(1)
O(1) get & put; O(n) space for n entries.

JavaScript's built-in Map preserves insertion order, so map.keys().next().value gives the oldest key — this lets you implement LRU without a separate linked list at the cost of code clarity. The doubly-linked list approach is canonical for interviews because it makes the O(1) argument explicit.

Pattern transfer → the same map + doubly-linked list skeleton powers LFU Cache (LC 460 — add a frequency layer), Design Twitter(ordered tweets per user), and any "sliding window of most-recent K distinct items" problem. Whenever you need O(1) ordered insert/delete + O(1) lookup, reach for this combination.

RUN IT Hash map + doubly-linked list: O(1) get & put

step 0 / 10
STARTInitialize LRU Cache with capacity 2. Dummy head (MRU side) and tail (LRU side) sentinel nodes in place.
1class LRUCache {
2  private capacity: number;
3  private map: Map<number, DLLNode>;
4  private head: DLLNode; // dummy MRU sentinel
5  private tail: DLLNode; // dummy LRU sentinel
6 
7▶  constructor(capacity: number) {
8▶    this.capacity = capacity;
9▶    this.map = new Map();
10▶    this.head = new DLLNode(0, 0);
11▶    this.tail = new DLLNode(0, 0);
12▶    this.head.next = this.tail;
13▶    this.tail.prev = this.head;
14  }
15 
16  get(key: number): number {
17    if (!this.map.has(key)) return -1;
18    const node = this.map.get(key)!;
19    this.remove(node);
20    this.insertFront(node);
21    return node.val;
22  }
23 
24  put(key: number, value: number): void {
25    if (this.map.has(key)) {
26      const node = this.map.get(key)!;
27      node.val = value;
28      this.remove(node);
29      this.insertFront(node);
30    } else {
31      const node = new DLLNode(key, value);
32      this.map.set(key, node);
33      this.insertFront(node);
34      if (this.map.size > this.capacity) {
35        const lru = this.tail.prev!;
36        this.remove(lru);
37        this.map.delete(lru.key);
38      }
39    }
40  }
41 
42  private remove(node: DLLNode): void {
43    node.prev!.next = node.next;
44    node.next!.prev = node.prev;
45  }
46 
47  private insertFront(node: DLLNode): void {
48    node.next = this.head.next;
49    node.prev = this.head;
50    this.head.next!.prev = node;
51    this.head.next = node;
52  }
53}
54 
55class DLLNode {
56  key: number;
57  val: number;
58  prev: DLLNode | null = null;
59  next: DLLNode | null = null;
60  constructor(key: number, val: number) {
61    this.key = key;
62    this.val = val;
63  }
64}
HEADTAIL
State
2
capacity
0
size
MRU / just accessedLRU endevictedcache hit result
slowfast

TYPESCRIPT The solution, annotated

lruCache.ts
class LRUCache {
  private capacity: number;
  private map: Map<number, DLLNode>;
  private head: DLLNode; // dummy MRU sentinel
  private tail: DLLNode; // dummy LRU sentinel

  constructor(capacity: number) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = new DLLNode(0, 0);
    this.tail = new DLLNode(0, 0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key: number): number {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key)!;
    this.remove(node);
    this.insertFront(node);
    return node.val;
  }

  put(key: number, value: number): void {
    if (this.map.has(key)) {
      const node = this.map.get(key)!;
      node.val = value;
      this.remove(node);
      this.insertFront(node);
    } else {
      const node = new DLLNode(key, value);
      this.map.set(key, node);
      this.insertFront(node);
      if (this.map.size > this.capacity) {
        const lru = this.tail.prev!;
        this.remove(lru);
        this.map.delete(lru.key);
      }
    }
  }

  private remove(node: DLLNode): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  private insertFront(node: DLLNode): void {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next!.prev = node;
    this.head.next = node;
  }
}

class DLLNode {
  key: number;
  val: number;
  prev: DLLNode | null = null;
  next: DLLNode | null = null;
  constructor(key: number, val: number) {
    this.key = key;
    this.val = val;
  }
}

Reading it block by block

Lines 1–14 — constructor. capacity caps the cache size. The Map maps each key to its doubly-linked list node for O(1) pointer retrieval. Dummy head and tail sentinels avoid null checks: the real entries always live between them, so remove and insertFront never need to handle empty-list edge cases.
Lines 16–22 — get. A map miss returns -1 immediately. On a hit, remove + insertFront promotes the node to the MRU position in O(1). The value is already stored in the node.
Lines 24–39 — put (existing key). Update node.val in place, then re-use the same remove + insertFront dance to refresh recency. No new node is allocated.
Lines 40–46 — put (new key) + eviction. Create a fresh node, insert it at the front (MRU), register it in the map. If map.size > capacity, the LRU node is tail.prev: remove it from the list and delete its key from the map. Critically, the map delete must happen after remove so the node's key field is still accessible.
Lines 51–62 — remove & insertFront. remove is four pointer assignments (prev.next and next.prev). insertFront splices the node immediately after the dummy head — also four assignments. Both are O(1) regardless of list length. The sentinels guarantee node.prev and node.next are never null.
Complexity → get and put are both O(1) time: the map gives O(1) pointer lookup; splice-out and splice-in are constant-time pointer rewires. Space is O(n) for n ≤ capacity entries.

INTERVIEWFollow-ups they'll ask

  • "How would you implement LFU (Least Frequently Used)?" Add a frequency counter per node and maintain a Map<freq, DoublyLinkedList>; track minFreq to find the eviction bucket in O(1).
  • "Can you do it without a custom linked list in JS/TS?" Yes — Mappreserves insertion order; delete-then-reinsert moves a key to the "end" (most recent). But this conflates insertion and access order and is less explicit about the invariant.
  • "What if the cache is accessed concurrently?" The current implementation is not thread-safe. You would need locks around getand put, or use a lock-free structure like a concurrent skip list.
  • "What are the edge cases?" Capacity of 1 (every put after the first evicts immediately); putting the same key twice (must not double-count size); get on a key that was just evicted (must return -1).
  • "Return the most recently used key?" head.next.key— O(1) because the dummy head's immediate successor is always the MRU node.

MNEMONIC The one-liner

"Map finds the node in O(1); dummy-sentinel list moves it to front or boots it from the back in O(1)."

TRIGGERS When you see ___ → reach for ___

"design a cache", evict least recently usedMap + doubly-linked list
O(1) ordered delete + O(1) lookupsentinel DLL + hash map
move-to-front on accessremove(node) then insertFront(node)
capacity exceeded → evict oldestremove(tail.prev) + map.delete

SKELETON The reusable shape

skeleton.ts
class LRUCache {
  private capacity: number;
  private map: Map<number, DLLNode>;
  private head: DLLNode; // MRU sentinel
  private tail: DLLNode; // LRU sentinel

  constructor(capacity: number) { /* init map, dummy head/tail */ }

  get(key: number): number {
    if (!this.map.has(key)) return -1;
    // move to front, return val
  }

  put(key: number, value: number): void {
    if (this.map.has(key)) { /* update + move to front */ }
    else {
      // insert new node at front
      // if over capacity, evict tail.prev + delete from map
    }
  }

  private remove(node: DLLNode): void { /* splice out */ }
  private insertFront(node: DLLNode): void { /* splice in after head */ }
}

FLASHCARDS Tap to flip

Why a doubly-linked list instead of a singly-linked list?
O(1) removal of an arbitrary node requires a pointer to the previous node. With a singly-linked list you must traverse from the head — O(n).
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 9
QUESTION 01
What is the time complexity of both get and put in the optimal LRU Cache?
QUESTION 02
With capacity 2: put(1,1); put(2,2); get(1); put(3,3); get(2) — what does the last get return?
QUESTION 03
Why are dummy head and tail sentinel nodes used?
QUESTION 04
After a successful get, the accessed node is moved to:
QUESTION 05
Which classic bug causes get to return stale data after an eviction?
QUESTION 06
Why must the list be doubly-linked rather than singly-linked?
QUESTION 07
When put is called with a key already in the cache, how many new DLLNode objects are allocated?
QUESTION 08
#146 · LRU CacheA hash map of key to doubly linked list node gives O(1) lookup; a doubly linked list with dummy head and tail gives O(1) insert and evict. Every get and put moves the accessed node to the head (MRU end).Which algorithmic approach does this primarily use?
QUESTION 09
#146 · LRU CacheA hash map of key to doubly linked list node gives O(1) lookup; a doubly linked list with dummy head and tail gives O(1) insert and evict. Every get and put moves the accessed node to the head (MRU end).Which implementation correctly solves it?