Efficient LRU Cache in Java
Updated on Feb 17 2018 at the 04th hour
DISCLAIMER: Expressed views on this blog are my own.
Fun fun stuff to do in lintcode. I mean we can always incur a linear traversal using a LinkedList if one wanted a simple way to do LRU, but why not challenge myself.
public class LRUCache {
public class LRUNode {
Integer key;
Integer data;
LRUNode prev;
LRUNode next;
public LRUNode(int key, int data) {
this.key = key;
this.data = data;
}
}
LRUNode head;
LRUNode tail;
Map nodeMap = new HashMap();
int maxCap;
/*
* @param capacity: An integer
*/public LRUCache(int capacity) {
// do intialization if necessary
this.maxCap = capacity;
}
/*
* @param key: An integer
* @return: An integer
*/
public int get(int key) {
// write your code here
LRUNode node = nodeMap.get(key);
if(node != null) {
this.remove(node);
this.push(node);
return node.data;
}
return -1;
}
/*
* @param key: An integer
* @param value: An integer
* @return: nothing
*/
public void set(int key, int value) {
// write your code here
if(nodeMap.containsKey(key)) {
LRUNode oldNode = this.nodeMap.get(key);
this.remove(oldNode);
}
LRUNode node = new LRUNode(key, value);
this.push(node);
if(nodeMap.size() > this.maxCap) {
this.removeOld();
}
}
private void push(LRUNode newHead) {
if(this.head != null) {
newHead.prev = null;
newHead.next = this.head;
this.head.prev = newHead;
}
if(this.tail == null) {
this.tail = newHead;
}
this.head = newHead;
this.nodeMap.put(newHead.key, newHead);
}
private void removeOld() {
if(this.tail == null) {
return;
}
this.remove(this.tail);
}
private void remove(LRUNode node) {
if(node.prev != null) {
node.prev.next = node.next;
}
if(node.next != null) {
node.next.prev = node.prev;
}
if(node.equals(this.head)) {
this.head = node.next;
}
if(node.equals(this.tail)) {
this.tail = node.prev;
}
node.next = null;
node.prev = null;
this.nodeMap.remove(node.key);
}
}
