Design an LRU Cache Class

Hash map plus doubly linked list

An LRU cache with fixed capacity evicts the least recently used entry when full. To make get and put O(1), combine a hash map from key to node with a doubly linked list ordered by recency: on access, move the node to the head; on insert when full, remove the tail. Interview extensions: make it thread-safe (a single lock is simplest; segmenting by key hash reduces contention), add TTL expiry, support eviction callbacks, or make the eviction policy a strategy (LRU, LFU). In Java, LinkedHashMap with access order and removeEldestEntry gives LRU behaviour, but interviewers usually want to see the structure built by hand.

LRU cache from scratch

Python; sentinel head and tail nodes simplify edge cases.

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

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map: dict = {}
        self.head, self.tail = _Node(), _Node()      # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

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

    def _push_front(self, node):
        node.next, node.prev = self.head.next, self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return None
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key, value) -> None:
        if key in self.map:
            node = self.map[key]
            node.value = value
            self._unlink(node)
        else:
            if len(self.map) == self.capacity:
                lru = self.tail.prev
                self._unlink(lru)
                del self.map[lru.key]
            node = _Node(key, value)
            self.map[key] = node
        self._push_front(node)

A stack of papers on a desk

Every paper you touch goes back on top; when the desk is full, the one at the bottom, untouched longest, goes in the bin.

Quick check: Why is a doubly linked list used rather than a singly linked list?

• To avoid using a hash map
• To sort keys alphabetically
• To store duplicate keys
• To unlink a node in O(1) given only a reference to it