LeetCode 146 · Medium · Linked List

LRU Cache

Design a cache with a fixed capacity. get(key) returns the value or −1; put(key, value) inserts or updates. When a put overflows the capacity, evict the least recently used key. Both calls must run in O(1).

O(1)get and put
O(capacity)space
map + listdoubly linked, by recency

capacity 1–4 · put k v and get k, separated by ; or commas · 1–12 calls · keys 0–9, values 0–99

Doubly linked list key:value · left = least recent end, right = most recent · arrow over = next, curve under = prev · row 2 = unlinked node

cache hash map · key → its node, so any node is found in O(1)

class LRUCache { private final int cap; private final Map<Integer, Node> cache = new HashMap<>(); // key to node private final Node left = new Node(0, 0), right = new Node(0, 0); public LRUCache(int capacity) { this.cap = capacity; left.next = right; right.prev = left; } private void remove(Node node) { Node prev = node.prev, nxt = node.next; prev.next = nxt; nxt.prev = prev; } private void insert(Node node) { // just before right Node prev = right.prev, nxt = right; prev.next = node; nxt.prev = node; node.next = nxt; node.prev = prev; } public int get(int key) { if (cache.containsKey(key)) { remove(cache.get(key)); insert(cache.get(key)); return cache.get(key).val; } return -1; } public void put(int key, int value) { if (cache.containsKey(key)) { remove(cache.get(key)); } cache.put(key, new Node(key, value)); insert(cache.get(key)); if (cache.size() > cap) { Node lru = left.next; // least recently used remove(lru); cache.remove(lru.key); } } private static class Node { // keeps its key, for eviction int key, val; Node prev, next; Node(int key, int val) { this.key = key; this.val = val; } }}
call
—
returns
—
cache.size()
—
outputs
—

Why it works

  1. Brute force keeps a list of keys by recency: every get and put must find the key in that list and move it to the end, and eviction scans for the oldest. O(capacity) per call.
  2. Two structures, each doing what it is fast at. The hash map finds a key's node in O(1). The doubly linked list keeps recency order: the node after left is the least recent, the node before right the most recent. Touching a key means cutting its node out and splicing it in before right.
  3. Everything is O(1): remove and insert rewire a fixed four pointers, because each node knows its own prev. A singly linked list could not unlink a node without walking to its predecessor.
  4. Sentinels remove edge cases. left and right are dummy nodes that never move, so the list is never truly empty and no pointer is ever null inside remove or insert.
  5. Pitfall: the node stores its key. On eviction you reach the node from left.next, and cache.remove(lru.key) needs the key to clean up the map. Also, a get counts as a use: it must move the node too.
  6. In practice: a LinkedHashMap built with accessOrder = true and an overridden removeEldestEntry is this exact structure. LFU Cache (460) adds a frequency count on top.