题解 | #设计LRU缓存结构#

信息结构， tuple (key, value) 是取用的数据对。

使用双向链表来作底层数据结构， 链表的容量为 capacity。 设置虚拟的头尾节点。 链表的顺序前后表示 tuple 读写的

使用Map作为各节点的地址寻址字典，Key 为 tuple的key， Value为节点Node。

为什么要用双向链表，便于删除操作。

1. get的实现：

从map （meta) 中判断是否存在，如果不存在返回-1.

如果存在，则先获得 retNode， 用于return value。

接下来要进行链表的移位。 将retNode 移动到head之后的一号位置。

2. put（set)的实现： 插入 <key, val2>

从map （meta) 中判断是否存在，如果不存在，则要将该tuple 插入到 head后的一号位置。

但要注意， 这里有capacity 的限制问题， 如果插入前，先作删除链表最后元素的操作； 删除之后再插入。

如果map(meta)中存在该信息， 则要进行移动位置（将key对应的node移动到一号位置）同时进行数据的刷新， Overwrite node的value为新的val2.