这题AC的前提是get()和set()操作都得是O(1)，不过题中没有说明这点（所以我一开始Naive的用了两个数组分别表示Key 和Value，想都不用想每个操作定然会达到N）。后来是看了discuss后，决定采用HashMap+LinkedList，但是结果还是一直TLE，其实TLE是预料中的，因为LinkedList的底层虽然是双向链表，我们在remove其中一个元素时，需要先通过遍历链表才能找到这个元素，这个遍历就使得时间复杂度为O(n)。

最后在网上看到这样一个 ，我觉得里头一个数据结构画的特别形象，如下：

有了这个提示，写自己的代码并不难，但是双向链表的操作特别需要细心和耐心，很容易出错。下面是我的Java代码，已AC。

1 package leetcode;  2   3 import java.util.HashMap;  4 /**  5  * 自己建一个双向链表  6  * 表头表示最新使用过得、表尾表示latest least used  7  * 采用LinkedList
     
      没法在O(1)的时间内删除某个节点(我感觉是这样)  8  * @author Echo  9  * 10  */ 11 class DNode 12 { 13     int key; 14     int value; 15     DNode next; 16     DNode pre; 17     public DNode() 18     { 19     } 20     public DNode(int k, int v) 21     { 22         key = k; 23         value = v; 24     } 25 } 26 /** 27  * 下面是LRU这个类 28  * @author Echo 29  * 30  */ 31 public class LRUCache1 { 32     //key和DNode是很明显的对应关系，并且hash表中的value之间又是双向链表 33     HashMap
      
        KV ; //这个数据结构可以参考 http://www.programcreek.com/2013/03/leetcode-lru-cache-java/ 34     DNode head ; //表示双向链表的表头 35     DNode tail ; //表示双向链表的表尾 36     int cap; //cache的容量 37     int sz = 0; //cache的实际size 38     public LRUCache1(int capacity) 39     { 40         cap = capacity; 41         KV = new HashMap
       
        (cap);  42     } 43     /** 44      *  Get the value (will always be positive) of the key if the key exists in the cache, 45      *  otherwise return -1. 46      * @param key 47      * @return 48      */ 49     public int get(int key) 50     { 51         if(KV.containsKey(key)) 52         { 53             DNode u = KV.get(key);     54             remove(u); 55             addHead(u); 56             KV.put(key, u); 57             return u.value; 58         } 59         return -1; 60     } 61     /** 62      * Set or insert the value if the key is not already present.  63      * When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. 64      * @param key 65      * @param value 66      */ 67     public void set(int key, int value) 68     { 69         DNode u = new DNode(key,value); 70         if(get(key) == -1) 71         {     72             if(sz