249. Design LRU Cache

Why this mechanism works

A dictionary finds an entry immediately, while a doubly linked list tracks recency and supports removing that known entry without searching. Sentinel nodes avoid separate empty/head/tail cases. Keep the least recent real node after head and the most recent before tail. Hits and updates move their nodes to that end.

State and boundaries

nodes maps exactly cached keys to their list nodes. The list contains each cached node once, ordered from least to most recent, with mutually consistent prev/next links.

Protocol

1. Initialize empty linked sentinels and map.
2. On a hit detach the node and append it before tail.
3. On put update an existing node or allocate a new one at the recent end.
4. If capacity is exceeded, detach head.next and delete its map entry.

Visualization

head <-> least recent <-> ... <-> most recent <-> tail
get(key): detach its node, append before tail
overflow: remove head.next from both list and dictionary

Python implementation

from structures import run_operations

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

class LRUCache:
    def __init__(self, capacity):
        self.capacity, self.nodes = capacity, {}
        self.head, self.tail = CacheNode(), CacheNode()
        self.head.next, self.tail.prev = self.tail, self.head

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

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

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

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

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L10 __init__: self.capacity, self.nodes = capacity, {}
self=LRUCache{'capacity':2, 'nodes':{}}; capacity=2

L5 __init__: self.key, self.value = key, value
self=CacheNode{'key':None, 'value':None}; key=None; value=None

L6 __init__: self.prev = self.next = None
self=CacheNode{'key':None, 'value':None, 'prev':None, 'next':None}; key=None; value=None

L5 __init__: self.key, self.value = key, value
self=CacheNode{'key':None, 'value':None}; key=None; value=None

L6 __init__: self.prev = self.next = None
self=CacheNode{'key':None, 'value':None, 'prev':None, 'next':None}; key=None; value=None

L11 __init__: self.head, self.tail = CacheNode(), CacheNode()
self=LRUCache{'capacity':2, 'nodes':{}, 'head':CacheNode..., 'tail':CacheNode...}; capacity=2

L32 put: if key in self.nodes:
self=LRUCache{'capacity':2, 'nodes':{}, 'head':CacheNode..., 'tail':CacheNode...}; key=1; value=10

L5 __init__: self.key, self.value = key, value
self=CacheNode{'key':1, 'value':10}; key=1; value=10

... 33 intermediate state changes omitted ...

L24 get: if key not in self.nodes:
self=LRUCache{'capacity':2, 'nodes':{...:..., ...:...}, 'head':CacheNode..., 'tail':CacheNode...}; key=3

L26 get: node = self.nodes[key]
self=LRUCache{'capacity':2, 'nodes':{...:..., ...:...}, 'head':CacheNode..., 'tail':CacheNode...}; key=3; node=CacheNode{'key':3, 'value':30, 'prev':CacheNode..., 'next':CacheNode...}

L15 _detach: node.prev.next = node.next
self=LRUCache{'capacity':2, 'nodes':{...:..., ...:...}, 'head':CacheNode..., 'tail':CacheNode...}; node=CacheNode{'key':3, 'value':30, 'prev':CacheNode..., 'next':CacheNode...}

L19 _append_recent: previous = self.tail.prev
self=LRUCache{'capacity':2, 'nodes':{...:..., ...:...}, 'head':CacheNode..., 'tail':CacheNode...}; node=CacheNode{'key':3, 'value':30, 'prev':CacheNode..., 'next':CacheNode...}; previous=CacheNode{'key':1, 'value':10, 'prev':CacheNode..., 'next':CacheNode...}

L10 __init__: self.capacity, self.nodes = capacity, {}
self=LRUCache{'capacity':1, 'nodes':{}}; capacity=1

L5 __init__: self.key, self.value = key, value
self=CacheNode{'key':None, 'value':None}; key=None; value=None

L6 __init__: self.prev = self.next = None
self=CacheNode{'key':None, 'value':None, 'prev':None, 'next':None}; key=None; value=None

L5 __init__: self.key, self.value = key, value
self=CacheNode{'key':None, 'value':None}; key=None; value=None

L6 __init__: self.prev = self.next = None
self=CacheNode{'key':None, 'value':None, 'prev':None, 'next':None}; key=None; value=None

L11 __init__: self.head, self.tail = CacheNode(), CacheNode()
self=LRUCache{'capacity':1, 'nodes':{}, 'head':CacheNode..., 'tail':CacheNode...}; capacity=1

L32 put: if key in self.nodes:
self=LRUCache{'capacity':1, 'nodes':{}, 'head':CacheNode..., 'tail':CacheNode...}; key=1; value=10

L5 __init__: self.key, self.value = key, value
self=CacheNode{'key':1, 'value':10}; key=1; value=10

... 12 intermediate state changes omitted ...

L24 get: if key not in self.nodes:
self=LRUCache{'capacity':1, 'nodes':{...:...}, 'head':CacheNode..., 'tail':CacheNode...}; key=1

L26 get: node = self.nodes[key]
self=LRUCache{'capacity':1, 'nodes':{...:...}, 'head':CacheNode..., 'tail':CacheNode...}; key=1; node=CacheNode{'key':1, 'value':11, 'prev':CacheNode..., 'next':CacheNode...}

L15 _detach: node.prev.next = node.next
self=LRUCache{'capacity':1, 'nodes':{...:...}, 'head':CacheNode..., 'tail':CacheNode...}; node=CacheNode{'key':1, 'value':11, 'prev':CacheNode..., 'next':CacheNode...}

L19 _append_recent: previous = self.tail.prev
self=LRUCache{'capacity':1, 'nodes':{...:...}, 'head':CacheNode..., 'tail':CacheNode...}; node=CacheNode{'key':1, 'value':11, 'prev':CacheNode..., 'next':CacheNode...}; previous=CacheNode{'key':None, 'value':None, 'prev':None, 'next':CacheNode...}

Why the solution is correct

Detaching and appending changes only recency, preserving all other entries and links. Every successful access or update becomes most recent by construction. New entries also enter there. Thus head.next is always the least recently used entry, and removing it implements exactly the required eviction policy.

Time and space

Expected O(1) time per get/put with hash lookup and constant pointer changes; O(capacity) stored entries. The sentinels use constant extra space.

Common mistakes

Updating a value without refreshing recency violates the access policy. Deleting only from the list or only from the map leaves inconsistent membership. Sentinel nodes must never be returned as cached data.

Reasoning card

Transfer exercise

Add expiration times. Identify why recency ordering alone cannot efficiently find the next expiring entry.