LRU Cache — Step-by-Step Visualization
mediumLeetCode #146Hash TableLinked ListDesignDoubly-Linked List
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the `LRUCache` class: `LRUCache(capacity)`, `get(key)`, and `put(key, value)`.
Algorithm Pattern
Hash Map + Doubly Linked List
Key Idea
To achieve O(1) for both `get` and `put`, we use a Hash Map combined with a Doubly Linked List. The Hash Map provides O(1) lookup to a node in the list. The Doubly Linked List maintains the order of access (MRU at front, LRU at back). When a key is accessed or added, we move its corresponding node to the MRU position. When capacity is exceeded, we remove the node at the LRU position.
Step-by-Step Approach
- Initialize Hash Map `cache` and dummy nodes `left` (LRU) and `right` (MRU).
- Get(key): If key exists, move node to `right` (MRU) and return value. Else return -1.
- Put(key, value): If key exists, update value and move node to `right`. If not, create node, add to `right`. If over capacity, remove node from `left` (LRU).
Common Gotchas
- Moving a node to MRU requires a `remove` and `insert` helper function for the Doubly Linked List.
- Dummy nodes `left` and `right` simplify the edge cases for list manipulation.