package LinkedList
type LRUNode struct {
key, val int
prev, next *LRUNode
}
type LRUCache struct {
size, capacity int
hashMap map[int]*LRUNode
virtualHead *LRUNode
virtualTail *LRUNode
}
func Constructor(capacity int) LRUCache {
cache := LRUCache{
size: 0,
capacity: capacity,
hashMap: make(map[int]*LRUNode),
virtualHead: new(LRUNode),
virtualTail: new(LRUNode),
}
cache.virtualHead.next = cache.virtualTail
cache.virtualTail.prev = cache.virtualHead
return cache
}
// Get 单次操作时间复杂度: O(1)
func (this *LRUCache) Get(key int) int {
if node, ok := this.hashMap[key]; !ok {
return -1
} else {
ret := node.val
this.moveToHead(node)
return ret
}
}
// Put 单次操作时间复杂度: O(1)
func (this *LRUCache) Put(key int, value int) {
if node, ok := this.hashMap[key]; ok {
node.val = value
this.moveToHead(node)
} else {
node = new(LRUNode)
node.key = key
node.val = value
this.hashMap[key] = node
this.insertToHead(node)
if this.size == this.capacity {
last := this.virtualTail.prev
delete(this.hashMap, last.key)
this.removeAtTail()
} else {
this.size++
}
}
}
func (this *LRUCache) moveToHead(node *LRUNode) {
node.prev.next = node.next
node.next.prev = node.prev
first := this.virtualHead.next
this.virtualHead.next = node
node.prev = this.virtualHead
node.next = first
first.prev = node
}
func (this *LRUCache) insertToHead(node *LRUNode) {
first := this.virtualHead.next
this.virtualHead.next = node
node.prev = this.virtualHead
node.next = first
first.prev = node
}
func (this *LRUCache) removeAtTail() {
lastPrev := this.virtualTail.prev.prev
lastPrev.next = this.virtualTail
this.virtualTail.prev = lastPrev
}