LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。现在要设计一种数据结构有如下几种性质：
1. 每个节点为一对key,value的形式，可通过get <key>查找，通过put <key, value> 插入
2. 最大存储节点数为n
3. put操作时，如果已经存储了n个节点，则要淘汰最近最少使用的那个节点
可能会有很多种解决方案，例如：
一、用一个双向链表来存储所有节点，get时，遍历整个链表，找到对应的节点，并且把该节点挪动到链表的第一个位置，因此，链接中越靠前的位置总是距离最后一次访问时间越短的节点，越靠后的位置总是距离最后一次访问时间约久的节点。所以put时，如果已达到最大存储节点数时，直接删除链表最后一个节点再插入即可。总结，优点：实现简单，put操作的时间复杂度为O(1) 缺点：get操作时间复杂度为O(n)，不够优秀。
二、我们都知道哈希表这种数据结构查询的时间性能很好，但是在这里如果只用一个哈希表，虽然查询和插入操作都能优化到O(1)，但是在删除，也就是查找最近最少使用的节点时，却不得不遍历整个哈希表。我们来做进一步优化，前面第一种方案删除和插入操作都是O(1)的，但是查询操作是O(n)，如果能把这两种方案结合一下的话，三种操作不就都是O(1)时间复杂度了。怎么结合呢？
哈希表的value存储节点的指针，同时把所有的value连接成一个双向链表，查询操作时，通过哈希表直接找到这个节点的指针，同时，可以在O(1)时间将这个节点移动到链表头部，删除操作时，直接删除链表尾部那个节点，同时将这个节点从哈希表中删除。
C++实现（这里为了简化操作，直接用了STL的map代替哈希表）
class LRUCache { public: struct Node { int key, value; Node *next, *pre; }; map<int, Node*> cache; Node *head, *rear; int size; LRUCache(int capacity) { size = capacity; head = new Node(); rear = new Node(); head->pre = NULL; head->next = rear; rear->next = NULL; rear->pre = head; } int get(int key) { if(cache.find(key) == cache.end()) return -1; Node *tmp = cache[key]; tmp->pre->next = tmp->next; tmp->next->pre = tmp->pre; head->next->pre = tmp; tmp->next = head->next; tmp->pre = head; head->next = tmp; return tmp->value; } void lru_delete() { if(cache.size() == 0) return; Node* tmp = rear->pre; rear->pre = tmp->pre; tmp->pre->next = rear; cache.erase(tmp->key); delete tmp; } void put(int key, int value) { // if the key exist, then just update the value if(cache.find(key) != cache.end()) { cache[key]->value = value; this->get(key); return; } if(cache.size() >= this->size) this->lru_delete(); Node *tmp = new Node; tmp->key = key; tmp->value = value; tmp->pre = this->head; tmp->next = this->head->next; if(head->next != NULL) head->next->pre = tmp; this->head->next = tmp; cache.insert(pair<int, Node*>(key, tmp)); } };