Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

 

LRU cache, 采用“如果满则淘汰最近未使用的项目“的策略，所以需要一个序列，每次插入的项目放入序列首，被查找的项目也移至序列首。如果超过数量上限则删除序列最后的项目。查找，插入操作都需要O(1)的时间复杂度，否则超时通不过。所以这个序列可以是链表，并且为了查找快捷，需要结合HashMap。由于涉及到转移项目操作，需要双向链表。

HashMap用于把查找键key和具体项目联系起来，这样就能直接获得项目，然后将其移至链表首位。

需要注意的是set操作中，如果set的key已经存在了，那就相当于一次查找操作加上修改其值和HashMap的操作。

代码如下：

1 class Node 2     { 3         int key; 4         int value; 5         Node next; 6         Node front; 7         Node(int k, int v) 8         { 9             key=k;10             value=v;11             next=null;12             front=null;13         }14     }15     16     private HashMap
     
       hs;17     private Node head;18     private Node tail;19     private int cap;20     public LRUCache(int capacity) {21         hs = new HashMap
      
       ();22         head = null;23         cap = capacity;24         tail = null;25     }26     27     public int get(int key) {28         Node re = hs.get(key);29         if(re==null)30             return -1;31         if(re.front==null)32             return re.value;33         re.front.next = re.next;34         if(re.next!=null)35             re.next.front = re.front;36         else37             tail = re.front;38         re.front = null;39         re.next = head;40         head.front = re;41         head = re;42         return re.value;43     }44     45     public void set(int key, int value) {46         Node temp = hs.get(key);47         if(temp!=null)48         {49             get(key);50             head.value = value;51             hs.put(key,head);52         }53         else54         {55             temp = new Node(key, value);56             temp.next = head;57             if(head!=null)58                 head.front = temp;59             head = temp;60             if(hs.size()==0)61                 tail = temp;62             hs.put(key, temp);63             if(hs.size()>cap)64             {65                 hs.remove(tail.key);66                 tail.front.next = null;67                 tail = tail.front;68             }69         }70     }