LRU Cache Design
Software Engineer path · lesson 49 of 99A classic design problem combining HashMap for O(1) lookup with Doubly Linked List for O(1) ordering. Foundation for caching systems and system design interviews.
Syntax: put word n · get word. Numbers from -99 to 99.
Empty cache with room for 3.
- 1get(k): if k not in map: return -1
- 2 move k to the front (most recent); return its value
- 3put(k, v): if k in map: update v, move to front
- 4 else: if full: evict the back (least recent)
- 5 insert (k, v) at the front
- 6# hash map + doubly linked list: every step is O(1)
- Hits
- 0 / 2
- Misses
- 0 / 1
- Evictions
- 0 / 1
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
Who does which job?
Sort each responsibility into the structure that handles it.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
Hash map
Drop items hereDoubly linked list
Drop items hereTest your knowledge
Why use a Doubly Linked List instead of Singly Linked List?
Write the code
LRU Cache
class LRUCache {
constructor(capacity) {
// Your code here
}
get(key) {
// Your code here
}
put(key, value) {
// Your code here
}
}The short version
Think of a small desk that fits only a fixed number of papers. Every time you touch a paper, it moves to the front of the stack. When a new paper arrives and the desk is full, whichever paper has sat untouched the longest — at the back — gets bumped off. The challenge: make both 'touch' and 'bump off' instant (O(1)).
In more depth
HashMap + Doubly Linked List
The key insight: we need two data structures working together.
HashMap: key → Node pointer (O(1) lookup)
DLL: Maintains order from most recent (head) to least recent (tail)
Operations:
Sentinel Nodes:
Use dummy head and tail nodes to eliminate edge case checks:
HEAD <-> Node1 <-> Node2 <-> TAILKey Gotchas:
When to reach for this
- Cache with size limit and eviction policy
- Need O(1) for both access and modification
- Ordering based on recency or frequency
- System design: caching layers
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required