1 package leetcode; 2  3 import java.util.HashMap; 4 import java.util.Map; 5  6 class Node{ 7     int key; 8     int value; 9     Node pre;10     Node next;11     Node(int key,int value){12         this.key=key;13         this.value=http://www.mamicode.com/value;14         this.pre=null;15         this.next=null;16     }17 }18 class CacheList{19     private Node head;20     private Node tail;21     CacheList(int capacity){22         head = new Node(0,0);23         tail = new Node(0,0);24         head.next=tail;25         tail.pre=head;26     }27     public void insertFirst(Node n){28         n.next=head.next;29         head.next.pre=n;30         head.next=n;31         n.pre=head;32         33     }34     public Node removeLast(){35         Node re = tail.pre;36         tail.pre.pre.next=tail;37         tail.pre=tail.pre.pre;38         return re;39     }40     public void shiftToFirst(Node n){41         n.pre.next=n.next;42         n.next.pre=n.pre;43         insertFirst(n);44     }45 }46 47 public class LRUCache {48      Map<Integer,Node> map;49      CacheList cacheList;50      int capacity;51     public LRUCache(int capacity) {52         map = new HashMap<Integer,Node>();53         cacheList= new CacheList(capacity);54         this.capacity=capacity;55     }56     57     public int get(int key) {58         if(map.get(key)==null)59         return -1;60         else {61             Node n= (Node) map.get(key);62             cacheList.shiftToFirst(n);63             return n.value;64         }65     }66   67     68     public void set(int key, int value) {69         if(map.containsKey(key)){70              Node come= (Node) map.get(key);71              come.value=http://www.mamicode.com/value;72              cacheList.shiftToFirst(come);;73         }else{74             if(map.size()==capacity){75                 Node old=cacheList.removeLast();76                 map.remove(old.key);77                          78             }79             Node nn=new Node(key,value);80             cacheList.insertFirst(nn);81             map.put(key, nn);82         }83         84 85     }86     public static void main(String[] args){87         LRUCache l = new LRUCache(1);88         l.set(2, 1);89         System.out.println(l.get(2));90         l.set(3, 2);91         System.out.println(l.get(2));92         System.out.println(l.get(3));93 94     }95 }