Implement an LRU Cache in Java
Problem
An LRU (least recently used) cache holds a limited number of entries; when it's full, adding a new entry evicts the one that hasn't been read or written for the longest time.
Build a cache with room for three entries that evicts the least recently used key when a fourth is added.
Java Program
import java.util.LinkedHashMap;
import java.util.Map;
public class LruCacheLinkedHashMap {
static class LruCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
LruCache(int capacity) {
super(16, 0.75f, true); // true = access order: every get() moves the entry to the end
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity; // evict the least recently used entry once we're over capacity
}
}
public static void main(String[] args) {
LruCache<String, Integer> cache = new LruCache<>(3);
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
System.out.println("Start: " + cache.keySet());
cache.get("a"); // "a" becomes the most recently used
System.out.println("After get(a): " + cache.keySet());
cache.put("d", 4); // over capacity, so the least recently used ("b") is evicted
System.out.println("After put(d): " + cache.keySet());
System.out.println("Contains b? " + cache.containsKey("b"));
}
}Output
Core Logic
LinkedHashMap can keep its entries in access order and lets a subclass decide when to drop the eldest one — together that is exactly an LRU cache.
- 1The constructor
super(16, 0.75f, true)switches the map from insertion order to access order, so everygetorputmoves that key to the end. - 2The front of the map is therefore always the least recently used entry.
- 3
removeEldestEntryruns after each insertion and returnstrueoncesize()exceeds the capacity, which removes the front entry. - 4The
keySet()printouts show the order from least to most recently used.
get("a"), the order is [b, c, a], so adding d evicts b, not a.Key Point: Forgetting the true access-order flag gives a FIFO cache instead — entries would be evicted by insertion time even if they were read a moment ago.
Why: Hash lookups and the linked-list reordering behind LinkedHashMap are constant time, and at most capacity entries are stored.
Key Concepts
Approach 2: HashMap and Doubly Linked List
import java.util.HashMap;
import java.util.Map;
public class LruCacheManual {
static class Node {
String key;
int value;
Node prev, next;
Node(String key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<String, Node> map = new HashMap<>();
private final Node head = new Node("", 0); // sentinel before the most recent entry
private final Node tail = new Node("", 0); // sentinel after the least recent entry
LruCacheManual(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
Integer get(String key) {
Node node = map.get(key);
if (node == null) return null;
unlink(node);
addToFront(node); // touched, so it becomes the most recent
return node.value;
}
void put(String key, int value) {
Node node = map.get(key);
if (node != null) {
node.value = value;
unlink(node);
addToFront(node);
return;
}
if (map.size() == capacity) {
Node lru = tail.prev; // the node just before the tail is the least recently used
unlink(lru);
map.remove(lru.key);
}
node = new Node(key, value);
map.put(key, node);
addToFront(node);
}
private void unlink(Node n) {
n.prev.next = n.next;
n.next.prev = n.prev;
}
private void addToFront(Node n) {
n.next = head.next;
n.prev = head;
head.next.prev = n;
head.next = n;
}
String order() { // most recent first
StringBuilder sb = new StringBuilder("[");
for (Node n = head.next; n != tail; n = n.next) {
if (sb.length() > 1) sb.append(", ");
sb.append(n.key);
}
return sb.append("]").toString();
}
public static void main(String[] args) {
LruCacheManual cache = new LruCacheManual(3);
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
cache.get("a");
cache.put("d", 4);
System.out.println("Most recent first: " + cache.order());
System.out.println("get(b) = " + cache.get("b"));
System.out.println("get(a) = " + cache.get("a"));
}
}
Output
Core Logic
Interviewers often ask for the cache without LinkedHashMap: a HashMap finds nodes in O(1), and a doubly linked list keeps them ordered by recency.
- 1Each
Nodeholds a key, a value and links to its neighbours;headandtailare sentinel nodes that remove null checks. - 2
getlooks the node up in the map, unlinks it and re-adds it right afterhead, marking it most recent. - 3
putupdates an existing node the same way, or — if the cache is full — removestail.prev, the least recently used node, before inserting. - 4
order()walks fromheadtotail, printing most recent first.
[d, a, c], and get("b") returns null because b was evicted.Key Point: The node must store its key as well as its value — when the tail node is evicted, the key is what's needed to remove it from the map.
Why: Every operation is a map lookup plus a fixed number of pointer updates.
Key Concepts
Interview Questions
Why is a doubly linked list needed instead of a singly linked one?
Removing a node from the middle needs access to its previous node. With a doubly linked list, that's O(1).
How would you make the LRU cache thread-safe?
Wrap its methods in synchronized or a lock, because even get changes the order in an access-ordered map.