Why an LRU cache needs a hash map and a linked list

transcript

Build a cache. Get and put in constant time. Eviction too. And no ordered dict. You build it yourself.

A dict finds any key in constant time. But LRU reorders on every access. A dict can't do that cheaply. So pair it with a doubly linked list. The map finds the node. The list unlinks it and moves it. Constant time. The oldest sits at the back. That's the next victim.

Right after the head: the most recently used. Right before the tail: the least recently used. Next to go. Head and tail are dummy nodes. Never removed. So no node is ever first, last or only. No edge-case bugs. Need B? The dict points straight at it. No search.

Capacity 3. Put A, B and C. Newest first: C, B, A. Get A. Now A is newest, and B is the oldest. Put D. The cache is full. B is evicted. A FIFO cache would have thrown out A. Same cache, different rule.

The dict finds the node. The list keeps the order. Neither works alone.

Full breakdown in the lecture.