Project: Implement an LRU Cache from Scratch

In this project you’ll build an LRU (Least Recently Used) cache — a fixed-capacity store that, when full, evicts whichever key was accessed longest ago. The challenge is doing both get and put in O(1). The classic answer combines two structures: a hash map for instant key lookup, and a doubly linked list that keeps entries ordered by recency. This is one of the most-asked interview problems; the concept page is LRU Cache.

What you’ll build

A cache with two operations:

get(key) — return the value if present (and mark it most-recently used), else a “miss”.
put(key, value) — insert or update; if over capacity, evict the least-recently-used entry first.

Why two structures

No single common structure gives O(1) for everything you need:

A hash map finds a key in O(1) but has no notion of order.
A doubly linked list can move a node to the front or drop the tail in O(1) if you already hold the node — but finding a node by key would be O(n).

Combine them: the hash map maps key → node, and the node lives in the linked list. Lookup is O(1) via the map; reordering and eviction are O(1) via the list. The “most recent” end is the head; the “least recent” victim is always at the tail.

For beginners: Why doubly linked? To unlink a node in O(1) you need its predecessor. A singly linked list would force an O(n) scan to find it. Storing a prev pointer makes removal a couple of pointer assignments. See Doubly Linked List.

The design

Use two sentinel nodes — a dummy head and dummy tail — so insertion and removal never hit a null edge case. Two helpers do all the pointer work: remove(node) unlinks a node, and addFront(node) splices a node right after head. Then:

get: look up the node; if found, remove then addFront (now most recent) and return its value.
put: if the key exists, update value and move to front. Otherwise, if full, evict tail.prev (the LRU node) and erase it from the map; then create a node, add to front, and record it in the map.

#include <unordered_map>

class LRUCache {
    struct Node {
        int key, value;
        Node* prev = nullptr;
        Node* next = nullptr;
        Node(int k, int v) : key(k), value(v) {}
    };
    int capacity;
    std::unordered_map<int, Node*> map;
    Node* head; // most-recent side
    Node* tail; // least-recent side

    void remove(Node* n) {
        n->prev->next = n->next;
        n->next->prev = n->prev;
    }
    void addFront(Node* n) {
        n->next = head->next;
        n->prev = head;
        head->next->prev = n;
        head->next = n;
    }
public:
    LRUCache(int cap) : capacity(cap) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) return -1; // miss
        Node* n = it->second;
        remove(n);
        addFront(n);
        return n->value;
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            it->second->value = value;
            remove(it->second);
            addFront(it->second);
            return;
        }
        if ((int)map.size() == capacity) {
            Node* lru = tail->prev;
            remove(lru);
            map.erase(lru->key);
            delete lru;
        }
        Node* n = new Node(key, value);
        addFront(n);
        map[key] = n;
    }
};

import java.util.HashMap;
import java.util.Map;

class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;
        Node(int k, int v) { key = k; value = v; }
    }
    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0); // most-recent side
    private final Node tail = new Node(0, 0); // least-recent side

    LRUCache(int capacity) {
        this.capacity = 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; // miss
        remove(n);
        addFront(n);
        return n.value;
    }

    void put(int key, int value) {
        Node existing = map.get(key);
        if (existing != null) {
            existing.value = value;
            remove(existing);
            addFront(existing);
            return;
        }
        if (map.size() == capacity) {
            Node lru = tail.prev;
            remove(lru);
            map.remove(lru.key);
        }
        Node n = new Node(key, value);
        addFront(n);
        map.put(key, n);
    }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = { key: 0, value: 0 }; // most-recent side
    this.tail = { key: 0, value: 0 }; // least-recent side
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  #remove(n) {
    n.prev.next = n.next;
    n.next.prev = n.prev;
  }
  #addFront(n) {
    n.next = this.head.next;
    n.prev = this.head;
    this.head.next.prev = n;
    this.head.next = n;
  }

  get(key) {
    const n = this.map.get(key);
    if (n === undefined) return -1; // miss
    this.#remove(n);
    this.#addFront(n);
    return n.value;
  }

  put(key, value) {
    const existing = this.map.get(key);
    if (existing !== undefined) {
      existing.value = value;
      this.#remove(existing);
      this.#addFront(existing);
      return;
    }
    if (this.map.size === this.capacity) {
      const lru = this.tail.prev;
      this.#remove(lru);
      this.map.delete(lru.key);
    }
    const n = { key, value };
    this.#addFront(n);
    this.map.set(key, n);
  }
}

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

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.head = Node()  # most-recent side
        self.tail = Node()  # least-recent side
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _add_front(self, n):
        n.next = self.head.next
        n.prev = self.head
        self.head.next.prev = n
        self.head.next = n

    def get(self, key):
        n = self.map.get(key)
        if n is None:
            return -1  # miss
        self._remove(n)
        self._add_front(n)
        return n.value

    def put(self, key, value):
        existing = self.map.get(key)
        if existing is not None:
            existing.value = value
            self._remove(existing)
            self._add_front(existing)
            return
        if len(self.map) == self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]
        n = Node(key, value)
        self._add_front(n)
        self.map[key] = n

Trying it out

With capacity 2: put(1,1), put(2,2), get(1) returns 1 (now 1 is most recent), put(3,3) evicts key 2, so get(2) returns the miss value -1.

Gotcha: On a put that updates an existing key, you must still move it to the front — an update counts as a use. Forgetting this is the most common LRU bug.

Complexity

get / put: O(1) average — one hash lookup plus a constant number of pointer updates.
space: O(capacity) for the stored entries.

Going deeper: Most languages ship an ordered map that hides the linked list — C++ std::list, Java LinkedHashMap (with accessOrder=true and removeEldestEntry), JS Map (insertion-ordered), Python collections.OrderedDict (move_to_end). They’re great in production, but building it by hand is what teaches you the structure. For a thread-safe or time-expiring variant, layer a TTL on each node.

Next project: a pathfinding visualizer.