package LRU
type LRUCache struct {
head *Node
tail *Node
Map map[int]*Node
cap int
}
type Node struct {
key int
value int
next *Node
prev *Node
}
func newNode(k, v int) *Node {
return &Node{
key: k,
value: v,
}
}
func Constructor(capacity int) LRUCache {
l := LRUCache{head: newNode(0, 0),
tail: newNode(0, 0),
Map: make(map[int]*Node),
cap: capacity,
}
l.head.next = l.tail
l.tail.prev = l.head
return l
}
func (this *LRUCache) Get(key int) int {v, ok := this.Map[key]
if !ok {return -1}
this.moveToTail(v, v.value)
return v.value
}
func (this *LRUCache) Put(key int, value int) {_, ok := this.Map[key]
if ok {this.moveToTail(this.Map[key], value)
} else {if len(this.Map) == this.cap {
toBeDelete := this.head.next
this.deleteNode(toBeDelete)
delete(this.Map, toBeDelete.key)
}
node := newNode(key, value)
this.Map[key] = node
this.insertToTail(node)
}
}
func (this *LRUCache) moveToTail(node *Node, newValue int) {this.deleteNode(node)
node.value = newValue
this.insertToTail(node)
}
func (this *LRUCache) deleteNode(node *Node) {
node.prev.next = node.next
node.next.prev = node.prev
}
func (this *LRUCache) insertToTail(node *Node) {
this.tail.prev.next = node
node.prev = this.tail.prev
node.next = this.tail
this.tail.prev = node
}