LRU Cache Patterns
Implement an O(1) least-recently-used cache using a doubly-linked list and hash map. Standard interview question with real-world applications in CDN edge caching, database buffer pools, and session stores.
Core Idea
Maintain insertion order via a linked list. On access, move the node to the head. On eviction, remove the tail. The hash map provides O(1) lookups by key, storing pointers directly to list nodes so removal and reordering never require a scan.
Complexity
Get
O(1)
Put
O(1)
Space
O(n)
Eviction
O(1)
Key Operations
- get(key) — lookup node in map, move to head, return value. Return -1 if absent.
- put(key, value) — if exists, update and move to head. If at capacity, evict tail before inserting at head.
- evict() — remove tail node from list and delete its entry from the map.
Gotchas
Use sentinel head and tail nodes to eliminate null checks on every splice. Store the key inside each list node so the map entry can be deleted during eviction without a reverse lookup. In languages without garbage collection, explicitly free evicted nodes to avoid memory leaks in long-running services.