LRU Cache Design: Hash Map, Linked List, and Worked Example

1. Introduction to LRU Cache Design

This guide develops one data-structure design problem: a least recently used (LRU) cache. It is a useful starting point for low-level design, but it is not a complete system-design curriculum. The implementations below store integer keys and values and return -1 when a key is absent. Capacity is assumed to be non-negative.

2. Core LLD Questions

Q1. Design LRU Cache

A cache has a fixed number of entries. get(key) returns the stored value and marks that entry as recently used. put(key, value) inserts or updates an entry and also marks it as recently used. If a new insertion exceeds capacity, evict the entry that has gone longest without a successful read or write. A missing read must not change the order.

Why combine two data structures?

A hash map finds the node for a key in expected constant time, but it does not by itself support moving an arbitrary entry within a recency ordering. A doubly linked list supports removing a known node and inserting it at the front without walking the list. Combining them gives each structure one job: lookup in the map, ordering in the list.

The head and tail are sentinel nodes, not cache entries. The node after head is the most recently used; the node before tail is the least recently used. Every map entry points to exactly one linked node. Removing a node must reconnect both neighbours. Eviction must also remove its map entry; otherwise a future lookup could return stale data or, in C++, a freed pointer.

Worked example: capacity two

Updating key 1 must not increase the number of entries. The C++ implementation reuses that node and moves it to the front, avoiding a leaked allocation. Its destructor releases all nodes, including the sentinels; copying is disabled because a shallow copy would otherwise share owning pointers.

Complexity and limits

Each operation changes a fixed number of list pointers and performs a few hash-map operations. Time is expected O(1), rather than a worst-case guarantee for every hash-table implementation. Space is O(capacity), plus the two sentinels. With capacity zero, every insertion is immediately evicted.

These examples are single-threaded, in-memory caches. They do not implement expiration, persistence, or coordination between servers. In a concurrent service, lookup and recency updates must be synchronized together. LRU is also vulnerable to scans: reading many distinct keys once can evict a frequently used working set. Those tradeoffs belong in a design discussion rather than being hidden behind an O(1) claim.

Implementation

cpp
#include <unordered_map>
using namespace std;

class LRUCache {
    struct Node {
        int key, val;
        Node *prev, *next;
        Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
    };
    int cap;
    unordered_map<int, Node*> map;
    Node *head, *tail;

    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    void add(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }
public:
    LRUCache(int capacity) : cap(capacity) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }
    ~LRUCache() {
        Node* current = head;
        while (current) {
            Node* next = current->next;
            delete current;
            current = next;
        }
    }
    LRUCache(const LRUCache&) = delete;
    LRUCache& operator=(const LRUCache&) = delete;
    int get(int key) {
        if (!map.count(key)) return -1;
        Node* node = map[key];
        remove(node);
        add(node);
        return node->val;
    }
    void put(int key, int value) {
        if (map.count(key)) {
            Node* existing = map[key];
            existing->val = value;
            remove(existing);
            add(existing);
            return;
        }
        Node* node = new Node(key, value);
        add(node);
        map[key] = node;
        if (map.size() > cap) {
            Node* lru = tail->prev;
            remove(lru);
            map.erase(lru->key);
            delete lru;
        }
    }
};

java
import java.util.HashMap;

class LRUCache {
    class Node {
        int key, val;
        Node prev, next;
        Node(int key, int val) { this.key = key; this.val = val; }
    }
    private int cap;
    private HashMap<Integer, Node> map = new HashMap<>();
    private Node head, tail;

    public LRUCache(int capacity) {
        this.cap = capacity;
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void add(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        remove(node);
        add(node);
        return node.val;
    }
    public void put(int key, int value) {
        if (map.containsKey(key)) remove(map.get(key));
        Node node = new Node(key, value);
        add(node);
        map.put(key, node);
        if (map.size() > cap) {
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.key);
        }
    }
}

python
class Node:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

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

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

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, value)
        self._add(node)
        self.map[key] = node
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

javascript
class Node {
    constructor(key = 0, val = 0) {
        this.key = key;
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

class LRUCache {
    constructor(capacity) {
        this.cap = capacity;
        this.map = new Map();
        this.head = new Node();
        this.tail = new Node();
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    _remove(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    _add(node) {
        node.next = this.head.next;
        node.prev = this.head;
        this.head.next.prev = node;
        this.head.next = node;
    }
    get(key) {
        if (!this.map.has(key)) return -1;
        let node = this.map.get(key);
        this._remove(node);
        this._add(node);
        return node.val;
    }
    put(key, value) {
        if (this.map.has(key)) this._remove(this.map.get(key));
        let node = new Node(key, value);
        this._add(node);
        this.map.set(key, node);
        if (this.map.size > this.cap) {
            let lru = this.tail.prev;
            this._remove(lru);
            this.map.delete(lru.key);
        }
    }
}

Time Complexity: expected O(1) | Space Complexity: O(capacity)

3. Summary Table

Explore more practice problems on DSAMaster's practice platform.