LRU Cache — Evict Least Recently Used

LRU evicts the stale key when capacity is full. A hash map for O(1) lookup plus a doubly linked list (or OrderedDict) tracks recency order.

Try this in Python

from collections import OrderedDict


class LRUCache:
    def __init__(self, cap: int) -> None:
        self.cap = cap
        self.od: OrderedDict[int, int] = OrderedDict()

    def get(self, k: int) -> int | None:
        if k not in self.od:
            return None
        self.od.move_to_end(k)
        return self.od[k]

    def put(self, k: int, v: int) -> None:
        if k in self.od:
            self.od.move_to_end(k)
        self.od[k] = v
        if len(self.od) > self.cap:
            self.od.popitem(last=False)


c = LRUCache(2)
c.put(1, 10)
c.put(2, 20)
print(c.get(1))
c.put(3, 30)
print(c.get(2), list(c.od.keys()))

Key takeaways

• move_to_end marks a key as most recently used.
• popitem(last=False) drops the LRU entry.
• In interviews, practice the DLL version too—it is the same logic.