问题描述：

LeetCode题目 ：146.LRU缓存的实现()

要求：设计实现一个LRU（最近最少使用）的缓存淘汰机制。时间复杂度控制在O(1)

分析：

1. 首先分析，最近最少使用，如果是每个元素记录一个最后被使用到的时间记录，是可以实现的，不过要遍历，方法有些笨；

2. 先使用最简单的数据结构数组，新使用到的元素放在头部，慢慢沉积到尾部的就是应该优先淘汰的元素；（利用线性机构的头尾，区分是否最近使用的到。）

3. 其次考虑O(1)如何实现，提到O(1) 优先想到的就是HashMap，另外数组遍历无法做到O(1)，并且增删数据不便，考虑使用链表；

4. 为元素的增删O(1)，因此需要维护一个双向链表。

因此决定：双向链表+HashMap

伪代码：

Get：查找依赖HashMap，移动依赖链表指针。

if   HashMap查询是否存在{
    // 存在
    (1)存在则将节点移动到头部（因为它最近被用到了）；
    (2)返回value
} 

返回-1 // 没查到

Put：

if   HashMap查询是否存在{
        // 存在
        (1) 更新节点值；
        (2)并且将节点移动到头部（被用到）；
} else{
        // 不存在
        (1) if 当前缓存空间是否够用 {
                // 不够用 则需要LRU淘汰
                (1) 删除链表尾部节点
               (2) 删除HashMap中尾部节点Key
        }

        // 正常加入即可
        (1) 链表添加新节点
        (2) HashMap增加新KV
}

Go实现：

package main

import "fmt"

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */
 
func main() {
   capacity := 2
   obj := Constructor(capacity)
   obj.Put(2, 1)
   obj.Put(2, 2)
   fmt.Println(obj.Get(2))
   obj.Put(1, 1) // LRU
   obj.Put(4, 1) // LRU
   fmt.Println(obj.Get(2))
}

type LinkNode struct {
   key, val  int
   next, pre *LinkNode
}

type LRUCache struct {
   searchMap  map[int]*LinkNode
   cap        int
   head, tail *LinkNode
}

func Constructor(capacity int) LRUCache {
   head := &LinkNode{0, 0, nil, nil}
   tail := &LinkNode{0, 0, nil, nil}

   head.pre = tail
   tail.next = head

   return LRUCache{make(map[int]*LinkNode, 0), capacity, head, tail}
}

func (this *LRUCache) Get(key int) int {
   // hash表查询是否存在
   node, exist := this.searchMap[key]
   if exist {
      // 存在则将该元素移至头部
      this.moveToHead(node)
      return node.val
   }

   // 不存在则返回-1
   return -1
}

func (this *LRUCache) Put(key int, value int) {
   // hash表查询是否存在
   node, exist := this.searchMap[key]
   if exist {
      node.val = value // 更新为新值
      // 存在则将该元素移至头部
      this.moveToHead(node)
   } else {
      newNode := &LinkNode{key, value, nil, nil}
      if len(this.searchMap) == this.cap { // 内存已经满了
         delete(this.searchMap, this.tail.next.key) // 从hash表删除
         this.removeNode(this.tail.next)            // 淘汰末尾元素
      }
      this.addNode(newNode)
      this.searchMap[key] = newNode
   }
}

func (this *LRUCache) moveToHead(node *LinkNode) {
   this.removeNode(node)
   this.addNode(node)
}

// 头部加入
func (this *LRUCache) addNode(node *LinkNode) {

   head := this.head

   node.next = head
   node.pre = head.pre

   head.pre.next = node
   head.pre = node
}

//
func (this *LRUCache) removeNode(node *LinkNode) {
   node.pre.next = node.next
   node.next.pre = node.pre
}