LRU 缓存
LRU 缓存：map + 双向链表
type LRUCache struct {
Size int
Capacity int
cache map[int]*DLinkedNode
head, tail *DLinkedNode
}
type DLinkedNode struct {
Key, Val int
Prev, Next *DLinkedNode
}
func Constructor(capacity int) LRUCache {
res := LRUCache{
Size: 0,
Capacity: capacity,
cache: make(map[int]*DLinkedNode, capacity),
head: &DLinkedNode{},
tail: &DLinkedNode{},
}
res.head.Next = res.tail
res.tail.Prev = res.head
return res
}
func (this *LRUCache) Get(key int) int {
node := this.cache[key]
if node == nil {
return -1
}
this.moveToHead(node)
return node.Val
}
func (this *LRUCache) Put(key int, value int) {
node := this.cache[key]
if node != nil {
node.Val = value
this.moveToHead(node)
} else {
node = &DLinkedNode{
Key: key,
Val: value,
}
if this.Size == this.Capacity {
this.deleteTail()
}
this.addToHead(node)
}
}
func (this *LRUCache) moveToHead(node *DLinkedNode) {
node.Prev.Next = node.Next
node.Next.Prev = node.Prev
node.Next = this.head.Next
this.head.Next.Prev = node
node.Prev = this.head
this.head.Next = node
}
func (this *LRUCache) addToHead(node *DLinkedNode) {
this.cache[node.Key] = node
node.Prev = this.head
node.Next = this.head.Next
this.head.Next.Prev = node
this.head.Next = node
this.Size++
}
func (this *LRUCache) deleteTail() {
if this.Size == 0 {
return
}
delete(this.cache, this.tail.Prev.Key)
this.tail.Prev.Prev.Next = this.tail
this.tail.Prev = this.tail.Prev.Prev
this.Size--
}
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/