coding problems · high

LRU Cache: Hash Map + Doubly-Linked List

Watch get() promote a node to the front and put() evict the least-recently-used tail - every operation O(1).

The code

LRUCache cache(3);

cache.put(1, 'A');
cache.put(2, 'B');
cache.put(3, 'C');
cache.get(1);        // hit  -> promote key 1
cache.put(4, 'D');   // full -> evict LRU (key 2)
cache.get(2);        // miss -> key 2 was evicted

What this lesson walks through

1. 01LRU = hash map + doubly-linked list
2. 02put(1, A)
3. 03put(2, B) - new node at front
4. 04put(3, C) - cache is now full
5. 05get(1) - hit, promote to front
6. 06put(4, D) - full, evict the LRU
7. 07Evicted 2, inserted 4 at front
8. 08get(2) - miss (it was evicted)

An LRU cache pairs a hash map (O(1) key -> node lookup) with a doubly-linked list that tracks recency: the front is most-recently-used, the back is least.