LRU (Least Recently Used) Cache Implementation in Java
import java.util.HashMap;
import java.util.Map;
class Node{
int key;
int value;
Node pre;
Node next;
public Node(int key , int value) {
this.key = key;
this.value = value;
}
}
class LRUImpl {
Node head , tail;
int CAPACITY, count;
Map<Integer, Node> map ;
public LRUImpl(int capacity) {
this.CAPACITY = capacity;
this.count = 0 ;
this.map = new HashMap<Integer, Node>();
head = new Node(0,0);
tail = new Node(0,0);
head.next = tail;
head.pre = null;
tail.next = null;
tail.pre = head;
}
public void deleteNode(Node node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
public void addNodeToHead(Node node) {
node.next = head.next;
node.pre = head;
head.next.pre = node;
head.next = node;
}
public void printValueFromCache(int key) {
if(map.containsKey(key)) {
Node node = map.get(key);
System.out.println("The value is "+ node.value);
deleteNode(node);
addNodeToHead(node);
}
else {
System.out.println("Invalid Key or Key does not exists");
}
}
public void setValueToCache(int key, int value) {
if(map.containsKey(key)) {
Node node = map.get(key);
deleteNode(node);
addNodeToHead(node);
}
else {
Node node = new Node(key, value);
map.put(key, node);
if(count < this.CAPACITY) {
count++;
addNodeToHead(node);
}
else {
Node nodeRemove = map.get(tail.pre.key);
map.remove(tail.pre.key);
deleteNode(nodeRemove);
addNodeToHead(node);
}
}
}
}
public class LRUCache{
public static void main(String args[]) {
LRUImpl lru = new LRUImpl(3);
lru.setValueToCache(1, 1);
lru.setValueToCache(2, 2);
lru.setValueToCache(3, 3);
lru.printValueFromCache(1);
lru.printValueFromCache(3);
lru.setValueToCache(4, 4);
lru.printValueFromCache(2); // does not exists
}
}
