type Node struct {
key, val int
next, prev *Node
}
func NewNode(k, v int) *Node {
return &Node{key: k, val: v}
}
type DoubleList struct {
head, tail *Node
size int
}
func NewDoubleList() *DoubleList {
head := &Node{key: 0, val: 0}
tail := &Node{key: 0, val: 0}
head.next, tail.prev = tail, head
return &DoubleList{
head: head,
tail: tail,
size: 0,
}
}
func (this *DoubleList) AddLast(n *Node) {
n.prev = this.tail.prev
n.next = this.tail
this.tail.prev.next = n
this.tail.prev = n
this.size++
}
func (this *DoubleList) Remove(n *Node) {
n.prev.next = n.next
n.next.prev = n.prev
n.prev = nil
n.next = nil
this.size--
}
// 删除链表中的第一个节点并且返回这个节点
func (this *DoubleList) RemoveFirst() *Node {
if this.head.next == this.tail {
return nil
}
node := this.head.next
this.Remove(node)
return node
}
func (this *DoubleList) Size() int {
return this.size
}
type LRUCache struct {
_map map[int]*Node
cache *DoubleList
cap int
}
func Constructor(capacity int) LRUCache {
return LRUCache{
_map: make(map[int]*Node),
cache: NewDoubleList(),
cap: capacity,
}
}
func (this *LRUCache) makeRecently(key int) {
x := this._map[key]
this.cache.Remove(x)
this.cache.AddLast(x)
}
func (this *LRUCache) addRecently(key, val int) {
node := NewNode(key, val)
this._map[key] = node
this.cache.AddLast(node)
}
func (this *LRUCache) deleteKey(key int) {
x := this._map[key]
this.cache.Remove(x)
delete(this._map, key)
}
func (this *LRUCache) removeLastRecently() {
deleteNode := this.cache.RemoveFirst()
deletedKey := deleteNode.key
delete(this._map, deletedKey)
}
func (this *LRUCache) Get(key int) int {
if _, ok := this._map[key]; !ok {
return -1
}
this.makeRecently(key)
return this._map[key].val
}
func (this *LRUCache) Put(key int, value int) {
if _, ok := this._map[key]; ok {
this.deleteKey(key)
this.addRecently(key, value)
return
}
if this.cache.Size() == this.cap {
this.removeLastRecently()
}
this.addRecently(key, value)
}
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/