LLD: LRU Cache

O(1) get and put with least-recently-used eviction — a hash map for lookup plus a doubly linked list for recency, behind a clean cache interface.

Big idea

An LRU cache keeps at most N entries and, when full, evicts the one used least recently. The trick is getting every operation in O(1): a hash map finds an entry's node instantly, and a doubly linked list keeps nodes in recency order so moving one to the front, or dropping the back, is a couple of pointer swaps.

Requirements

Functional

get(key) returns the value or a miss; a hit makes the entry most recent.
put(key, value) inserts or updates; if over capacity, evict the least recently used.
Fixed capacity set at construction.

Non-functional: get and put in O(1); safe for concurrent use (extension); eviction policy swappable (extension).

Entities

Cache (interface), LRUCache, Node (key, value, prev, next), DoublyLinkedList (with sentinel head and tail), optionally EvictionPolicy and CacheStats.

Think of it like

A small desk with room for five folders. Every time you use a folder you put it on top of the pile. When a sixth folder arrives, the one at the bottom — the one you haven't touched for longest — goes back to the filing cabinet. To find a folder fast you also keep an index card telling you exactly where each one sits in the pile.

Class diagram

Loading diagram

Map for lookup, list for order

Key flow: a put that evicts

Loading diagram

put(d) on a full cache of a, b, c

Watch it

Code skeleton

A from-scratch LRU with sentinel nodes

class Node:
    __slots__ = ("key", "value", "prev", "next")
    def __init__(self, key=None, value=None):
        self.key, self.value, self.prev, self.next = key, value, None, None


class DoublyLinkedList:
    def __init__(self):
        self.head, self.tail = Node(), Node()        # sentinels: no edge cases for empty lists
        self.head.next, self.tail.prev = self.tail, self.head
    def push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node
    def remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev
    def pop_back(self):
        node = self.tail.prev
        self.remove(node)
        return node
    def keys(self):
        node, out = self.head.next, []
        while node is not self.tail:
            out.append(node.key); node = node.next
        return out


class LRUCache:
    def __init__(self, capacity):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity, self.map, self.order = capacity, {}, DoublyLinkedList()
        self.hits = self.misses = 0

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            self.misses += 1
            return None
        self.hits += 1
        self.order.remove(node); self.order.push_front(node)    # now most recent
        return node.value

    def put(self, key, value):
        if key in self.map:
            node = self.map[key]
            node.value = value
            self.order.remove(node)
        else:
            if len(self.map) == self.capacity:
                evicted = self.order.pop_back()
                del self.map[evicted.key]
                print(f"  evict {evicted.key}")
            node = Node(key, value)
            self.map[key] = node
        self.order.push_front(node)


cache = LRUCache(3)
for k, v in [("a", 1), ("b", 2), ("c", 3)]:
    cache.put(k, v)
print("get a ->", cache.get("a"))
cache.put("d", 4)                      # b is least recent now
print("get b ->", cache.get("b"))
cache.put("c", 30)                     # update refreshes c
cache.put("e", 5)
print("order (most recent first):", cache.order.keys())
print(f"hits={cache.hits} misses={cache.misses}")

output
get a -> 1
  evict b
get b -> None
  evict a
order (most recent first): ['e', 'c', 'd']
hits=1 misses=1

Run and edit it in the app.

In Python, collections.OrderedDict with move_to_end and popitem(last=False) gives the same behaviour in a few lines — say so in an interview, then show you know what's underneath.

Why a doubly linked list rather than a singly linked one?

Why does each list node store its key as well as its value?

Extensions and trade-offs

Thread safety — one lock around get/put is simplest; sharded caches (N independent LRUs keyed by hash) reduce contention.
TTL — store an expiry per node and treat expired entries as misses (Rate limiter uses the same injected clock idea).
Other policies — LFU, FIFO, or size-aware eviction behind an EvictionPolicy Strategy.
Write-through/back — wrap a slow store with the cache as a Proxy or Decorator.
At system scale, see Caching.

Key terms

LRU (least recently used) — Evict the entry that hasn't been accessed for the longest time.
Sentinel node — A dummy head or tail node that removes empty-list special cases.
Eviction — Removing an entry to make room for a new one.
Hit rate — The fraction of lookups served from the cache.