The Algorithms - Python Python TheAlgorithms/Python

How an LRU Cache Works

A doubly-linked list plus a hashmap gives O(1) get and put. The eviction policy at the core of CPU caches, browser caches, and functools.lru_cache.

6 stops ~18 min Verified 2026-05-05

What you will learn

Why a doubly-linked list plus a hashmap achieves O(1) get and O(1) put
How sentinel head and rear nodes eliminate edge-case checks in add and remove
How get both reads the value and moves the accessed node to the rear of the list
How put evicts the least-recently-used node when the cache is at capacity
Why the decorator classmethod wraps any T to U function without changing its interface
How cache_info exposes hits, misses, capacity, and current size as a repr string
Why the doctest shows key 2 evicted before key 1 after a get re-orders the list

Prerequisites

Comfort reading Python generics syntax with TypeVar
Familiarity with doubly-linked lists and hash dictionaries
No prior knowledge of cache eviction policies required

The story behind LRU eviction

Least-Recently-Used cache eviction was described by Laszlo Belady in a 1966 IBM Systems Journal paper analyzing page replacement in virtual memory systems. The core question was simple: when physical memory is full and a new page must be loaded, which existing page should be discarded? Belady proved that the optimal policy is to evict the page that will not be needed for the longest time in the future. That policy, called Belady's MIN or OPT, is theoretically perfect but unimplementable because it requires knowing the future.

LRU is the practical approximation: evict the page that was accessed least recently, on the assumption that recent access predicts future access. The doubly-linked-list-plus-hashmap implementation that appears everywhere in interviews and libraries gives O(1) for both read and write by combining the O(1) lookup of a hashmap with the O(1) move of a doubly-linked list.

Python's functools.lru_cache uses this data structure internally. CPU L1 and L2 caches use LRU or pseudo-LRU variants in hardware. Browser HTTP caches, DNS resolvers, and database buffer pools all apply the same eviction logic. The implementation in this file is a clean educational version that also ships as a function decorator, mirroring the standard library interface.

1 / 6

DoubleLinkedListNode: Key-Value Pair with Bidirectional Links

other/lru_cache.py:10

Each cache entry is a node holding a key and value plus prev and next pointers. The generic parameters T and U let the cache store any hashable key with any value.

The LRU cache needs to track two things for every entry: its cached value and its position in the access-order sequence. A single node carries both. The key field lets the list remove a node from the hashmap when it is evicted; the val field is what the caller actually wants. The next and prev pointers allow O(1) removal and O(1) insertion anywhere in the list without scanning. The generic syntax DoubleLinkedListNode[T, U] on line 10 uses Python 3.12 type-parameter syntax, which lets the type checker verify that a cache keyed by strings always stores string nodes without any separate annotation. The __repr__ method shows whether both pointers are set, which makes the doctest readable: a freshly constructed node has neither neighbor.

Key takeaway

Each node carries both the cached value and the list position. Bidirectional pointers make O(1) removal possible without scanning.

class DoubleLinkedListNode[T, U]:
    """
    Double Linked List Node built specifically for LRU Cache

    >>> DoubleLinkedListNode(1,1)
    Node: key: 1, val: 1, has next: False, has prev: False
    """

    def __init__(self, key: T | None, val: U | None):
        self.key = key
        self.val = val
        self.next: DoubleLinkedListNode[T, U] | None = None
        self.prev: DoubleLinkedListNode[T, U] | None = None

    def __repr__(self) -> str:
        return (
            f"Node: key: {self.key}, val: {self.val}, "
            f"has next: {bool(self.next)}, has prev: {bool(self.prev)}"
        )

2 / 6

DoubleLinkedList: Sentinel Nodes and the add/remove Contract

other/lru_cache.py:98

Head and rear are permanent sentinel nodes with null keys. add always inserts before rear; remove returns None for sentinels and unlinked nodes.

The list uses two permanent sentinel nodes, head and rear, whose key fields are None. They never hold cached data; they exist so that add and remove never have to check whether a node's neighbors exist. The head-rear link on line 101 initializes an empty list where the two sentinels point at each other. add always inserts before rear by relinking four pointers, making the rear end of the list the most-recently-used position. remove returns None for any node whose pointers are None, which covers both sentinels and nodes that have already been removed. After removal the node's own pointers are set to None, so a double-remove is safe and idempotent. These two methods are all the LRUCache class calls.

Key takeaway

Sentinel head and rear nodes eliminate edge-case checks. add inserts before rear (most-recent end); remove returns None for sentinels and double-removes.

    def __init__(self) -> None:
        self.head: DoubleLinkedListNode[T, U] = DoubleLinkedListNode(None, None)
        self.rear: DoubleLinkedListNode[T, U] = DoubleLinkedListNode(None, None)
        self.head.next, self.rear.prev = self.rear, self.head

    def __repr__(self) -> str:
        rep = ["DoubleLinkedList"]
        node = self.head
        while node.next is not None:
            rep.append(str(node))
            node = node.next
        rep.append(str(self.rear))
        return ",\n    ".join(rep)

    def add(self, node: DoubleLinkedListNode[T, U]) -> None:
        """
        Adds the given node to the end of the list (before rear)
        """

        previous = self.rear.prev

        # All nodes other than self.head are guaranteed to have non-None previous
        assert previous is not None

        previous.next = node
        node.prev = previous
        self.rear.prev = node
        node.next = self.rear

    def remove(
        self, node: DoubleLinkedListNode[T, U]
    ) -> DoubleLinkedListNode[T, U] | None:
        """
        Removes and returns the given node from the list

        Returns None if node.prev or node.next is None
        """

        if node.prev is None or node.next is None:
            return None

        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None
        return node

3 / 6

LRUCache Doctest: The Eviction Sequence in Concrete Terms

other/lru_cache.py:146

The class doctest shows a capacity-2 cache where getting key 1 promotes it past key 2, so key 2 is evicted when key 3 is inserted.

The doctest makes the eviction sequence concrete. After inserting keys 1 and 2, calling get(1) moves key 1 to the rear (most-recent) position, so the list order becomes: head, key 2, key 1, rear. When key 3 is inserted at capacity, the cache evicts the node nearest to head, which is key 2. The list after insertion is: head, key 1, key 3, rear. get(2) then returns None because key 2 was evicted. This trace is the clearest way to understand why get must update the list position, not only read the value: a read that does not update the order would leave key 1 vulnerable to eviction even though it was the most recently accessed entry.

Key takeaway

get(1) before the put(3) promotes key 1 to most-recent, so key 2 is evicted instead. A get that skips list-update would break the LRU invariant.

class LRUCache[T, U]:
    """
    LRU Cache to store a given capacity of data. Can be used as a stand-alone object
    or as a function decorator.

    >>> cache = LRUCache(2)

    >>> cache.put(1, 1)
    >>> cache.put(2, 2)
    >>> cache.get(1)
    1

    >>> cache.list
    DoubleLinkedList,
        Node: key: None, val: None, has next: True, has prev: False,
        Node: key: 2, val: 2, has next: True, has prev: True,
        Node: key: 1, val: 1, has next: True, has prev: True,
        Node: key: None, val: None, has next: False, has prev: True

    >>> cache.cache  # doctest: +NORMALIZE_WHITESPACE
    {1: Node: key: 1, val: 1, has next: True, has prev: True, \
     2: Node: key: 2, val: 2, has next: True, has prev: True}

    >>> cache.put(3, 3)

    >>> cache.list
    DoubleLinkedList,
        Node: key: None, val: None, has next: True, has prev: False,
        Node: key: 1, val: 1, has next: True, has prev: True,
        Node: key: 3, val: 3, has next: True, has prev: True,
        Node: key: None, val: None, has next: False, has prev: True

    >>> cache.cache  # doctest: +NORMALIZE_WHITESPACE
    {1: Node: key: 1, val: 1, has next: True, has prev: True, \
     3: Node: key: 3, val: 3, has next: True, has prev: True}

    >>> cache.get(2) is None
    True

4 / 6

get: Read the Value and Promote the Node to Most-Recent

other/lru_cache.py:246

get removes the node from its current list position, re-adds it at the rear, and returns the value. Miss increments miss counter and returns None.

A cache get is two operations, not one. The hashmap lookup on line 253 finds the node in O(1) and increments hits. Then the node is removed from its current position in the doubly-linked list and immediately re-added at the rear. Those two list operations each touch only four pointers and run in O(1) regardless of cache size. The result is that after every successful get, the accessed node sits at the most-recent end of the list, furthest from the eviction candidate at the head end. The assertion on line 257 verifies that the removed node is the same object that the hashmap held, catching any bug where the list and hashmap fall out of sync. On a miss, self.miss increments and None returns without touching the list.

Key takeaway

get removes and re-adds the node in O(1) to promote it to most-recent. Two operations per hit, not one, is the cost of maintaining the LRU order.

    def get(self, key: T) -> U | None:
        """
        Returns the value for the input key and updates the Double Linked List.
        Returns None if key is not present in cache
        """
        # Note: pythonic interface would throw KeyError rather than return None

        if key in self.cache:
            self.hits += 1
            value_node: DoubleLinkedListNode[T, U] = self.cache[key]
            node = self.list.remove(self.cache[key])
            assert node == value_node

            # node is guaranteed not None because it is in self.cache
            assert node is not None
            self.list.add(node)
            return node.val
        self.miss += 1
        return None

5 / 6

put: Insert or Update, Evict the Oldest if Over Capacity

other/lru_cache.py:266

put inserts a new node at the rear when under capacity. At capacity it evicts list.head.next before inserting. Updating an existing key bumps the node to rear.

The put operation has three cases. If the key is new and the cache is under capacity, a fresh node is created and appended to the rear. If the key is new but the cache is at capacity, list.head.next is the oldest node because every prior get moved its node toward the rear and every prior insert placed new nodes at the rear; the node nearest to head has been untouched the longest. That node is removed from both the list and the hashmap before the new node is inserted. If the key already exists, the node is removed from its current position, its value is updated, and it is re-added at the rear, which counts as a recent use. All three paths touch only a constant number of pointers and a single hashmap operation, keeping put at O(1).

Key takeaway

Eviction targets list.head.next, the oldest node. All three cases (new, evict-then-new, update) touch only O(1) pointers and one hashmap operation.

    def put(self, key: T, value: U) -> None:
        """
        Sets the value for the input key and updates the Double Linked List
        """

        if key not in self.cache:
            if self.num_keys >= self.capacity:
                # delete first node (oldest) when over capacity
                first_node = self.list.head.next

                # guaranteed to have a non-None first node when num_keys > 0
                # explain to type checker via assertions
                assert first_node is not None
                assert first_node.key is not None
                assert (
                    self.list.remove(first_node) is not None
                )  # node guaranteed to be in list assert node.key is not None

                del self.cache[first_node.key]
                self.num_keys -= 1
            self.cache[key] = DoubleLinkedListNode(key, value)
            self.list.add(self.cache[key])
            self.num_keys += 1

        else:
            # bump node to the end of the list, update value
            node = self.list.remove(self.cache[key])
            assert node is not None  # node guaranteed to be in list
            node.val = value
            self.list.add(node)

6 / 6

The Decorator: LRU Cache as a Function Wrapper

other/lru_cache.py:297

LRUCache.decorator wraps any T-to-U function in an LRU cache of configurable size. cache_info returns the backing LRUCache instance for inspection.

The decorator classmethod makes LRUCache usable as a drop-in memoizer. The outer function takes a size parameter; the inner functions close over func and a dict mapping each decorated function to its own cache instance. That dict is necessary because a single classmethod might decorate multiple functions, and each must have a separate cache. The wrapper calls get first; on a miss it calls the original function, then stores the result with put. The cache_info inner function returns the backing LRUCache instance, which is attached to the wrapper via setattr so callers can inspect hits, misses, and current size without importing anything extra. The doctest in the class docstring uses this to cache a Fibonacci function and verify 194 hits across 99 unique inputs.

Key takeaway

The decorator pattern mirrors functools.lru_cache. cache_info returns the LRUCache instance directly, exposing hits, misses, and size for inspection.

    @classmethod
    def decorator(
        cls, size: int = 128
    ) -> Callable[[Callable[[T], U]], Callable[..., U]]:
        """
        Decorator version of LRU Cache

        Decorated function must be function of T -> U
        """

        def cache_decorator_inner(func: Callable[[T], U]) -> Callable[..., U]:
            # variable to map the decorator functions to their respective instance
            decorator_function_to_instance_map: dict[
                Callable[[T], U], LRUCache[T, U]
            ] = {}

            def cache_decorator_wrapper(*args: T) -> U:
                if func not in decorator_function_to_instance_map:
                    decorator_function_to_instance_map[func] = LRUCache(size)

                result = decorator_function_to_instance_map[func].get(args[0])
                if result is None:
                    result = func(*args)
                    decorator_function_to_instance_map[func].put(args[0], result)
                return result

            def cache_info() -> LRUCache[T, U]:
                return decorator_function_to_instance_map[func]

            setattr(cache_decorator_wrapper, "cache_info", cache_info)  # noqa: B010

            return cache_decorator_wrapper

        return cache_decorator_inner

Your codebase next

Create code tours for your project

Intraview lets AI create interactive walkthroughs of any codebase. Install the free VS Code extension and generate your first tour in minutes.

Install Intraview Free