Lesson 162
LRU Cache
Hash Map + Doubly Linked List
1:00How to build a fixed-capacity cache that evicts the least-recently-used entry in O(1) time using a hash map paired with a doubly linked list.
By the end, you can
- Explain why the naive sorted-list LRU implementation is O(n) per operation.
- Describe how combining a hash map with a doubly linked list achieves O(1) get and put.
- Trace a sequence of get/put operations on a capacity-2 LRU cache and identify which key is evicted at each step.
- Explain why the list must be doubly (not singly) linked and what role the dummy sentinel nodes play.
- State what value a cache miss returns and why a get on a hit must move the node to the front.
- Distinguish LRU, LFU, and CLOCK eviction policies and identify where each is used in practice.
Up next in Advanced Data Structures
