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

LRU数据规则解释: 链表结构， 每次查询或者set都把对应节点更新到链表头部， 设置链表长度， 超过链表长度后删除链表最后一个last

难点: 获节点表要求速度为O(1)，传统链表想要查询某一数据得遍历速度是O(n), 答主是利用key的唯一性通过hash进行散列计算用来获取key对应的节点, 对传统链进行变种开发

备注: 为了和hash的散列计算结合起来， 每个链表节点都会存key， 然后这个链表设置为双向链表， 这样要移动、移除、新增某一个链表节点速度都是O(1), 计算与写入Hash也是O(1) 这样存储的时候也能保证是 O(1) + O(1) = O(1), 为了保证移除最后一个节点速度也是O(1), 把最后一个节点也存到变种链表里了

author email: pythonmain@163.com