LRU Cache: Design with Hash Map + Doubly Linked List

An LRU (Least Recently Used) cache is a fixed-capacity key-value store that, when full, evicts the item that was used least recently to make room for a new one. The design challenge — a classic interview question — is to make both get and put run in O(1). The trick is to combine two structures: a hash map for instant lookup and a doubly linked list to track usage order.

Why two structures?

A hash map gives O(1) lookup by key — but has no notion of order.
A doubly linked list gives O(1) insertion and removal if you already hold the node — and naturally maintains an ordering (most-recent at the front, least-recent at the back).

Store each value in a list node, and let the hash map point key → node. On any access you can find the node in O(1) (map) and move it to the front in O(1) (list). Eviction removes the back node.

// Sketch of the layout:
// map:  key -> node
// list: [most recent] <-> ... <-> [least recent]
// get(k):  node = map[k]; move node to front; return node->val
// put(k):  if exists, update + move to front;
//          else add at front; if over capacity, drop the back node

// Sketch of the layout:
// map:  key -> node
// list: [most recent] <-> ... <-> [least recent]
// get(k):  node = map[k]; move node to front; return node.val
// put(k):  if exists, update + move to front;
//          else add at front; if over capacity, drop the back node

// Sketch of the layout:
// map:  key -> node
// list: [most recent] <-> ... <-> [least recent]
// get(k):  node = map[k]; move node to front; return node.val
// put(k):  if exists, update + move to front;
//          else add at front; if over capacity, drop the back node

# Sketch of the layout:
# map:  key -> node
# list: [most recent] <-> ... <-> [least recent]
# get(k):  node = map[k]; move node to front; return node.val
# put(k):  if exists, update + move to front;
#          else add at front; if over capacity, drop the back node

Full implementation

We use two sentinel nodes (head and tail) so insertion and removal never hit a null edge case. C++ and Java build the doubly linked list explicitly; JavaScript and Python lean on their insertion-ordered maps (Map / dict), which give the same O(1) behavior with less code.

#include <list>
#include <unordered_map>

class LRUCache {
    int cap;
    std::list<std::pair<int,int>> items;             // front = most recent
    std::unordered_map<int, std::list<std::pair<int,int>>::iterator> pos;
public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto it = pos.find(key);
        if (it == pos.end()) return -1;
        items.splice(items.begin(), items, it->second); // move to front
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = pos.find(key);
        if (it != pos.end()) {
            it->second->second = value;
            items.splice(items.begin(), items, it->second);
            return;
        }
        if ((int)items.size() == cap) {              // evict least recent
            pos.erase(items.back().first);
            items.pop_back();
        }
        items.emplace_front(key, value);
        pos[key] = items.begin();
    }
};

import java.util.HashMap;

class LRUCache {
    static class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }
    private final int cap;
    private final HashMap<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0), tail = new Node(0, 0);

    LRUCache(int capacity) {
        cap = capacity;
        head.next = tail;
        tail.prev = head;
    }
    private void remove(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
    private void addFront(Node n) {
        n.next = head.next; n.prev = head;
        head.next.prev = n; head.next = n;
    }
    int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;
        remove(n); addFront(n);                      // move to front
        return n.val;
    }
    void put(int key, int value) {
        Node n = map.get(key);
        if (n != null) { n.val = value; remove(n); addFront(n); return; }
        if (map.size() == cap) {                     // evict least recent
            Node lru = tail.prev;
            remove(lru); map.remove(lru.key);
        }
        Node fresh = new Node(key, value);
        addFront(fresh); map.put(key, fresh);
    }
}

class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();        // insertion order = usage order (oldest first)
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    this.map.delete(key);        // re-insert to mark most recent
    this.map.set(key, val);
    return val;
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    else if (this.map.size === this.cap) {
      this.map.delete(this.map.keys().next().value); // evict oldest
    }
    this.map.set(key, value);
  }
}

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = OrderedDict()         # ordered by usage (oldest first)

    def get(self, key):
        if key not in self.map:
            return -1
        self.map.move_to_end(key)        # mark most recent
        return self.map[key]

    def put(self, key, value):
        if key in self.map:
            self.map.move_to_end(key)
        self.map[key] = value
        if len(self.map) > self.cap:
            self.map.popitem(last=False)  # evict oldest

Going deeper: Python’s OrderedDict.move_to_end and JS’s delete-then-set both achieve O(1) reordering; under the hood they’re doing exactly what the explicit C++/Java linked list does. The explicit version is worth knowing for interviews that ban built-in ordered maps.

Complexity

Operation	Time	Space
`get`	O(1)	—
`put`	O(1)	—
Total	—	O(capacity)

Common pitfalls

Forgetting to reorder on get. A read counts as a use — move the item to the front, or your eviction order is wrong.
Updating an existing key. A put on a present key must refresh both the value and its recency; don’t double-insert.
Evicting before inserting the new key. Check capacity and evict the back node first, then add the new front node.
Stale map entries. When you evict a list node, remove its key from the map too, or lookups will dereference dead nodes.

When to use it

LRU is the default eviction policy for caches everywhere — CPU caches, database buffer pools, web/CDN caches, and memoization with a memory budget. Want to build one end to end? See the LRU cache project, or practice the design on the advanced exercises.