LRU Cache Visualization & Animation
Evicts the least recently used item in O(1) using a HashMap combined with a doubly linked list.
## What is it?
An LRU (Least Recently Used) Cache evicts the least recently used item when it reaches capacity. It supports O(1) `get` and `put` operations. Implemented with a HashMap + Doubly Linked List.
## How it works
- **HashMap** maps each key to its corresponding node in the doubly linked list → O(1) lookup
- **Doubly Linked List** maintains access order; most recently used at head, least recently used at tail
**get(key):**
- If not in map → return -1
- Move the node to the head of the list (mark as recently used)
- Return its value
**put(key, value):**
- If key exists → update value, move to head
- If key is new:
- If at capacity → remove the tail node (LRU item) and its map entry
- Create new node, add at head, add to map
## When to use
- Caching systems (CPU cache, web cache, database buffer pool)
- Any "evict the least recently used" policy
- LeetCode 146 — the canonical cache design problem
## Key Points
- HashMap for O(1) lookup; doubly linked list for O(1) insertions/deletions at known positions
- Dummy head and tail nodes simplify edge cases
- Combined, both structures give O(1) amortized for all operations
Category: algorithms
Difficulty: intermediate
Time Complexity: O(1) get/put
Space Complexity: O(capacity)
View LRU Cache Visualization