Sequnece Diagram
import java.util.*;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
// Node for doubly linked list
class Node {
int key;
int value;
Node prev;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
// LRU Cache implementation
class LRUCache {
private final int capacity;
private final Map<Integer, Node> cache;
private final Node head, tail;
private final Lock lock;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.lock = new ReentrantLock();
// Dummy head and tail nodes
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
// Get value from cache
public int get(int key) {
lock.lock();
try {
if (!cache.containsKey(key)) {
return -1;
}
Node node = cache.get(key);
moveToHead(node);
return node.value;
} finally {
lock.unlock();
}
}
// Put key-value pair in cache
public void put(int key, int value) {
lock.lock();
try {
if (cache.containsKey(key)) {
Node node = cache.get(key);
node.value = value;
moveToHead(node);
} else {
Node newNode = new Node(key, value);
cache.put(key, newNode);
addNode(newNode);
if (cache.size() > capacity) {
Node tailNode = popTail();
cache.remove(tailNode.key);
}
}
} finally {
lock.unlock();
}
}
// Add a new node right after the head
private void addNode(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
// Remove a node from the doubly linked list
private void removeNode(Node node) {
Node prev = node.prev;
Node next = node.next;
prev.next = next;
next.prev = prev;
}
// Move a node to the head (most recently used)
private void moveToHead(Node node) {
removeNode(node);
addNode(node);
}
// Pop the least recently used node (from the tail)
private Node popTail() {
Node tailNode = tail.prev;
removeNode(tailNode);
return tailNode;
}
}
// Example usage
public class LRUCacheExample {
public static void main(String[] args) {
LRUCache cache = new LRUCache(3);
// Put values
cache.put(1, 10);
cache.put(2, 20);
cache.put(3, 30);
System.out.println("Get key 2: " + cache.get(2)); // Output: 20
// Add a new value and evict the least recently used
cache.put(4, 40);
System.out.println("Get key 1: " + cache.get(1)); // Output: -1 (evicted)
// Access key 3 and add another value
System.out.println("Get key 3: " + cache.get(3)); // Output: 30
cache.put(5, 50);
System.out.println("Get key 2: " + cache.get(2)); // Output: -1 (evicted)
}
}
Sample Input and Output:
Input:
Output:
Get key 2: 20Get key 1: -1Get key 3: 30Get key 5: 50Node class represents an entry in the cache with pointers for the doubly linked list.LRUCache class maintains the cache using a HashMap for quick lookups and a doubly linked list to track usage order.put() method handles insertion and eviction of least recently used items.get() method retrieves the value and updates the usage order.ReentrantLock.