leetcode 146 题：设计一个LRU缓存。

我们知道LRU的意思是最近最少使用，这肯定是用链表实现最合适，大概想一下都知道要怎么样做，但真正去实现的时候，还是需要思考一下的。有几个要点需要把握：

1. 用一个map和list实现，map的键是key（题目为了简化设定为int，实际场景中可能是int类型的hash值），值是list的元素。
2. list的元素不是只有值，而是key和value都存储起来。
3. 无论读写，都是先检查要寻找的key是否在map中。

type KV struct {
    Key int
    Val int
}

type LRUCache struct {
    cap   int
    cache map[int]*list.Element
    list  *list.List
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        cap:   capacity,
        cache: make(map[int]*list.Element),
        list:  list.New(),
    }
}

func (this *LRUCache) Get(key int) int {
    if ele, ok := this.cache[key]; ok {
        this.list.MoveToFront(ele)
        return ele.Value.(*KV).Val
    }
    return -1
}

func (this *LRUCache) Put(key int, value int) {
    if ele, ok := this.cache[key]; ok {
        ele.Value.(*KV).Val = value
        this.list.MoveToFront(ele)
    } else {
        // 注意这里是 >=
        if len(this.cache) >= this.cap {
            back := this.list.Back()
            delete(this.cache, back.Value.(*KV).Key)
            this.list.Remove(back)
        }
        ele := this.list.PushFront(&KV{key, value})
        this.cache[key] = ele
    }
}