Every read or write operation marks an entry as recently used. The primary requirement is that both get() and put() operations execute in O(1) time.
Requirements
A correct LRU cache implementation should meet the following requirements:1. The cache stores key-value pairs.
2. When a key is accessed using get(), it becomes the most recently used item.
3. When a key is inserted or updated using put(), it also becomes the most recently used item.
4. If the cache is full, inserting a new item removes the least recently used item.
5. Both get() and put() operations execute in O(1) time.
Design
A HashMap provides O(1) lookup by key.A Doubly Linked List maintains the usage order. Each node stores references to both its previous and next nodes, allowing nodes to be removed or inserted in O(1) time.
The head always represents the most recently used node. The tail always represents the least recently used node.
Every cache entry is represented by a node stored both in the HashMap and in the Doubly Linked List.
Operations
Both operations take O(1) time because the HashMap provides constant-time lookup, while the doubly linked list allows constant-time insertion, removal, and movement of nodes without traversing the list.get(key)
The key is searched in the HashMap. If it is not found, return null. If found, move the node to the front of the linked list and return its value.put(key, value)
If the key already exists, update its value, move it to the front, and finish. If the key does not exist and the cache has free space, create a new node, insert it at the front, and add it to the map.If the cache is full, remove the node at the tail, delete it from the map, create a new node, insert it at the front, and add it to the map.
Java Implementation
Whenever get() or put() accesses an existing entry, it is moved to the front of the list.When the cache reaches its capacity, the last node in the list is removed and its corresponding entry is deleted from the HashMap. This ensures that all cache operations execute in O(1) time.
import java.util.HashMap;
import java.util.Map;
public class LRUCache<K, V> {
private final int capacity;
private final Map<K, Node<K, V>> cache = new HashMap<>();
private final Node<K, V> head;
private final Node<K, V> tail;
public LRUCache(int capacity) {
this.capacity = capacity;
head = new Node<>(null, null);
tail = new Node<>(null, null);
head.next = tail;
tail.prev = head;
}
public V get(K key) {
Node<K, V> node = cache.get(key);
if (node == null) {
return null;
}
moveToFront(node);
return node.value;
}
public void put(K key, V value) {
Node<K, V> node = cache.get(key);
if (node != null) {
node.value = value;
moveToFront(node);
return;
}
if (cache.size() == capacity) {
Node<K, V> lru = removeLast();
cache.remove(lru.key);
}
Node<K, V> newNode = new Node<>(key, value);
addFirst(newNode);
cache.put(key, newNode);
}
private void moveToFront(Node<K, V> node) {
remove(node);
addFirst(node);
}
private void addFirst(Node<K, V> node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
private void remove(Node<K, V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private Node<K, V> removeLast() {
Node<K, V> node = tail.prev;
remove(node);
return node;
}
private static class Node<K, V> {
K key;
V value;
Node<K, V> prev;
Node<K, V> next;
Node(K key, V value) {
this.key = key;
this.value = value;
}
}
}
Example
This example demonstrates how the least recently used entry is automatically evicted when the cache reaches its maximum capacity.public class Main {
public static void main(String[] args) {
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "A");
cache.put(2, "B");
cache.put(3, "C");
cache.get(1);
cache.put(4, "D");
System.out.println(cache.get(2)); // null
System.out.println(cache.get(1)); // A
System.out.println(cache.get(3)); // C
System.out.println(cache.get(4)); // D
}
}
Execution
Initially (Empty Cache):Head → Tail
After put(1), put(2), and put(3):
Head → 3 → 2 → 1 → Tail
After get(1):
Head → 1 → 3 → 2 → Tail
After put(4):
Least Recently Used (key 2) is evicted.
Head → 4 → 1 → 3 → Tail
Complexity
get() performs a HashMap lookup and updates the linked list in constant time. put() performs insertion, update, eviction, and linked list operations in constant time.Time Complexity
get() → O(1)
put() → O(1)
Space Complexity
O(capacity)
LRU Cache Using LinkedHashMap
We can also use LinkedHashMap, which already maintains insertion or access order and can implement an LRU cache by overriding removeEldestEntry().import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true); // accessOrder = true
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
public static void main(String[] args) {
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "A");
cache.put(2, "B");
cache.put(3, "C");
cache.get(1); // 1 becomes most recently used
cache.put(4, "D"); // Removes key 2
System.out.println(cache); // {3=C, 1=A, 4=D}
}
}
Making the LRU Cache Thread-Safe
The simplest approach is to protect all cache operations with a ReentrantLock.import java.util.concurrent.locks.ReentrantLock;
public class LRUCache<K, V> {
private final ReentrantLock lock = new ReentrantLock();
// Existing fields...
public V get(K key) {
lock.lock();
try {
Node<K, V> node = cache.get(key);
if (node == null) {
return null;
}
moveToFront(node);
return node.value;
} finally {
lock.unlock();
}
}
public void put(K key, V value) {
lock.lock();
try {
Node<K, V> node = cache.get(key);
if (node != null) {
node.value = value;
moveToFront(node);
return;
}
if (cache.size() == capacity) {
Node<K, V> lru = removeLast();
cache.remove(lru.key);
}
Node<K, V> newNode = new Node<>(key, value);
addFirst(newNode);
cache.put(key, newNode);
} finally {
lock.unlock();
}
}
// Other methods remain unchanged...
}
public synchronized V get(K key) {
// Existing implementation
}
public synchronized void put(K key, V value) {
// Existing implementation
}
tryLock(), timed lock acquisition, and interruptible locking.
