Implementing an LRU cache with a doubly linked list and hash map

A cache stores data close to the code that needs it, allowing repeated requests to avoid slower work. An LRU cache keeps entries up to a chosen capacity and removes the least recently used entry when a new one arrives. A read or a write makes an entry recent. This simple rule preserves frequently accessed values without requiring a prediction of every future request.

A Python dictionary provides fast key lookup but no automatic access order. A list can record order, but finding or removing a particular entry may require scanning the whole list. Combining a hash map with a doubly linked list solves both problems: the map locates an entry directly, and the list maintains recency with constant-time moves. The result is predictable eviction with average O(1) lookup and update.

Why an LRU cache needs a predictable eviction policy

Every bounded cache needs a rule for deciding what to remove. First-in, first-out is simple, yet it can discard an entry that remains useful while retaining an older one. Least recently used eviction removes the entry untouched for the longest time. It is a heuristic rather than a guarantee of the ideal choice, but its behaviour is easy to reason about and test.

Think of a passenger on a crowded train in Brisbane, alternating between a map, a music playlist and a banking application while the connection is unreliable. Keeping recently opened data can make each interaction feel faster. LRU does not know that a bank transaction may be more urgent than a playlist, however, so it treats recency as a useful signal rather than the only priority.

For broader algorithm study, the Hello ML community offers open educational articles that connect explanations with implementation details.

Designing the doubly linked list and hash map

The cache keeps two views of the same data. A hash map maps each key to a list node. A doubly linked list arranges those nodes by recency, with the newest at the front and the oldest at the back. Each real node holds a key, a value, a previous pointer and a next pointer.

The map makes lookup independent of list length. The list records order without sorting a collection of key-value pairs. Two-way links matter because detaching a node requires access to both its predecessor and successor. With only a forward pointer, locating the predecessor could mean walking through much of the list.

Two sentinel nodes remove boundary special cases. A permanent head sits before the newest entry, and a permanent tail sits after the oldest. They remain linked even when the cache is empty. Insertions and removals can therefore use the same pointer updates whether the list contains one entry or thousands.

The map and list must never disagree. Every dictionary entry points to a live node, and every live node belongs to exactly one cache entry. This shared-node design avoids copying values between structures and keeps updates synchronised.

Implementing get, put, and eviction

This implementation uses explicit nodes and a dictionary rather than relying on an ordered container:

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

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


class LRUCache:
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("capacity must be positive")

        self.capacity = capacity
        self._nodes = {}
        self._head = Node()
        self._tail = Node()
        self._head.next = self._tail
        self._tail.prev = self._head

    def _unlink(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = None

    def _promote(self, node):
        node.prev = self._head
        node.next = self._head.next
        self._head.next.prev = node
        self._head.next = node

    def get(self, key):
        node = self._nodes.get(key)
        if node is None:
            return -1

        self._unlink(node)
        self._promote(node)
        return node.value

    def put(self, key, value):
        node = self._nodes.get(key)

        if node is not None:
            node.value = value
            self._unlink(node)
            self._promote(node)
            return

        node = Node(key, value)
        self._nodes[key] = node
        self._promote(node)

        if len(self._nodes) > self.capacity:
            oldest = self._tail.prev
            self._unlink(oldest)
            del self._nodes[oldest.key]

The get method looks up a node, moves it to the front and returns its value. A miss leaves the order unchanged. The put method updates and promotes an existing key, or inserts a new node at the front. If that insertion exceeds capacity, the node immediately before the tail is evicted from both the list and the dictionary. Recency therefore changes on reads as well as writes.

Construction rejects a non-positive capacity. The sample also returns -1 for a miss. If -1 is a legitimate cached value, use a unique sentinel or raise an exception instead, so absence cannot be confused with real data.

Reasoning about correctness and complexity

The central invariant is that the dictionary and list contain the same entries, ordered from newest to oldest. A hit moves its node to the front without changing its value. An insertion adds a newest node. When capacity is exceeded, the node before the tail is removed from both structures. These steps preserve consistency and size.

With average constant-time dictionary access, get and put are O(1). Node promotion and eviction are also O(1), since neither requires traversal. Space is O(c) for c cached entries, plus fixed metadata. Pathological hash collisions are a separate dictionary-performance concern worth considering when keys come from an untrusted source.

Related algorithm lessons reinforce the value of reuse. A subset-sum dynamic programming guide shows how saved subproblem results avoid repeated computation. Dynamic programming deliberately retains required states, whereas an LRU cache keeps recent results and eventually discards them.

That difference prevents an LRU cache from replacing a dynamic programming table. It can evict a result that a later request needs, forcing recomputation, while a correctly designed table can guarantee reuse of every relevant state. Choose the cache when bounded memory and changing request patterns matter.

Applying caches responsibly in Australian systems

LRU-style caches appear in API gateways, service workers and local computation layers. A small retailer in Melbourne may cache a product catalogue while prices and stock levels change frequently. The cache reduces repeated work, but stale availability data must still expire. Python also provides functools.lru_cache for pure functions and OrderedDict for explicit recency control.

Australian privacy obligations apply to cache contents, not merely the storage technology. Where the Privacy Act 1988 applies, the Australian Privacy Principles remain relevant when cached values contain personal information. Avoid unnecessary personal fields in shared caches, encrypt sensitive values, set expiry times and support clearing entries when source data changes or is deleted.

Everyday use adds nuance. A commuter in Sydney may check an electronic ticket, a weather service and a message application during a train transfer. Recency helps repeated interactions, but it cannot recognise that a ticket may be more urgent than entertainment. Critical operations may deserve separate storage or an explicit priority policy.

Distributed deployments also need consistent naming. A service running in Brisbane and another running in Melbourne may share a cache tier while using different configuration. Versioned keys or separate namespaces can prevent one deployment from serving stale assumptions to the other.

Testing behaviour and measuring performance

Correctness is easiest to trust when tested as a sequence of observable operations. Inspect the cache after each access, not just at the end, because a faulty promotion can leave a plausible final state while the eviction order was wrong. A short deterministic example makes the expected behaviour explicit:

cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)

assert cache.get("a") == 1  # Refreshes "a"
cache.put("c", 3)          # Evicts "b"

assert cache.get("b") == -1
assert cache.get("a") == 1
assert cache.get("c") == 3

Check invariants before performance. A fuller suite should cover updates, misses, an empty cache and the capacity boundary. Property-based tests can generate random operation sequences and compare the result with a simple reference model.

Invariants to verify

• Each cached key maps to exactly one node.
• A successful read moves that key to the front.
• An update changes the value and refreshes recency.
• Eviction removes the oldest node from both structures.
• Misses and empty-cache cases preserve consistency.

Different algorithms need different evidence. The radix sorting guide explores another case where constraints shape both the design and its tests. For an LRU cache, record hit ratio, latency and memory together, since frequent hits can still hide expensive misses and substantial per-entry overhead.

Measurements to record

• Hit ratio for representative request traffic.
• Median and high-percentile read and write latency.
• Memory used per cached entry.
• Eviction frequency and the keys affected.
• Repeatable results from correctness tests.

Together, these measurements distinguish a useful cache from one that merely adds bookkeeping to every request.