import java.util.HashMap;
public class LRUCache
{
int size;
Node least;
Node recent;
HashMap<Integer,Integer> hm;
HashMap<Integer,Node> nodeMap;
LRUCache(int capacity)
{
// Write your code here
size = capacity;
least = null;
recent = null;
hm =new HashMap<>();
nodeMap = new HashMap<>();
}
public int get(int key)
{
// Write your code here
if(hm.containsKey(key))
{
updateTheCache(key);
return hm.get(key);
}
return -1;
}
public void put(int key, int value)
{
// Write your code here
if(!hm.containsKey(key) && hm.size() >= size)
{
hm.remove(least.key);
nodeMap.remove(least.key);
hm.put(key, value);
Node n = new Node(key);
nodeMap.put(key, n);
if(least == recent)// if cache capacity is 1
{
least = recent = n;
}
else
{
least = least.next;
least.prev = null;
recent.next = n;
n.prev = recent;
recent = n;
}
}
else if(hm.containsKey(key))
{
updateTheCache(key);
hm.put(key, value);
}
else
{
hm.put(key, value);
Node n = new Node(key);
nodeMap.put(key, n);
if(least == null)
{
least = recent = n;
}
else
{
recent.next = n;
n.prev = recent;
recent = n;
}
}
}
private void updateTheCache(int key)
{
if(least == recent)// the capacity of cache is 1 or in cache their is only one element as of now
{return; }
else
{
Node temp = nodeMap.get(key);
if(least != temp && recent != temp)
{
temp.prev.next = temp.next;
temp.next.prev = temp.prev;
recent.next = temp;
temp.prev = recent;
recent = temp;
}
else if(least == temp)
{
least=least.next;
least.prev = null;
recent.next = temp;
temp.prev = recent;
recent = temp;
}
}
}
}
class Node
{
Node prev;
Node next;
int key;
public Node(int k)
{
key = k;
}
}