Hash map plus linked list (LRU)

O(1) lookup and O(1) recency with two structures that point at each other.

Low-level design conceptState, data structures and algorithms inside objects2 Nov 2026

01The intuition

The problem it solves

A browser keeps the last few pages in memory so going back is instant. When memory is full it should drop the page you used longest ago. The obvious design is a list ordered by last use: finding a page means scanning the list, and moving a page to the front means removing it from the middle, which is also a scan. With a thousand pages, every click costs a thousand steps, twice.

class Cache:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.items: list[tuple[str, bytes]] = []   # most recent first

    def get(self, key: str) -> bytes | None:
        for i, (k, v) in enumerate(self.items):     # O(n) scan
            if k == key:
                self.items.pop(i)                   # O(n) shift
                self.items.insert(0, (k, v))
                return v
        return None

Build it one piece at a time

Step one: fix the lookup. A dictionary finds a key in one step. But a dictionary has no order, so it cannot tell you which key is the oldest.

class Cache:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.map: dict[str, bytes] = {}      # O(1) find, but who is oldest?

Step two: fix the ordering. A doubly linked list lets you remove any node and put it at the front in one step each, if you already hold the node. You do not have to walk to find the ends: keep two fixed sentinel nodes, head and tail, so the most recent is always right after head and the oldest right before tail.

class Node:
    def __init__(self, key: str = "", value: bytes = b"") -> None:
        self.key, self.value = key, value
        self.prev: "Node | None" = None
        self.next: "Node | None" = None

class Order:
    def __init__(self) -> None:
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head
    def unlink(self, n: Node) -> None:
        n.prev.next, n.next.prev = n.next, n.prev          # O(1)
    def push_front(self, n: Node) -> None:
        n.next, n.prev = self.head.next, self.head
        self.head.next.prev = n; self.head.next = n        # O(1)
    def oldest(self) -> Node:
        return self.tail.prev

Step three: point the two structures at each other. The dictionary maps a key to its node, so a get finds the node in one step and the list moves it in one step. Eviction takes the node before the tail and deletes its key from the dictionary.

class LRUCache:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.map: dict[str, Node] = {}
        self.order = Order()

    def get(self, key: str) -> bytes | None:
        node = self.map.get(key)
        if node is None: return None
        self.order.unlink(node); self.order.push_front(node)   # touch
        return node.value

    def put(self, key: str, value: bytes) -> None:
        if key in self.map:
            node = self.map[key]; node.value = value
            self.order.unlink(node); self.order.push_front(node)
            return
        if len(self.map) == self.capacity:
            old = self.order.oldest()
            self.order.unlink(old); del self.map[old.key]       # evict
        node = Node(key, value); self.map[key] = node; self.order.push_front(node)

Why it works

The principle: when one structure gives you fast lookup and another gives you fast reordering, let each hold a pointer to the other and keep them in step. The invariant is that every key in the map is exactly one node in the list and every node is in the map, and the list order is the recency order. Where it breaks: a touch that moves the node but forgets to update on a put of an existing key, eviction that unlinks the node but leaves the key in the map, and the classic interview edge case: a get followed immediately by a put when full must evict the key that was least recent after the get, not before. Interviewers also ask why not a Python OrderedDict; the answer is that it is this structure, and you should be able to build it.

The trade-off you must say out loud

Two structures mean twice the bookkeeping and about three pointers of overhead per entry, which matters for millions of small values. If the cache is tiny, a list is fine. The follow-up is nearly always one of three: thread safety (one lock around get and put, or finer locks with care), LFU (buckets of nodes per frequency, each bucket its own list), and TTL (a timestamp on the node, checked lazily on get and swept occasionally).

Where it shows up in the 100 Google problems

LRU cache: the structure itself; the interview is about getting the invariant right under every operation order.
Thread-safe LFU cache: a map from frequency to one of these lists, plus a lock strategy.
Cache manager with pluggable eviction: the list is the LRU policy's private state behind a policy interface.
Set with O(1) getRandom: the same idea with an array instead of a list: the map stores each element's index.
Playlist shuffler with a no-repeat window: recently played tracks kept in exactly this order so the oldest can rejoin the pool.