6.7

Idea: combine two O(1) structures 1. a hash map table: key → node for direct access, 2. a doubly-linked list that stores nodes from MRU → LRU. Moving a node to the list’s front marks it as most recently used; dropping the tail deletes the least recently used. Every operation therefore touches only a constant number of pointers and hash entries.

Node layout: (key, value, prev, next). Sentinel nodes head and tail avoid edge-cases: head.next is always the most-recent node, tail.prev the least-recent.

class LRU:
  def __init__(self, capacity):
    self.cap = capacity
    self.tab = {} # key → node
    self.head, self.tail = Node(), Node() # sentinels
    self.head.next, self.tail.prev = self.tail, self.head

  def _add_front(self, x): # O(1)
    x.next = self.head.next; x.prev = self.head
    self.head.next.prev = x; self.head.next = x

  def _remove(self, x): # O(1)
    x.prev.next = x.next; x.next.prev = x.prev

  def get(self, k):
    if k not in self.tab: return -1
    n = self.tab[k]; self._remove(n); self._add_front(n)
    return n.val

  def put(self, k, v):
    if k in self.tab: # update
      n = self.tab[k]; n.val = v; self._remove(n)
    else:
      n = Node(k, v); self.tab[k] = n
      if len(self.tab) > self.cap: # evict LRU
        lru = self.tail.prev; self._remove(lru); del self.tab[lru.key]
    self._add_front(n)

Complexities • get, put: a fixed number of hash look-ups and pointer updates → [math]O(1)[/math] time, [math]O(n)[/math] space.

Why it works • The hash map guarantees constant-time key lookup. • The doubly-linked list preserves global order and lets us move / delete any node in O(1). • By always inserting new or recently accessed nodes next to head, and evicting at tail, we maintain the Least-Recently-Used discipline exactly.

Back to Chapter 6