get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Idea: Use a bi-directional linked list to store the inserted data. At the same time use a hashmap<key, node> to achieve O(1) access. Whenever a key is visited or modified, move it out of the bi-directional linked list, then insert it to the tail of the list. Whenever an insertion is required and the capacity is full, remove the node at the head.
Time: O(1) Space: O(n)
Code:
public class LRUCache {
class Node{
int key;
int val;
Node prev;
Node next;
public Node(int key,int val)
{
this.key=key;
this.val=val;
this.prev=null;
this.next=null;
}
}
public int capacity;
public HashMap<Integer,Node> keyToNode;
public Node head;
public Node tail;
public LRUCache(int capacity) {
this.capacity=capacity;
keyToNode=new HashMap<Integer,Node>();
head=new Node(-1,-1);
tail=new Node(-1,-1);
head.next=tail;
tail.prev=head;
}
public int get(int key) {
if(keyToNode.containsKey(key)==false)
return -1;
Node tmp=keyToNode.get(key);
tmp.prev.next=tmp.next;
tmp.next.prev=tmp.prev;
moveToTail(tmp);
return keyToNode.get(key).val;
}
public void set(int key, int value) {
if(get(key)!=-1)
{
keyToNode.get(key).val=value;
return;
}
if(keyToNode.size()==capacity)
{
keyToNode.remove(head.next.key);
head.next=head.next.next;
head.next.prev=head;
}
Node newNode=new Node(key,value);
keyToNode.put(key,newNode);
moveToTail(newNode);
}
public void moveToTail(Node cur)
{
cur.prev=tail.prev;
tail.prev=cur;
cur.prev.next=cur;
cur.next=tail;
}
}
