------2020.02.18更新------
確保head.pre 和 end.next 為nil陈辱，感謝評論區(qū)朋友指出
LRU緩存淘汰算法
LRU是最近最少使用策略的縮寫奖年，是根據(jù)數(shù)據(jù)的歷史訪問記錄來進行淘汰數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)最近被訪問過沛贪，那么將來被訪問的幾率也更高”陋守。
雙向鏈表實現(xiàn)LRU
將Cache的所有位置都用雙鏈表連接起來，當一個位置被訪問(get/put)之后利赋，通過調(diào)整鏈表的指向嗅义，將該位置調(diào)整到鏈表尾的位置，新加入的Cache直接加到鏈表尾隐砸。
這樣之碗，在多次操作后，最近被訪問(get/put)的季希，就會被向鏈表尾方向移動褪那，而沒有訪問的，向鏈表前方移動式塌，鏈表頭則表示最近最少使用的Cache博敬。
當達到緩存容量上限時，鏈表頭就是最少被訪問的Cache峰尝，我們只需要刪除鏈表頭便可繼續(xù)添加新的Cache偏窝。
代碼實現(xiàn)
type Node struct {
Key int
Value int
pre *Node
next *Node
}
type LRUCache struct {
limit int
HashMap map[int]*Node
head *Node
end *Node
}
func Constructor(capacity int) LRUCache{
lruCache := LRUCache{limit:capacity}
lruCache.HashMap = make(map[int]*Node, capacity)
return lruCache
}
func (l *LRUCache) Get(key int) int {
if v,ok:= l.HashMap[key];ok {
l.refreshNode(v)
return v.Value
}else {
return -1
}
}
func (l *LRUCache) Put(key int, value int) {
if v,ok := l.HashMap[key];!ok{
if len(l.HashMap) >= l.limit{
oldKey := l.removeNode(l.head)
delete(l.HashMap, oldKey)
}
node := Node{Key:key, Value:value}
l.addNode(&node)
l.HashMap[key] = &node
}else {
v.Value = value
l.refreshNode(v)
}
}
func (l *LRUCache) refreshNode(node *Node){
if node == l.end {
return
}
l.removeNode(node)
l.addNode(node)
}
func (l *LRUCache) removeNode(node *Node) int{
if node == l.end {
l.end = l.end.pre
l.end.next = nil
}else if node == l.head {
l.head = l.head.next
l.head.pre = nil
}else {
node.pre.next = node.next
node.next.pre = node.pre
}
return node.Key
}
func (l *LRUCache) addNode(node *Node){
if l.end != nil {
l.end.next = node
node.pre = l.end
node.next = nil
}
l.end = node
if l.head == nil {
l.head = node
}
}
