DSA · interactive
LRU cache
A cache with room for 3 items. When it's full, throw out the one used least recently. A hash map finds items in O(1); a doubly linked list keeps them in order of use so moving and evicting are O(1) too.
- put(a, 1)
- put(b, 2)
- put(c, 3)
- get(a)
- put(d, 4)
- get(b)
- get(c)
- put(e, 5)
- get(a)
Recency list: most recent → least recent
headtail
Hash map
{ }
· 0 hits, 0 misses
Capacity 3. Most recent on the left, least recent on the right.
op 0 of 9
1 Key → list node, so finding an item is O(1).
Map<key, Node>
2 3 4
In production
Tools and technologies
LRU and its approximations sit in front of most slow storage.
Not tied to one language — use these names when you search docs or design a system.