You are viewing...

Efficient LRU Cache in Java

Updated on February 17, 2018 at the 04th hour
Posted under:

DISCLAIMER: All views are considered my own and you should not draw any conclusions on associates.

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);
}
}
You just read "Efficient LRU Cache in Java". Please share if you liked it!
You can read more recent posts here.