乙己说：LRU 实现思路整理

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

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

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
}