LRU Cache
Evicts the least recently used entry. A hash map plus a recency list gives O(1) get and put.
LRU Cache: A hit moves the node to the front
put 4 40: a new key, but the cache holds 3 already. The tail, key 2, is the least recently used, so it is dropped from both the list and the map, and 4:40 becomes the head.
Cost
- Get
- O(1)
- Put
- O(1)
- Space
- O(capacity)
Before this
Leads to
Topics that need this one first.
Taught by the same lesson
LRU Cache covers these too, in the same run.