LRU Cache Implementaion

• LRU Cache (Java) Design and implement a data structure for Least Recently Used (LRU) cache. 
• The LRU caching scheme is to remove the least recently used frame when the cache is full and a new page is referenced which is not there in cache.
• Properties are,
• Fixed Size: Cache needs to have some bounds to limit memory usages.
• Fast Access: Cache Insert and lookup operation should be fast , preferably O(1) time.
• Replacement of Entry in case , Memory Limit is reached: A cache should have efficient algorithm to evict the entry when memory is full.
• When we think about O(1) lookup , obvious data structure comes in our mind is HashMap. HashMap provide O(1) insertion and lookup.
• but HashMap does not has mechanism of tracking which entry has been queried recently and which not.To track this we require another data-structure which provide fast insertion ,deletion and updation , in case of LRU we use Doubly Linkedlist . 
• Reason for choosing doubly LinkList is O(1) deletion , updation and insertion if we have the address of Node on which this operation has to perform.
•  HashMap will hold the keys and address of the Nodes of Doubly LinkedList . And Doubly LinkedList will hold the values of keys.
• As We need to keep track of Recently used entries, We will use a clever approach. We will remove element from bottom and add element on start of LinkedList and whenever any entry is accessed , it will be moved to top. so that recently used entries will be on Top and Least used will be on Bottom.

• package com.iwq.LRU.withhashmap; import java.util.HashMap; import java.util.Map; public class LRUcache { Map hashmap = new HashMap(); Entry start; Entry end; int LRU_SIZE = 4; public void put(int key, int value) { // if key already exists update value and move to top if (hashmap.containsKey(key)) // Key Already Exist, just update the value and move it to top { Entry entry = hashmap.get(key); entry.value = value; removeNode(entry); addAtTop(entry); } else { Entry newnode = new Entry(); newnode.left = null; newnode.right = null; newnode.value = value; newnode.key = key; if (hashmap.size() > LRU_SIZE) // We have reached maxium size so need to make room for new element. { hashmap.remove(end.key); removeNode(end); addAtTop(newnode); } else { addAtTop(newnode); } hashmap.put(key, newnode); } } public void removeNode(Entry node) { // remove from left and right nodes if (node.left != null) { node.left.right = node.right; } else { start = node.right; } if (node.right != null) { node.right.left = node.left; } else { end = node.left; } } public void addAtTop(Entry node) { // node.right = start; node.left = null; if (start != null) start.left = node; start = node; if (end == null) end = start; } }