LRU Cache
What you'll build
An LRUCache class with get(key) and put(key, value) operations, both O(1), that evicts the least recently used entry when the cache exceeds its capacity.
Goals
- Combine a hash map (for O(1) lookup) with a doubly linked list (for O(1) recency updates)
- Implement get and put with eviction on overflow
- Reason about operation complexity
- Justify design choices in comments
Prerequisites
- Objects as hash maps
- Linked list concepts (from project-11)
- O(1) complexity reasoning
Steps
- 1
Choose your data structures
Decide how to achieve O(1) get and put. The classic approach: a Map (or object) for key→node lookup, plus a doubly linked list to track access order. Document your choice.
Hint
A doubly linked list lets you move a node to the front in O(1) when you already have a reference to it (from the map).
- 2
Define the node and cache skeleton
Define a doubly linked list node (value, prev, next) and the LRUCache constructor taking a capacity. Initialize the map and the list head/tail sentinels.
Hint
Sentinel head/tail nodes simplify edge cases (empty list, single node).
- 3
Implement get
get(key) returns the value if present and moves that node to the front (most recently used). If absent, return -1. State the acceptance criteria: get on a missing key returns -1; get on a present key returns its value and makes it the most recent.
Hint
Look up the node in the map, unlink it from its current position, and move it to the front.
- 4
Implement put with eviction
put(key, value): if the key exists, update the value and move to front. If new, add to front and increment size. If size exceeds capacity, evict the least recently used (tail) and remove it from the map. Acceptance: after put beyond capacity, the oldest entry is gone.
Hint
Eviction removes the node before the tail sentinel and deletes its key from the map.
- 5
Verify with a scenario
Write a test: cache capacity 2; put(1,1), put(2,2), get(1)→1, put(3,3) (evicts key 2), get(2)→-1, get(3)→3, put(4,4) (evicts key 1), get(1)→-1, get(3)→3, get(4)→4. All assertions must pass.
Hint
If any assertion fails, re-check your eviction order — the most recently get/put key should never be evicted first.
Try it yourself
What you learned
You combined two data structures to achieve O(1) operations on a real-world abstraction — LRU caches are used in CPU caches, browser caches, Redis, and many databases.
Related Resources
Related Glossary
A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.
- Cache
A fast store of recently used data.
Decode error messages
Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.