LRU Cache

The Idea

Two structures, one job each. A map finds a key in one step but stores no order; a doubly linked list reorders in one step but cannot find.

Keep the node in the map. Every touch unlinks it and relinks it at the front, so the tail is always the least recently used — and evicting it is O(1).

Real-World Example

A desk stacked with paper files and an index card box. The cards say which pile a file is in; reading a file means putting it back on top. When the desk overflows, the sheet at the bottom goes.

The Code

from collections import OrderedDict     # a hash map *plus* a linked list

class LRU:
    def __init__(self, cap): self.cap, self.box = cap, OrderedDict()
    def get(self, k):
        if k not in self.box: return -1
        self.box.move_to_end(k)                     # unlink, relink at front
        return self.box[k]
    def put(self, k, v):
        self.box[k] = v; self.box.move_to_end(k)
        if len(self.box) > self.cap: self.box.popitem(last=False)   # drop tail

c = LRU(2); c.put("a", 1); c.put("b", 2); c.get("a"); c.put("c", 3)
print(list(c.box), c.get("b"))          # ['a', 'c'] -1

The Tradeoff

Both operations are O(1), but a hit is a write, so a shared cache needs a lock exactly where it is hottest. LRU is also fooled by one sweep of cold keys; a frequency policy survives that and costs more to maintain.