Implement Least Recently Used (LRU) cache

 If item is present in cache, it is moved to front of the list and location is returned.

 If it is not present , a new page mapping is done. If cache is not full, a new entry is added to front otherwise least recently used entry is removed and then a new entry to front is added.

import java.util.HashMap;
import java.util.Map;

public class LRUCacheSample1 {
    DoubleLinkList start = null;
    DoubleLinkList end = null;
    int capacity = 5;
    int count = 0;
    Map<Integer, DoubleLinkList> map = new HashMap<>();
    class DoubleLinkList{
        DoubleLinkList next;
        DoubleLinkList prev;
        int key;
        int val;
      
        public DoubleLinkList(int key,int val) {
            this.key = key;
            this.val = val;
        }
    }
  
    void get(int key) {
        if(map.containsKey(key)) {
            DoubleLinkList existNode = map.get(key);
            moveNodeToFront(existNode);
        }
    }
  
    void add(int key,int val) {
        if(map.containsKey(key)) {
            DoubleLinkList existNode = map.get(key);
            existNode.val = val;
            moveNodeToFront(existNode);
        }else {
            DoubleLinkList node = new DoubleLinkList(key, val);
            if(count<capacity) {
                count = count+1;
                addNodeAtFront(node);
            }else {
                DoubleLinkList lastNode = map.remove(end.key);
                removeNode(lastNode);
                addNodeAtFront(node);
            }
      
        }
    }
  
    void removeNode(DoubleLinkList node) {
         end = end.prev;
         if(null!=end) {
             end.next = null;
         }
        node = null;
    }
  
    void addNodeAtFront(DoubleLinkList node) {
        node.next = start;
        if(null!=start) {
            start.prev = node;
        }
            start = node;
         if(end==null) {
             end = node;
         }
         map.put(node.key, node);
        
    }
  
    void moveNodeToFront(DoubleLinkList node) {
        DoubleLinkList pr = node.prev;
        DoubleLinkList nex = node.next;
        if(null!=pr) {
            pr.next = nex;
        }else {
            start = node;
        }
        if(null!=nex) {
            nex.prev = pr;
        }else {
            end = pr;
        }
      
         addNodeAtFront(node);
    }
  
    void print() {
        DoubleLinkList node = start;
        while(null!=node) {
            System.out.println("key is"+node.key+"val is"+node.val);
            node = node.next;
        }
    }
  
  
    public static void main(String args[]) {
        LRUCacheSample1 obj = new LRUCacheSample1();
        obj.add(5, 10);
        obj.add(2, 4);
        obj.add(3, 6);
        obj.add(6, 12);
        obj.add(8, 16);
        
        obj.print();
        obj.get(3);
        System.out.println("*****************");
        System.out.println("after get 3");
        obj.print();
      
        obj.add(9, 18);
        System.out.println("*****************");
        System.out.println("after add 9");
        obj.print();
      
        obj.add(2, 13);
        System.out.println("*****************");
        System.out.println("after update 2");
        obj.print();
      
      
    }
  
}
output::
key is8val is16
key is6val is12
key is3val is6
key is2val is4
key is5val is10
*****************
after get 3
key is3val is6
key is8val is16
key is6val is12
key is2val is4
key is5val is10
*****************
after add 9
key is9val is18
key is3val is6
key is8val is16
key is6val is12
key is2val is4
*****************
after update 2
key is2val is13
key is9val is18
key is3val is6
key is8val is16
key is6val is12

Ref: http://androidsrc.net/lru-cache-java-implementation/