Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

LRU Cache
DSA

LRU Cache

Learn how a hash map and doubly linked list combine to implement an efficient Least Recently Used cache.

An LRU cache evicts the least recently used entry when full.

The two-structure trick:

A hashmap gives O(1) lookup; a doubly-linked list orders entries by recency. Map values point at list nodes so a “touch” is O(1) pointer surgery.

Focus on recognizing:

“Evict least recently used” + O(1) = map → linked-list nodes

Core Template

Watch a capacity-2 cache absorb put(1,A), put(2,B), get(1), put(3,C), get(2) — the eviction lands on the untouched key. Press ▶ to animate.

LRU Cache

Evict the least-recently-used item on capacity overflow.

A doubly-linked list keeps recency (MRU at head, LRU at tail) with a hash map key→node. get moves the node to head; put inserts at head and, if over capacity, drops the tail. Both ops are O(1).

LINKED LIST VISUALIZER
Steps –
1:A
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        map: key → node;   doubly-linked list: MRU at head
                      
                        2
                        get(k): if missing → -1; else move node to head, return value
                      
                        3
                        put(k,v): existing → update + move to head
                      
                        4
                                  new → insert at head; over capacity → evict tail
                      
class LRUCache {
    static class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    private final int cap;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0);   // MRU side
    private final Node tail = new Node(0, 0);   // LRU side

    public LRUCache(int capacity) {
        cap = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        remove(node);
        insert(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) remove(map.get(key));
        if (map.size() == cap) remove(tail.prev);   // evict LRU

        insert(new Node(key, value));
    }

    private void remove(Node n) {
        map.remove(n.key);
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void insert(Node n) {               // at head = MRU
        map.put(n.key, n);
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
    }
}
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.data = OrderedDict()   # first item = LRU

    def get(self, key: int) -> int:
        if key not in self.data:
            return -1
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key: int, value: int) -> None:
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if len(self.data) > self.cap:
            self.data.popitem(last=False)   # evict LRU
class LRUCache {
    int cap;
    list<pair<int, int>> items;   // front = MRU
    unordered_map<int, list<pair<int, int>>::iterator> map;

public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) return -1;

        items.splice(items.begin(), items, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            it->second->second = value;
            items.splice(items.begin(), items, it->second);
            return;
        }

        if ((int)items.size() == cap) {
            map.erase(items.back().first);
            items.pop_back();
        }

        items.emplace_front(key, value);
        map[key] = items.begin();
    }
};
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.data = new Map(); // insertion order = LRU → MRU
  }

  get(key) {
    if (!this.data.has(key)) return -1;

    const val = this.data.get(key);
    this.data.delete(key);
    this.data.set(key, val); // bump to MRU
    return val;
  }

  put(key, value) {
    if (this.data.has(key)) this.data.delete(key);

    this.data.set(key, value);
    if (this.data.size > this.cap)
      this.data.delete(this.data.keys().next().value); // oldest
  }
}

Java needs the manual list; Python/JS give you an ordered container for free — know both versions.

What Makes It O(1)?

The map stores nodes, not values

map[key] → linked-list node

because finding the value AND its position must both be O(1). Storing bare values would force an O(n) list scan on every touch.

Sentinel head/tail nodes

Dummy head and tail eliminate every null check at the ends — remove/insert are pure pointer rewires.

LRU = map for lookup + list for order + sentinels for clean edges.

Common Mistakes

Forgetting to move on get.

A read is also a “use” — get must bump the key to MRU or eviction order goes stale.

Evicting before checking existence in put.

Update-in-place path (key exists) must not trigger eviction. Handle update first, then capacity.

Broken pointer updates.

Every insert/remove touches four pointers. Draw it once carefully; test edge cases (single element, evicting the only element).

Complexity

OperationTime
getO(1)
putO(1)
SpaceO(capacity)

My Private Notes

Notes are auto-saved locally to this device.