2020-09-18：LRU手撸，说下时间复杂度和空间复杂度。

package test40_lru

import (
    "fmt"
    "testing"
)

/*
哈希表 + 双向链表
时间复杂度：对于 put 和 get 都是 O(1)O(1)。
空间复杂度：O(capacity)，因为哈希表和双向链表最多存储 capacity+1 个元素。
*/
//https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/
//go test -v -test.run TestLru
func TestLru(t *testing.T) {
    cache := NewLRUCache(2)

    cache.Put(1, 1)
    cache.Put(2, 2)
    cache.Get(1)    // 返回  1
    cache.Put(3, 3) // 该操作会使得关键字 2 作废
    cache.Get(2)    // 返回 -1 (未找到)
    cache.Put(4, 4) // 该操作会使得关键字 1 作废
    cache.Get(1)    // 返回 -1 (未找到)
    cache.Get(3)    // 返回  3
    cache.Get(4)    // 返回  4

}

type LRUCache struct {
    size       int
    capacity   int
    cache      map[int]*DLinkedNode
    head, tail *DLinkedNode
}

type DLinkedNode struct {
    key, value int
    prev, next *DLinkedNode
}

func NewDLinkedNode(key, value int) *DLinkedNode {
    return &DLinkedNode{
        key:   key,
        value: value,
    }
}

func NewLRUCache(capacity int) LRUCache {
    l := LRUCache{
        cache:    map[int]*DLinkedNode{},
        head:     NewDLinkedNode(0, 0),
        tail:     NewDLinkedNode(0, 0),
        capacity: capacity,
    }
    l.head.next = l.tail
    l.tail.prev = l.head
    return l
}

//获取元素
func (f *LRUCache) Get(key int) int {
    //如果缓存里未找到元素
    if _, ok := f.cache[key]; !ok {
        fmt.Println(-1)
        return -1
    }

    //缓存里有元素
    node := f.cache[key]

    //如果 key 存在，先通过哈希表定位，再移到头部
    f.moveToHead(node)
    fmt.Println(node.value)
    return node.value
}

//放入元素
func (f *LRUCache) Put(key int, value int) {
    //如果缓存里没有元素
    if _, ok := f.cache[key]; !ok {
        node := NewDLinkedNode(key, value)
        f.cache[key] = node
        //放在头部
        f.addToHead(node)
        f.size++
        //如果元素个数大于容量，需要删除元素
        if f.size > f.capacity {
            //删除链表尾部
            removed := f.removeTail()
            //删除map中的key
            delete(f.cache, removed.key)
            f.size--
        }
    } else { //缓存里有元素
        //获取元素
        node := f.cache[key]
        //修改值
        node.value = value
        //移动到链表头
        f.moveToHead(node)
    }
}

//添加到头节点
func (f *LRUCache) addToHead(node *DLinkedNode) {
    node.prev = f.head
    node.next = f.head.next
    f.head.next.prev = node
    f.head.next = node
}

//删除节点
func (f *LRUCache) removeNode(node *DLinkedNode) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

//移动到头节点
func (f *LRUCache) moveToHead(node *DLinkedNode) {
    f.removeNode(node)
    f.addToHead(node)
}

//删除尾部
func (f *LRUCache) removeTail() *DLinkedNode {
    node := f.tail.prev
    f.removeNode(node)
    return node
}