SyntaxPilot
Courses/DSA and Coding Problems/Lesson 25
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 25 of 90

LRU cache: hash map + doubly linked list

queued

These are the notes for DSA episode 25, the classic design question that closes the linked list block. Build a cache with a fixed capacity where get and put both run in O(1) average time and, when it is full, the least recently used key is thrown out. The obvious way keeps an ArrayList in recency order: it is correct, but every call scans and shifts, so 4 lakh calls on a 1-lakh cache hit Time Limit Exceeded. The fix glues two structures together: a HashMap from key to node finds any key instantly, and a doubly linked list with dummy head and tail keeps the order and lets you unhook any node in O(1). Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

A phone has room for only 2 apps in memory. You open Maps, then Music. You switch back to Maps: it jumps to the front of the recent-apps screen. Then you open Camera, and there's no room. Maps was just used, so the phone closes Music, the app untouched the longest. That rule is LRU: least recently used.

On the phone In the code
Apps kept in memory Entries in the cache
Room for 2 apps capacity
Opening an app get(key) or put(key, value): a "use"
The front of the recent-apps screen The most recently used key (head.next)
The app closed to make room The evicted key (tail.prev)

A cache is a small, fast memory that keeps copies of things you used recently. A hit means the item is in the cache (fast); a miss means you go to the slow place (disk, network). When the cache is full you must evict (throw out) one entry. Browsers, databases, operating systems and CPUs all use LRU-style caches.

Problem statement

Design a class LRU(capacity) with:

  • get(key): return the value if the key is present, else -1. This counts as a use.
  • put(key, value): insert or update the key. This counts as a use. If a new key makes the cache exceed capacity, evict the least recently used key first.

Both must run in O(1) average time.

capacity 2:
put(1,1) put(2,2) get(1) put(3,3) get(2) put(4,4) get(1) get(3) get(4)
            →        1            -1           -1     3      4

Edge cases: capacity 1, put on an existing key (update the value and make it most recent), get of a missing key.

Brute force: an ArrayList in recency order

Keep [key, value] pairs in an ArrayList, oldest first, newest last. get scans for the key, removes it and appends it; put removes any old pair, appends, and drops index 0 when over capacity.

    static class LRU {
        int cap;
        ArrayList<int[]> list = new ArrayList<>();
        LRU(int cap) { this.cap = cap; }
        int find(int key) {
            for (int i = 0; i < list.size(); i++)
                if (list.get(i)[0] == key) return i;
            return -1;
        }
        int get(int key) {
            int i = find(key);
            if (i == -1) return -1;
            int[] e = list.remove(i);
            list.add(e);
            return e[1];
        }
        void put(int key, int value) {
            int i = find(key);
            if (i != -1) list.remove(i);
            list.add(new int[]{key, value});
            if (list.size() > cap) list.remove(0);
        }
    }

The example prints 1 -1 -1 3 4. Correct.

The big input: 4 lakh calls

Capacity 1 lakh; put 2 lakh keys, then get 2 lakh keys:

        int n = 100000;
        LRU c = new LRU(n);
        long t0 = System.nanoTime();
        for (int i = 0; i < 2 * n; i++) c.put(i, i);
        for (int i = 0; i < 2 * n; i++) c.get(i);
        long ms = (System.nanoTime() - t0) / 1000000;
        System.out.println("4 lakh calls, " + ms + " ms");

Result: Time Limit Exceeded.

Why the brute force fails

  • find(key) scans the list: O(n).
  • ArrayList.remove(i) and remove(0) shift every element after i: O(n).
Capacity Steps (about 4 calls × n each, per key)
1,000 ~40 lakh: instant
10,000 ~40 crore
1 lakh ~4 × 10¹⁰: TLE

We need two things at once: (1) find any key instantly, (2) move any entry to the "newest" end and drop the oldest instantly.

The key insight: two structures, glued together

Think of a hotel: the reception register maps a guest's name to a room (find anyone instantly), and the rooms along a corridor are kept in order of last visit. The register doesn't store the guest's luggage, it points at the room.

Need Structure Cost
Find a key HashMap<Integer, Node> O(1) average
Keep recency order Doubly linked list, newest at the front O(1) to move/unhook a node you hold
Know which key to delete on eviction Node stores its key O(1) map.remove(lru.key)

Why doubly linked? To unhook node x you need its previous node: x.prev.next = x.next; x.next.prev = x.prev;. In a singly linked list x doesn't know its previous node, so you'd walk from the head: O(n).

Why dummy head and tail? With a fake head and fake tail, every real node always has a real prev and next, so no null checks. The newest node is always head.next; the eviction victim is always tail.prev.

Trace with capacity 2:

Operation List (head → tail) Map keys Note
start H ⇄ T {} empty
put(1,1), put(2,2) H ⇄ 2 ⇄ 1 ⇄ T 1, 2 new nodes go after H
get(1) H ⇄ 1 ⇄ 2 ⇄ T 1, 2 unhook 1, add after H
put(3,3) H ⇄ 3 ⇄ 1 ⇄ T 1, 3 full: victim tail.prev = 2, removed from list and map

The optimal solution in Java

import java.util.*;

public class Main {
    static class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }
    static class LRU {
        int cap;
        HashMap<Integer, Node> map = new HashMap<>();
        Node head = new Node(0, 0), tail = new Node(0, 0);
        LRU(int cap) {
            this.cap = cap;
            head.next = tail; tail.prev = head;
        }
        void remove(Node x) {
            x.prev.next = x.next;
            x.next.prev = x.prev;
        }
        void addFront(Node x) {
            x.next = head.next; x.prev = head;
            head.next.prev = x; head.next = x;
        }
        int get(int key) {
            Node x = map.get(key);
            if (x == null) return -1;
            remove(x); addFront(x);
            return x.val;
        }
        void put(int key, int value) {
            Node x = map.get(key);
            if (x != null) { x.val = value; remove(x); addFront(x); return; }
            x = new Node(key, value);
            map.put(key, x); addFront(x);
            if (map.size() > cap) {
                Node lru = tail.prev;
                remove(lru); map.remove(lru.key);
            }
        }
    }
    public static void main(String[] args) {
        LRU c = new LRU(2);
        c.put(1, 1); c.put(2, 2);
        System.out.print(c.get(1) + " ");
        c.put(3, 3);
        System.out.print(c.get(2) + " ");
        c.put(4, 4);
        System.out.println(c.get(1) + " " + c.get(3) + " " + c.get(4));
        LRU one = new LRU(1);
        one.put(1, 10); one.put(2, 20);
        System.out.println(one.get(1) + " " + one.get(2));
        LRU u = new LRU(2);
        u.put(1, 1); u.put(2, 2); u.put(1, 100); u.put(3, 3);
        System.out.println(u.get(1) + " " + u.get(2) + " " + u.get(3));
    }
}

Output:

1 -1 -1 3 4
-1 20
100 -1 3
  • The example is correct.
  • Capacity 1: put(2, 20) evicts 1, so get(1) is -1, get(2) is 20.
  • Updating key 1 to 100 makes it the most recent, so put(3, 3) evicts 2: 100 -1 3.

With capacity 1 lakh and the same 4 lakh calls: 4 lakh calls, 128 ms (the exact time varies run to run).

Java's shortcut: LinkedHashMap

LinkedHashMap is a hash map with a doubly linked list inside. The third constructor argument true means access order (every get/put moves the entry to the end), and removeEldestEntry decides eviction:

    static class LRU extends LinkedHashMap<Integer, Integer> {
        int cap;
        LRU(int cap) { super(16, 0.75f, true); this.cap = cap; }
        int get(int key) { return getOrDefault(key, -1); }
        void put(int key, int value) { super.put(key, value); }
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> e) {
            return size() > cap;
        }
    }

Same example, same output: 1 -1 -1 3 4. Use it in real projects; in interviews you're usually asked to build the hand-made version.

The same solution in C++

std::list is a doubly linked list, and splice moves a node to the front in O(1) without copying it. The map stores the node's iterator.

#include <bits/stdc++.h>
using namespace std;

class LRUCache {
    int cap;
    list<pair<int, int>> order;                          // front = most recent: {key, value}
    unordered_map<int, list<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;
        order.splice(order.begin(), order, it->second);  // move to front in O(1)
        return it->second->second;
    }
    void put(int key, int value) {
        auto it = pos.find(key);
        if (it != pos.end()) {
            it->second->second = value;
            order.splice(order.begin(), order, it->second);
            return;
        }
        order.emplace_front(key, value);
        pos[key] = order.begin();
        if ((int)pos.size() > cap) {
            pos.erase(order.back().first);
            order.pop_back();
        }
    }
};

int main() {
    LRUCache c(2);
    c.put(1, 1); c.put(2, 2);
    cout << c.get(1) << " ";
    c.put(3, 3);
    cout << c.get(2) << " ";
    c.put(4, 4);
    cout << c.get(1) << " " << c.get(3) << " " << c.get(4) << "\n";
}

Output: 1 -1 -1 3 4

The same solution in Python

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

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

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

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

    def get(self, key):
        x = self.map.get(key)
        if x is None:
            return -1
        self._remove(x); self._add_front(x)
        return x.val

    def put(self, key, value):
        x = self.map.get(key)
        if x:
            x.val = value
            self._remove(x); self._add_front(x)
            return
        x = Node(key, value)
        self.map[key] = x
        self._add_front(x)
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

c = LRUCache(2)
c.put(1, 1); c.put(2, 2)
r = [c.get(1)]
c.put(3, 3); r.append(c.get(2))
c.put(4, 4); r += [c.get(1), c.get(3), c.get(4)]
print(*r)

Output: 1 -1 -1 3 4

Python shortcut with collections.OrderedDict (move_to_end and popitem(last=False) are O(1)):

from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity):
        self.cap, self.d = capacity, OrderedDict()
    def get(self, key):
        if key not in self.d: return -1
        self.d.move_to_end(key)
        return self.d[key]
    def put(self, key, value):
        self.d[key] = value
        self.d.move_to_end(key)
        if len(self.d) > self.cap: self.d.popitem(last=False)
c = LRUCache(2)
c.put(1, 1); c.put(2, 2); r = [c.get(1)]; c.put(3, 3); r.append(c.get(2)); c.put(4, 4); r += [c.get(1), c.get(3), c.get(4)]
print(*r)

Output: 1 -1 -1 3 4

Three real bugs

Bug 1: forgetting map.remove(lru.key) on eviction

                remove(lru);   // the key stays in the map

Real output on the example: 1 2 1 3 4. get(2) should be -1, but the map still points at the evicted node, so the "ghost" comes back (and unhooking a node that's no longer in the list corrupts the neighbours). The map also keeps growing: a memory leak.

Bug 2: get doesn't move the node to the front

            if (x == null) return -1;
            return x.val;

Real output: 1 2 -1 3 4. Reading key 1 didn't count as a use, so put(3, 3) evicted 1 instead of 2. That's FIFO (first in, first out), not LRU.

Bug 3: a node without its key

    static class Node {
        int val;
        ...

Real compile error:

Main.java:38: error: cannot find symbol
                remove(lru); map.remove(lru.key);
                                           ^
  symbol:   variable key
  location: variable lru of type Node
1 error

At eviction you hold only the node; it is the only thing that can tell you which key to delete from the map.

Complexity

Approach get put Space 4 lakh calls, cap 1 lakh
ArrayList in recency order O(n) O(n) O(capacity) Time Limit Exceeded
HashMap + singly linked list O(n) (find the previous node) O(n) O(capacity) too slow
HashMap + doubly linked list O(1) avg O(1) avg O(capacity) 128 ms
LinkedHashMap(…, true) O(1) avg O(1) avg O(capacity) same idea, built in

"Average" because a hash map lookup is O(1) on average (it can degrade with many collisions).

Common mistakes

Mistake What you see Why Fix
remove(lru); without map.remove(lru.key) 1 2 1 3 4 the map still points at evicted nodes remove from the list and the map
get doesn't move the node 1 2 -1 3 4 reads don't count as use: FIFO remove(x); addFront(x); in get
Node without key error: cannot find symbol eviction can't tell the map what to delete store key and val in the node
put on an existing key adds a second node the map and the list disagree, wrong evictions old node left in the list update the value and move the node
Using ArrayList / singly linked list Time Limit Exceeded finding or unhooking is O(n) HashMap + doubly linked list
No dummy nodes NullPointerException at the ends head.prev/tail.next are null dummy head and tail

Mini project: a photo-thumbnail cache

A gallery app keeps the thumbnails of the last 3 photos you opened in memory; anything else is loaded from disk. Add a peek (look without counting as a use) and a size, then count disk loads:

        LRU c = new LRU(2);
        c.put(1, 1); c.put(2, 2);
        System.out.print(c.peek(1) + " ");
        c.put(3, 3);
        System.out.println(c.get(1) + " " + c.get(2) + " size " + c.size());
        LRU thumbs = new LRU(3);
        int[] opened = {7, 3, 7, 9, 4, 3, 7};
        int loads = 0;
        for (int photo : opened) {
            if (thumbs.get(photo) == -1) { loads++; thumbs.put(photo, photo * 100); }
        }
        System.out.println("disk loads: " + loads + " of " + opened.length);

with, inside LRU:

        int peek(int key) {
            Node x = map.get(key);
            return x == null ? -1 : x.val;
        }
        int size() { return map.size(); }

Real output:

1 -1 2 size 2
disk loads: 6 of 7

peek(1) didn't count as a use, so put(3, 3) evicted 1. Only the second open of photo 7 was a hit.

Practice

1. What does get return on an empty cache?

Solution

-1: map.get(key) is null.

2. Why does put on an existing key not trigger an eviction?

Solution

The number of keys doesn't change. The code updates the value, moves the node to the front, and returns before the size check.

3. Trace capacity 2: put(1,1) put(2,2) put(1,10) put(3,3) get(2) get(1).

Solution

put(1,10) makes 1 most recent, so put(3,3) evicts 2. get(2) = -1, get(1) = 10.

4. LFU cache (harder): evict the least frequently used key, ties broken by LRU.

Solution

Keep key → node (value, frequency), a map frequency → doubly linked list of nodes with that frequency (each list in LRU order), and minFreq. On a use, move the node from list f to list f + 1 (update minFreq if list f became empty and f == minFreq). To evict, remove tail.prev of the minFreq list. A new key gets frequency 1 and sets minFreq = 1. All operations O(1).

5. LRU with a time-to-live: entries expire after t seconds.

Solution

Store an expiresAt timestamp in each node. In get, if now >= expiresAt, remove the node from the list and the map and return -1. Eviction for capacity stays tail.prev.

Quick quiz

LRU c = new LRU(3);
c.put(1, 1); c.put(2, 2); c.put(3, 3);
c.get(1); c.put(4, 4); c.get(3); c.put(5, 5);

Which keys are left?

  • 1, 3, 5
  • 3, 4, 5
  • 1, 4, 5
  • 2, 3, 5
Answer

3, 4, 5. After get(1) the order (newest first) is 1, 3, 2, so put(4) evicts 2 → 4, 1, 3. get(3) → 3, 4, 1, so put(5) evicts 1 → 5, 3, 4. (Real output of System.out.println(c.map.keySet()): [3, 4, 5].)

Interview questions

  1. Design an LRU cache with O(1) get and put. HashMap from key to node + doubly linked list in recency order with dummy head and tail; move to front on every use; evict tail.prev.
  2. Why a doubly linked list, not singly? Unhooking a node needs its previous node; a singly linked list would need an O(n) walk.
  3. Why does the node store the key? On eviction, the node is all you have; you need its key to delete it from the map.
  4. Why dummy nodes? No null checks at either end; newest is head.next, victim is tail.prev.
  5. Is it really O(1)? Average O(1): hash map operations are O(1) on average.
  6. How would you make it thread-safe? Simplest: a lock around get/put (both mutate the list). For high concurrency: segment the cache into shards, each with its own lock.
  7. What does Java give you for free? LinkedHashMap with accessOrder = true and removeEldestEntry.
  8. LRU vs LFU vs FIFO? LRU evicts the oldest use; LFU the fewest uses; FIFO the oldest insertion, ignoring reads.

Glossary

Term Meaning
Cache A small, fast memory that keeps copies of recently used data
Hit / miss The item is / isn't in the cache
Evict Throw an entry out of a full cache to make room
LRU (least recently used) Eviction policy: remove the entry whose last use is oldest
FIFO (first in, first out) Remove the entry inserted first, ignoring reads
LFU (least frequently used) Remove the entry used the fewest times
Capacity The maximum number of entries the cache holds
HashMap Key → value store with O(1) average lookup
Doubly linked list Each node has prev and next, so any node can be unhooked in O(1)
Dummy (sentinel) node A fake node at an end so real nodes never have null neighbours
head.next / tail.prev The most recent node / the least recently used node
LinkedHashMap (access order) Java's built-in hash map + doubly linked list
O(1) average Constant time on average, independent of the cache size
Time Limit Exceeded (TLE) Too slow for the judge's limit (8 s in the SyntaxPilot compiler)

Summary

  • An LRU cache evicts the key whose last use is oldest; get and put both count as uses.
  • An ordered ArrayList is O(n) per call and times out.
  • HashMap<key, Node> + doubly linked list (dummy head/tail): move to front on every use, evict tail.prev and map.remove(lru.key). O(1) average per call, O(capacity) space.
  • Java: LinkedHashMap(16, 0.75f, true) + removeEldestEntry. Python: OrderedDict. C++: list + unordered_map + splice.

Next episode: Stacks: valid parentheses.