LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(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.

The cache is initialised with a positive capacity.




public class LRUCacheNew {

static class ListNode {
int key;
int value;
ListNode prev;
ListNode next;
@Override
public String toString() {
return "ListNode [key=" + key + ", value=" + value + "]";
}
}

Map<Integer, ListNode> hashmap = new HashMap<Integer, ListNode>();
ListNode head;
ListNode tail;

int totalItemsInCache;
int maxCapacity;

public LRUCacheNew(int maxCapacity) {
totalItemsInCache = 0;
this.maxCapacity = maxCapacity;
head = new ListNode();
tail = new ListNode();
head.next = tail;
tail.prev = head;
}

public int get(int key) {
ListNode node = hashmap.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}

public void put(int key, int value) {
ListNode node = hashmap.get(key);
if (node == null) {
ListNode newNode = new ListNode();
newNode.key = key;
newNode.value = value;
hashmap.put(key, newNode);
addToFront(newNode);
totalItemsInCache++;
if (totalItemsInCache > maxCapacity) {
removeLRUEntry();
}
} else {
node.value = value; 
moveToHead(node);
}
}

private void removeLRUEntry() {
ListNode tail = popTail();
hashmap.remove(tail.key);
totalItemsInCache--;
}

private ListNode popTail() {
ListNode tailItem = tail.prev;
removeFromList(tailItem);
return tailItem;
}

private void addToFront(ListNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}

private void removeFromList(ListNode node) {
ListNode savedPrev = node.prev;
ListNode savedNext = node.next;

savedPrev.next = savedNext;
savedNext.prev = savedPrev;
}

private void moveToHead(ListNode node) {
removeFromList(node);
addToFront(node);
}

private void printData(){
System.out.println(hashmap);
}

public static void main(String[] args) {
LRUCacheNew cache = new LRUCacheNew(5);
cache.put(2, 4);
cache.put(1, 4);
cache.put(3, 4);
cache.put(5, 4);
cache.put(6, 4);
cache.put(7, 4);
cache.put(9, 4);
cache.put(0, 4);

System.out.println(cache.get(2)); //-1
System.out.println(cache.get(9)); //4
cache.printData(); 

}
}

Output : 

-1

4

{0=ListNode [key=0, value=4], 5=ListNode [key=5, value=4], 6=ListNode [key=6, value=4], 7=ListNode [key=7, value=4], 9=ListNode [key=9, value=4]}