An LRU cache stores a limited number of key value pairs and evicts the least recently used item when it runs out of space. This cheat sheet helps students connect the abstract eviction rule to a concrete data structure design. It is useful for algorithms courses, systems courses, and technical interview preparation.
The goal is to make get and put operations both correct and efficient.
Key Facts
- An LRU cache with capacity C stores at most C key value pairs and evicts the least recently used pair when a new pair must be inserted into a full cache.
- The standard O(1) design combines a hash map from key to node with a doubly linked list ordered from most recently used to least recently used.
- get(k) returns the value for key k if present, then moves that node to the most recently used position.
- get(k) returns a miss value such as -1 or null if key k is not present, and it must not change the list.
- put(k, v) updates the value and moves the node to most recently used if key k already exists.
- put(k, v) inserts a new node at most recently used position if key k is absent, then evicts the least recently used node if size > capacity.
- With a hash map and doubly linked list, get(k) time = O(1), put(k, v) time = O(1), and space = O(C).
- Sentinel head and tail nodes simplify insert and remove logic because every real node has both a previous and next pointer.
Vocabulary
- LRU cache
- A bounded cache that removes the least recently used item when it needs space for a new item.
- Cache hit
- A cache hit occurs when a requested key is already stored in the cache.
- Cache miss
- A cache miss occurs when a requested key is not stored in the cache.
- Hash map
- A data structure that maps keys to values and supports average O(1) lookup, insertion, and deletion.
- Doubly linked list
- A linked list where each node stores references to both the previous node and the next node.
- Eviction
- Eviction is the removal of an item from the cache to keep the cache within its capacity.
Common Mistakes to Avoid
- Forgetting to move a node after get(k) is wrong because reading an item counts as recent use in an LRU cache.
- Evicting the most recently used node is wrong because LRU specifically removes the item that has gone unused for the longest time.
- Updating the value in the hash map but not the linked list is wrong because the cache order becomes inconsistent with actual access history.
- Removing a node from the list but leaving its key in the hash map is wrong because future lookups may point to deleted or invalid nodes.
- Using only an array or plain list is usually wrong for the standard design because moving and deleting arbitrary items takes O(n) instead of O(1).
Practice Questions
- 1 An LRU cache has capacity 2. Starting empty, perform put(1,10), put(2,20), get(1), put(3,30). Which key is evicted?
- 2 An LRU cache has capacity 3. Starting empty, perform put(1,1), put(2,2), put(3,3), get(2), put(4,4). List the keys from most recently used to least recently used.
- 3 For a cache with capacity C using a hash map and doubly linked list, what are the time complexities of get(k), put(k,v), and the space complexity?
- 4 Why does the common O(1) LRU cache design need both a hash map and a doubly linked list instead of only one of them?