在我第一次写LRU时，应用map+列表的模式，map使得get和set的工夫复杂度为O(1)，列表保护插入元素的程序，当get或set元素时，将元素挪动或插入到队头；当达到LRU缓存容量下限时，将列表尾部元素去除掉。然而在列表中调整元素程序时，工夫复杂度达不到O(1)。
明天写了一个改进版，应用map+双向链表的模式。map存储key和链表节点的指针，双向链表中既存储key也存储value。map仍然用来使get和set的工夫复杂度为O(1)，当须要将元素挪动到队头时，仅需通过map找到节点，将节点左右连贯打断，而后插入到队头，当删除元素或队头插入元素时，仅需找到头尾节点再进行插入或删除就能够了。这样取代列表后，工夫复杂度变为O(1)。
援用一张图来阐明这个构造。
操作流程：
get操作：
- 在map中存在：将元素挪动至链表头节点，返回value值
- 在map中不存在：返回-1
set操作：
- 在map中存在：批改节点中value的值，而后将节点挪动到链表头节点
- 在map中不存在：
- 没有达到cap下限：构建节点，map中存储此节点，而后将节点插入到头节点
- 达到cap下限：先删除链表队尾元素，删除map中的key。而后构建节点，map中存储此节点，而后将节点插入到头节点
代码：
package mainimport "fmt"// map用来get 和 set，双向链表放弃绝对程序// 为什么用双向链表？因为在删除节点时，以及插入到头部时，工夫复杂度都是1type Node struct { pre *Node next *Node key int // 不便删除map中的key value int //}type lruCache struct { cap int // 存储容量，达到容量后再插入则须要删除元素 headNode *Node // 双向链表头节点， tailNode *Node // 双向链表尾节点， nodeMap map[int]*Node // 使得get、set操作工夫复杂度为1}func (l *lruCache) get(k int) int { node := l.nodeMap[k] if node == nil{ return -1 } // 获取元素，并将此元素挪动到head头地位 headNode := l.headNode // 将节点截取 node.pre.next = node.next node.next.pre = node.pre // 而后将此节点插入到头节点 headNode.next.pre = node node.next = headNode.next headNode.next = node node.pre = headNode v := node.value return v}func (l *lruCache) set(k, v int) { node := l.nodeMap[k] // 第一种状况，k在map中不存在，直接插入到头节点 if node == nil{ // 思考lru的容量，达到容量后则要删除尾部元素(间接让尾部元素的指针断开) if len(l.nodeMap) == l.cap { lastNode := l.tailNode.pre lastNode.pre.next = l.tailNode l.tailNode.pre = lastNode.pre lastNode.pre = nil lastNode.next = nil // map中也要删除 deleteKey := lastNode.key delete(l.nodeMap, deleteKey) } newNode := &Node{ pre: l.headNode, next: l.headNode.next, key: k, value: v, } l.headNode.next = newNode newNode.next.pre = newNode // map中设置值 l.nodeMap[k] = newNode }else{ // 第二种状况，key在map中存在。将map的值更改，而后将此值挪动到头部 node.value = v // 将节点截取 node.pre.next = node.next node.next.pre = node.pre // 而后将此节点插入到头节点 firstNode := l.headNode secondNode := l.headNode.next firstNode.next = node secondNode.pre = node node.next = secondNode node.pre = firstNode }}func main() { head := &Node{ pre: nil, next: nil, key: 0, value: 0, } tail := &Node{ pre: nil, next: nil, key: 0, value: 0, } head.next = tail tail.pre = head lru := lruCache{ cap: 2, headNode: head, tailNode: tail, nodeMap: make(map[int]*Node), } lru.set(1,1) lru.set(2, 2) re := lru.get(1) fmt.Println(re) // 1 lru.set(3,3) re = lru.get(2) fmt.Println(re) // -1 re = lru.get(3) fmt.Println(re) // 3 lru.set(4, 4) re = lru.get(1) fmt.Println(re) // -1 re = lru.get(3) fmt.Println(re) // 3 re = lru.get(4) fmt.Println(re) // 4}