题解 | #设计LRU缓存结构#
设计LRU缓存结构
http://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84
信息结构， tuple (key, value) 是取用的数据对。
使用双向链表来作底层数据结构， 链表的容量为 capacity。 设置虚拟的头尾节点。 链表的顺序前后表示 tuple 读写的
使用Map作为各节点的地址寻址字典，Key 为 tuple的key， Value为节点Node。
为什么要用双向链表，便于删除操作。
- get的实现：
从map （meta) 中判断是否存在，如果不存在返回-1.
如果存在，则先获得 retNode， 用于return value。
接下来要进行链表的移位。 将retNode 移动到head之后的一号位置。
- put（set)的实现： 插入 <key, val2>
从map （meta) 中判断是否存在，如果不存在，则要将该tuple 插入到 head后的一号位置。
但要注意， 这里有capacity 的限制问题， 如果插入前，先作删除链表最后元素的操作； 删除之后再插入。
如果map(meta)中存在该信息， 则要进行移动位置（将key对应的node移动到一号位置）同时进行数据的刷新， Overwrite node的value为新的val2.
