About LRU Cache
LRU (Least Recently Used) cache evicts the least recently accessed item when at capacity.
Data Structure: Hash Map + Doubly Linked List composite gives O(1) for both GET and PUT. The hash map provides O(1) key lookup; the doubly linked list maintains access order with O(1) move-to-front and O(1) tail removal.
Why both? A hash map alone cannot track ordering. A linked list alone requires O(n) lookup. Together they achieve O(1) for all operations.
Use Cases:
- CPU cache (L1/L2/L3)
- Web browser page cache
- Database buffer pool
- CDN edge caching
- DNS resolution cache
- OS page replacement
vs FIFO: FIFO evicts oldest inserted, ignoring access patterns. LRU adapts to locality of reference.
vs LFU: LFU evicts least frequently used, which can retain stale popular items. LRU naturally ages out unused entries.