Complexity of an LRU Cache

The hash map plus doubly linked list design makes every operation constant time on average. This chapter explains where that bound comes from, what it costs in memory, how simpler designs compare, and why hit ratio matters as much as Big-O.

Time per operation

The list operations are O(1) in the worst case because each changes at most four pointers. The hash map is O(1) on average; with pathological collisions a lookup can degrade to O(n), and resizing makes insertion amortized rather than strictly constant. In practice, with a decent hash function, every operation is a handful of memory accesses.

Space

The cache holds at most capacity entries, so space is O(capacity). The constant factor is larger than for a plain dict: each entry needs a map slot, a node object, two pointers and a second reference to the key. You can see the overhead in Python:

import sys

class Node:
    __slots__ = ("key", "value", "prev", "next")

class FatNode:
    def __init__(self):
        self.key = self.value = self.prev = self.next = None

slim, fat = Node(), FatNode()
print(sys.getsizeof(slim))                            # e.g. 64 bytes
print(sys.getsizeof(fat) + sys.getsizeof(fat.__dict__))  # noticeably more

Exact numbers depend on the Python version, but __slots__ consistently saves memory per node. OrderedDict and functools.lru_cache keep their links in C, which is cheaper still.

Why simpler designs are slower

Many first attempts keep keys in a plain list and move them around. Finding and removing a key in a Python list costs O(n), so each operation becomes linear.

class NaiveLRU:
    def __init__(self, capacity):
        self.capacity = capacity
        self.order = []          # least recent first
        self.data = {}

    def get(self, key):
        if key not in self.data:
            return None
        self.order.remove(key)   # O(n) search and shift
        self.order.append(key)
        return self.data[key]

    def put(self, key, value):
        if key in self.data:
            self.order.remove(key)
        elif len(self.data) >= self.capacity:
            del self.data[self.order.pop(0)]  # O(n) shift
        self.order.append(key)
        self.data[key] = value