LRUcache.java

/*************NODE CLASS*********************/
public class ListNode {
	int key;
	int value;
	ListNode next;
	ListNode prev;
	
	public ListNode(){
		
	}
	
	public ListNode(int key, int value){
		this.key = key;
		this.value = value;
	}
}
/*******************************************/
class LRUCache {
	
	int capacity;
	int size;
	
	ListNode head;//Dummy head
	ListNode tail;//Dummy tail
	HashMap<Integer, ListNode> keyToNode;
	
	public LRUCache(int capacity){
		this.capacity = capacity;
		this.keyToNode = new HashMap<>();
		//connect head and tail together
		this.head = new ListNode();
		this.tail = new ListNode();
		this.head.next = tail;
		this.tail.prev = head;
	}
	
	public void put(int key, int value){
		if(this.keyToNode.get(key) == null){//our cache does not hold key
			ListNode newNode = new ListNode(key, value);//create node to append to our cache
			this.keyToNode.put(key, newNode);//add entry in hashmap to link the key and node recently created
			//add the new node to front
			this.addToFront(newNode);
			this.size++;
			//LRU EXIT POLICY CHECK
			if(this.size > this.capacity) this.removeLRUEntry();
		}else{//our cache already holds the key
			ListNode keyHolderNode = this.keyToNode.get(key);//get node holding the key
			keyHolderNode.value = value;//change value to new value
			//move node to front
			this.moveToFront(keyHolderNode);
		}
	}
	
	public int get(int key){
		ListNode keyHolderNode = this.keyToNode.get(key);
		if(keyHolderNode == null){//key did not exist in cache
			return -1;
		}else{//key exists in cache
			//move node to front of list
			this.moveToFront(keyHolderNode);
			return keyHolderNode.value;
		}
	}
	
	//AUXILIARY METHODS
	private void removeLRUEntry() {
	   ListNode lastNode = popTail();
	   this.keyToNode.remove(lastNode.key);
	   this.size--;
	  }
	
    private void addToFront(ListNode node) {
	    node.prev = head;
	    node.next = head.next;
	    head.next.prev = node;
	    head.next = node;
	 }
    
    private void moveToFront(ListNode node){
    	this.removeFromList(node);
    	this.addToFront(node);
    }
    
     private void removeFromList(ListNode node) {
        ListNode savedPrev = node.prev;
        ListNode savedNext = node.next;

        savedPrev.next = savedNext;
        savedNext.prev = savedPrev;
      }
     
      private ListNode popTail(){
    	  ListNode tailNode = this.tail.prev;
    	  tailNode.prev.next = tailNode.next;
    	  tailNode.next.prev = tailNode.prev;
    	  return tailNode;
      }
}