LeetCode——LRU Cache

design and implement a data structure for least recently used (lru) cache. it should support the following operations: <code>get</code> and <code>set</code>.

<code>get(key)</code> - get the value

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

<code>set(key, value)</code> - 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.

思路：

最常用的数据结构实现方式是map和double-linked list，map只是为了实现键值key-value对应，这样就避免了每次寻找特定值都要在双线链表里面顺序查找，服务器是没办法负担这种低效率的查找方法的。

set流程讲解：

在map中查找key，如果找到，说明这个节点已经存在，那么将该节点的的位置排在链表头部；

如果没找到，要进行第二个判断“是否已经达到了max_size”，如果已经达到了，将原来链表最后一个节点删除，然后将对应的map中的key-value删除，然后再加入新节点，并在map中加入对应的key-value，如果没有达到max-size，那么分配新地址给这个节点，同时加入到list和对应的map中。

get比较简单

代码：

附：splice是移动链表元素的方法

splice实例代码：