LRU Cache

 1 public class LRUCache {
 2     entry first,last;
 3     Map<Integer,entry> map;
 4     int curSize = 0;
 5     int cap;
 6     
 7     public LRUCache(int capacity) {
 8         this.cap = capacity;
 9         map = new HashMap<Integer,entry>();
10     }
11     
12     public int get(int key) {
13         if(map.get(key)!=null){
14             moveToHead(map.get(key));
15             return map.get(key).val;
16         }
17         return -1;
18     }
19     
20     public void set(int key, int value) {
21         entry e = map.get(key);
22         if(e==null){
23             if(curSize>=cap){
24                 map.remove(last.key);
25                 removeLast();
26             }
27             else{
28                 curSize++;
29             }
30             e = new entry(key,value);
31         }
32         if(curSize==1){
33             first = e;
34             last = e;
35         }
36         e.val=value;
37         moveToHead(e);
38         map.put(key,e);
39     }
40     public void moveToHead(entry node){
41         if(node==first) return;
42         if(node.pre!=null)
43             node.pre.next = node.next;
44         if(node.next!=null)
45             node.next.pre = node.pre;
46         if(node==last){
47             last = node.pre;
48         }
49         if(first!=null){
50             first.pre = node;
51             node.next = first;
52         }
53         first = node;
54         node.pre = null;
55     }
56     public void removeLast(){
57         if(last!=null){
58             if(last.pre!=null)
59                 last.pre.next=null;
60             else
61                 first = null;
62         }
63         last = last.pre;
64     }
65 }
66 class entry{
67     entry next,pre;
68     int key,val;
69     public entry(int key,int val){
70         this.key = key;
71         this.val = val;
72     }
73     public entry(){}
74 }