The dictionary finds an existing node in expected constant time. The node’s previous and next pointers let the cache detach and reinsert it in constant time without searching for its predecessor.

The dictionary maps keys to their unique nodes. A list runs from least to most recent between two dummy sentinels. A successful get moves its node to the recent end. put updates an existing node or creates one; if capacity is exceeded, evict the least-recent real node from both structures. Every stored key must appear exactly once in the list, and every real node must be indexed. Sentinels simplify edge cases; they are never real entries.

What the function promises: LRUCache(capacity) supports integer-valued get and put as in the linked problem. A miss returns −1. Nonnegative capacity is required; zero capacity stores nothing. This implementation is single-threaded and in memory.

class Link:
    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.previous = self.next = None

class LRUCache:
    def __init__(self, capacity):
        if type(capacity) is not int or capacity < 0:
            raise ValueError("Capacity must be a nonnegative integer")
        self.capacity = capacity
        self.nodes = {}
        self.head, self.tail = Link(), Link()
        self.head.next, self.tail.previous = self.tail, self.head

    def _detach(self, node):
        node.previous.next = node.next
        node.next.previous = node.previous

    def _make_recent(self, node):
        previous = self.tail.previous
        previous.next = node
        node.previous, node.next = previous, self.tail
        self.tail.previous = node

    def get(self, key):
        if key not in self.nodes:
            return -1
        node = self.nodes[key]
        self._detach(node)
        self._make_recent(node)
        return node.value

    def put(self, key, value):
        if self.capacity == 0:
            return
        if key in self.nodes:
            node = self.nodes[key]
            node.value = value
            self._detach(node)
        else:
            node = Link(key, value)
            self.nodes[key] = node
        self._make_recent(node)
        if len(self.nodes) > self.capacity:
            oldest = self.head.next
            self._detach(oldest)
            del self.nodes[oldest.key]

cache = LRUCache(2)
cache.put(1, 10)
cache.put(2, 20)
assert cache.get(1) == 10
cache.put(3, 30)
assert cache.get(2) == -1
cache.put(1, 11)
assert cache.get(1) == 11 and len(cache.nodes) == 2
empty = LRUCache(0)
empty.put(1, 1)
assert empty.get(1) == -1

Work and storage: Expected O(1) get and put, O(capacity) space. Python’s OrderedDict can supply the ordering operations in practical code; the explicit list here exposes the invariant being maintained.

When to recognize it: Fast lookup and fast recency updates require different structures kept consistent by one owner.

Check before applying it: A hit changes recency. Updating an existing key must not create a second list node. This example is single-threaded.

Not generally. Recency and expiration are different orders. Decide whether lazy expiry on access is sufficient or add a separate expiry index, then keep all indexes consistent through one update boundary.