LRU Cache Implementation
1 min readJul 14, 2021
class LRUCache {
private Map<Integer, Node> map;
final Node head = new Node();
final Node tail = new Node();
private int capacity;public LRUCache(int capacity) {
this.map = new HashMap<>(capacity);
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
int result = -1;
Node node = map.get(key);
if(node != null) {
result=node.value;
remove(node);
add(node);
}
return result;
}
public void put(int key, int value) {
Node node = map.get(key);
if(node != null) {
remove(node);
node.value = value;
add(node);
}
else
{
if(map.size() == capacity) {
map.remove(tail.prev.key);
remove(tail.prev);
}
node = new Node();
node.key = key;
node.value = value;
map.put(key, node);
add(node);
}
}
//add the first node to Doubly Linked List
public void add(Node node){
Node head_next = head.next;
head.next = node;
node.next = head_next;
node.prev = head;
head_next.prev = node;
}
//remove the node of Doubly LinkedList
public void remove(Node node){
Node next_node = node.next;
Node prev_node = node.prev;
next_node.prev = prev_node;
prev_node.next = next_node;
}
class Node {
int key;
int value;
Node next;
Node prev;
}
}