SpecializedSpecialized Structures

LRU Cache

A fixed-capacity key-value store that evicts the least recently used entry, with O(1) get and put via a hash map plus a doubly linked list.

Learn LRU Cache →
empty list
map (key → node)
keyvalue
1/18LRU cache with capacity 2. A hash map gives O(1) lookup by key; a doubly linked list orders entries by recency — head is most recently used, tail is the eviction candidate.
Hit (moved to front)InsertedEvicted (least recent)Looked up
PseudocodeLearn LRU Cache →
1get(k): if k not in map: return -1
2  move node to front (most recent); return node.value
3put(k, v): if k in map: update value; move to front
4  else: insert new node at front; map[k] = node
5    if size > capacity: evict the tail node; delete map[tail.key]
Variables
size0
capacity2
Complexity
access O(1)
search O(1)
insert O(1)
delete O(1)
Speed