LRUCache.java

import java.util.*;

public class LRUCache {

    //double linked list class
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
    }

    //Adding a new node to the DLL
    private void addNode(DLinkedNode node) {

        //Since the new node is the most recently used node,
        //we add it after the pseudo head.  
        //Pseudo Head and Tail of the DLL will remain the same.
        node.prev = head;
        node.next = head.next;

        //The former node after the pseudo head, now points to
        //the new node as its previous node.
        head.next.prev = node;
        //The next node after the pseudo head is the added node.
        head.next = node;
    }

    //Removing a node from the DLL
    private void removeNode(DLinkedNode node){

        //The node before and after the deleted node
        DLinkedNode prev = node.prev;
        DLinkedNode next = node.next;

        //The previous node points to the node after
        //the removed node.
        prev.next = next;
        //The next node points to the node before
        //the removed node.
        next.prev = prev;
    }

    //Moving a node to the head of the DLL
    //Used to update the MRU and LRU nodes
    private void moveToHead(DLinkedNode node){

        //First removes the node, then adds it
        //to the DLL again.
        removeNode(node);
        addNode(node);
    }

    //Pops out the node before the pseudo tail  
    //and returns the removed node.
    private DLinkedNode popTail() {

        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }

    //The map of integers to the DLL (Cache)
    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, 
                                                          DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    //Initializing the cache
    public LRUCache(int capacity) {
        //current size of the link list
        this.size = 0;
        this.capacity = capacity;

        head = new DLinkedNode();
        tail = new DLinkedNode();

        head.next = tail;
        tail.prev = head;
    }

    //Get method
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) return -1;

        //Moves the node to the start of the DLL as MRU
        moveToHead(node);

        return node.value;
    }

    //Put method
    public void put(int key, int value) {
        //Checks if the given node already exists
        DLinkedNode node = cache.get(key);

        //Adding a new node to the cache
        if(node == null) {
            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;

            cache.put(key, newNode);
            addNode(newNode);

            ++size;

            //If the cache capacity is full, pop the tail (LRU)
            if(size > capacity) {

                DLinkedNode tail = popTail();
                cache.remove(tail.key);
                --size;
            }
        }
        //Else, Updates the value and the position
        //of the previously existing node
        else {

            node.value = value;
            moveToHead(node);
        }
    }
}