LRU cache¶

An LRU cache must support direct key lookup, refresh recency on access, and evict the least-recent key at capacity. No single basic structure owns all three operations.

Operation contract¶

Operation	Target	Owner
find key	`O(1)` expected	hash map `key → list node`
mark most recent	`O(1)`	doubly linked list splice
find least recent	`O(1)`	list tail
evict	`O(1)` expected	tail removal + map erase

Cross-structure invariant¶

Every live map entry points to exactly one live list node, every real list node has exactly one map entry, the front is most recent, and the back is least recent.

That sentence is the proof obligation for every mutation.

flowchart LR
  accTitle: LRU cache synchronizes a hash map with recency order
  accDescr: The map points directly to list nodes, the list orders keys from most to least recent, successful access moves one node to the front, and eviction removes the tail from both structures.
  M["Hash map<br/>key → list node"] --> N2["key 2"]
  M --> N7["key 7"]
  M --> N4["key 4"]
  H["MRU sentinel"] <--> N2
  N2 <--> N7
  N7 <--> N4
  N4 <--> T["LRU sentinel"]
  G["get key 7"] --> X["Detach node 7"]
  X --> Y["Insert node 7 after MRU"]
  T -->|"evict tail key 4"| E["Erase node 4<br/>and map entry 4"]

Follow one key through both owners: lookup starts in the map, recency changes in the list, and eviction must delete the same key from both.

Thinking flow¶

A map solves lookup but cannot answer which key is oldest.
A linked list owns recency but cannot find an arbitrary key quickly.
Store list-node handles in the map.
On successful get, move that existing node to the front.
On put, update-and-move or insert at the front.
If over capacity, capture the tail key, remove its node, and erase the same key from the map.

Tested templates¶

The comments mark the synchronization points rather than narrating every syntax line.

PythonC++17C++11

class _LRUNode:
    """One entry in the recency list."""

    __slots__ = ("key", "value", "previous", "next")

    def __init__(self, key: int = 0, value: int = 0) -> None:
        self.key = key
        self.value = value
        self.previous: _LRUNode | None = None
        self.next: _LRUNode | None = None


class LRUCache:
    """Map keys to nodes while a linked list owns recency order."""

    def __init__(self, capacity: int) -> None:
        if capacity < 0:
            raise ValueError("capacity must be nonnegative")
        self.capacity = capacity
        self.nodes: dict[int, _LRUNode] = {}
        self.head, self.tail = _LRUNode(), _LRUNode()
        self.head.next, self.tail.previous = self.tail, self.head

    def _detach(self, node: _LRUNode) -> None:
        # Splice the node out without searching for its neighbors.
        assert node.previous is not None and node.next is not None
        node.previous.next = node.next
        node.next.previous = node.previous

    def _insert_front(self, node: _LRUNode) -> None:
        # The first real node is always the most recently used.
        first = self.head.next
        assert first is not None
        node.previous, node.next = self.head, first
        self.head.next = first.previous = node

    def _touch(self, node: _LRUNode) -> None:
        self._detach(node)
        self._insert_front(node)

    def get(self, key: int) -> int:
        node = self.nodes.get(key)
        if node is None:
            return -1
        # A successful read makes this entry most recent.
        self._touch(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.nodes:
            node = self.nodes[key]
            node.value = value
            self._touch(node)
            return

        node = _LRUNode(key, value)
        self.nodes[key] = node
        self._insert_front(node)
        if len(self.nodes) > self.capacity:
            # Evict the least-recent real node and its map entry together.
            oldest = self.tail.previous
            assert oldest is not None and oldest is not self.head
            self._detach(oldest)
            del self.nodes[oldest.key]

class LRUCache {
 public:
  explicit LRUCache(int capacity) : capacity_(capacity) {
    if (capacity < 0) {
      throw std::invalid_argument("capacity must be nonnegative");
    }
  }

  // The map stores iterators into this instance's list, so shallow copying
  // would leave the copy pointing into the original cache.
  LRUCache(const LRUCache&) = delete;
  LRUCache& operator=(const LRUCache&) = delete;
  LRUCache(LRUCache&&) noexcept = default;
  LRUCache& operator=(LRUCache&&) noexcept = default;

  int get(int key) {
    const auto found = nodes_.find(key);
    if (found == nodes_.end()) {
      return -1;
    }
    // A successful read makes this entry most recent.
    touch(found->second);
    return found->second->second;
  }

  void put(int key, int value) {
    const auto found = nodes_.find(key);
    if (found != nodes_.end()) {
      found->second->second = value;
      touch(found->second);
      return;
    }

    // The list front is most recent; the back is the eviction target.
    recency_.push_front({key, value});
    nodes_[key] = recency_.begin();
    if (nodes_.size() > static_cast<std::size_t>(capacity_)) {
      const int oldest_key = recency_.back().first;
      recency_.pop_back();
      nodes_.erase(oldest_key);
    }
  }

 private:
  using Entry = std::pair<int, int>;
  using Iterator = std::list<Entry>::iterator;

  void touch(Iterator entry) {
    // splice moves the existing node without invalidating its iterator.
    recency_.splice(recency_.begin(), recency_, entry);
  }

  int capacity_;
  std::list<Entry> recency_;
  std::unordered_map<int, Iterator> nodes_;
};

class LRUCache {
 public:
  explicit LRUCache(int capacity) : capacity_(capacity) {
    if (capacity < 0) {
      throw std::invalid_argument("capacity must be nonnegative");
    }
  }

  // The map stores iterators into this instance's list, so shallow copying
  // would leave the copy pointing into the original cache.
  LRUCache(const LRUCache&) = delete;
  LRUCache& operator=(const LRUCache&) = delete;
  LRUCache(LRUCache&&) noexcept = default;
  LRUCache& operator=(LRUCache&&) noexcept = default;

  int get(int key) {
    const auto found = nodes_.find(key);
    if (found == nodes_.end()) {
      return -1;
    }
    // A successful read makes this entry most recent.
    touch(found->second);
    return found->second->second;
  }

  void put(int key, int value) {
    const auto found = nodes_.find(key);
    if (found != nodes_.end()) {
      found->second->second = value;
      touch(found->second);
      return;
    }

    // The list front is most recent; the back is the eviction target.
    recency_.push_front({key, value});
    nodes_[key] = recency_.begin();
    if (nodes_.size() > static_cast<std::size_t>(capacity_)) {
      const int oldest_key = recency_.back().first;
      recency_.pop_back();
      nodes_.erase(oldest_key);
    }
  }

 private:
  using Entry = std::pair<int, int>;
  using Iterator = std::list<Entry>::iterator;

  void touch(Iterator entry) {
    // splice moves the existing node without invalidating its iterator.
    recency_.splice(recency_.begin(), recency_, entry);
  }

  int capacity_;
  std::list<Entry> recency_;
  std::unordered_map<int, Iterator> nodes_;
};

Boundary tests¶

capacity zero;
overwrite an existing key without creating a second node;
get changes the next eviction victim;
evict from capacity one;
repeatedly update the current head or tail.

Practice¶

LeetCode: LRU Cache