LRU Cache

Support get and put in constant time. Remove the least recently used item when the cache is full.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

LRU Cache: The map gives direct node access while the doubly linked order exposes the eviction candidate at its left edge.

Input and goalSupport `get` and `put` in constant time. Remove the least recently used item when the cache is full.

Initialize empty cacheCreate least and most sentinels, link them together, and start with an empty key-to-node map.

least→most

inputcapacity=2; put(1,10), put(2,20), get(1), put(3,30), get(2)map{}linkseach shown adjacency has both previous and next linkssize0 / 2

Recognize it

The interface requires both O(1) key lookup and O(1) least-recent eviction, which no single ordinary array, map, or queue provides alone.

Keep true

Every map entry points to exactly one node between the sentinels, and list order is least-recent to most-recent; successful access moves that same key to the right edge.

Reuse it

Combine an index with an ordered linked structure whenever a system needs direct identity lookup plus constant-time promotion, removal, or boundary eviction.

Pattern: Hash map plus doubly linked list.

Simple idea: The map finds a node by key. The linked list stores use order. The left side is least recent and the right side is most recent. Reading or writing a key moves its node to the right side.

from __future__ import annotations
from dataclasses import dataclass

@dataclass(eq=False, slots=True)
class _CacheNode:
   key: int = 0
   value: int = 0
   previous: _CacheNode | None = None
   next: _CacheNode | None = None


class LRUCache:
   def __init__(self, capacity: int) -> None:
      self.capacity = capacity
      self.nodes: dict[int, _CacheNode] = {}
      self.least = _CacheNode()
      self.most = _CacheNode()
      self.least.next = self.most
      self.most.previous = self.least

   def _remove(self, node: _CacheNode) -> None:
      node.previous.next = node.next
      node.next.previous = node.previous

   def _append(self, node: _CacheNode) -> None:
      node.previous = self.most.previous
      node.next = self.most
      self.most.previous.next = node
      self.most.previous = node

   def get(self, key: int) -> int:
      if key not in self.nodes:
         return -1
      node = self.nodes[key]
      self._remove(node)
      self._append(node)
      return node.value

   def put(self, key: int, value: int) -> None:
      if key in self.nodes:
         self._remove(self.nodes[key])

      node = _CacheNode(key, value)
      self.nodes[key] = node
      self._append(node)

      if len(self.nodes) > self.capacity:
         removed = self.least.next
         self._remove(removed)
         del self.nodes[removed.key]

Cost: get and put take $O(1)$ average time. Space is $O(capacity)$.