For LRU cache, it's like a fifo queue but reassign the existing value to the first if we use the value(get). Based on fifo, one may think of using a pair to record the key and value and put them into a queue, however, it takes much time to search/delete for a value in a queue O(N). Alternatively, we can use doublyLinkedList to maintain the relationships between pairs(nodes) and easily remove/change any nodes. Then we use a hashmap to keep track of <key, node>pair to help get the node value in O(1).
For get method, we need to consider:
1. key contains in hashmap: bring to the front, return value;
2.key not contains in hashmap: return -1;
For put method, we need to consider:
1. if hashmap has the key : change the value through hashmap, remove the old node in DLL, add the new node in the front;
2. else if capacity > 0: capacity--, add to hashmap, add the new node to the front
3. else: delete the tail node, delete the pair in hashmap, add the new node to front, add to hashmap.
Code:
class LRUCache {
public DLinkedListNode head;
public DLinkedListNode tail;
int capacity;
HashMap<Integer, DLinkedListNode> hm;
class DLinkedListNode {
int key;
int value;
DLinkedListNode prev;
DLinkedListNode next;
}
public LRUCache(int capacity) {
head = new DLinkedListNode();
tail = new DLinkedListNode();
head.next = tail;
tail.prev = head;
hm = new HashMap<>();
this.capacity = capacity;
}
public int get(int key) {
if(hm.containsKey(key)){
DLinkedListNode c = hm.get(key);
movetoFront(c);
return c.value;
}
return -1;
}
public void movetoFront(DLinkedListNode cur){
remove(cur);
addFront(cur);
}
public void remove(DLinkedListNode cur){
DLinkedListNode next = cur.next;
DLinkedListNode prev = cur.prev;
prev.next = next;
next.prev = prev;
}
public void addFront(DLinkedListNode cur){
DLinkedListNode next = head.next;
head.next = cur;
cur.next = next;
next.prev = cur;
cur.prev = head;
}
public void removeLast(){
DLinkedListNode t = tail.prev;
hm.remove(t.key);
DLinkedListNode tPrev = t.prev;
tail.prev = tPrev;
tPrev.next = tail;
}
public void put(int key, int value) {
if(hm.containsKey(key)){
DLinkedListNode newNode = new DLinkedListNode();
newNode.key = key;
newNode.value = value;
remove(hm.get(key));
addFront(newNode);
hm.replace(key, newNode);
return;
}
if(capacity > 0){
DLinkedListNode newNode = new DLinkedListNode();
newNode.key = key;
newNode.value = value;
hm.put(key, newNode);
addFront(newNode);
capacity--;
}else{
DLinkedListNode newNode = new DLinkedListNode();
newNode.key = key;
newNode.value = value;
removeLast();
addFront(newNode);
hm.put(key, newNode);
}
}
}
