LeetCode 146. LRU缓存机制Golang版

1. 问题描述

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。
实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

2. 思路

3. 代码

type LRUCache struct {size intcapacity intcache map[int]*DLinkedNodehead, tail *DLinkedNode
}type DLinkedNode struct {key, value intprev, next *DLinkedNode
}func initDLinkedNode(key, value int) *DLinkedNode {return &DLinkedNode{key: key,value: value,}
}func Constructor(capacity int) LRUCache {l := LRUCache {cache : map[int]*DLinkedNode{},head : initDLinkedNode(0, 0),tail : initDLinkedNode(0, 0),capacity: capacity,}l.head.next = l.taill.tail.prev = l.headreturn l
}func (this *LRUCache) Get(key int) int {if _, ok := this.cache[key]; !ok {return -1}node := this.cache[key]this.moveToHead(node)return node.value
}func (this *LRUCache) Put(key int, value int)  {if _, ok := this.cache[key]; !ok {node := initDLinkedNode(key, value)this.cache[key] = nodethis.addToHead(node)this.size++if this.size > this.capacity {removed := this.removeTail()delete(this.cache,removed.key)this.size--}} else {node := this.cache[key]node.value = valuethis.moveToHead(node)}
}func (this *LRUCache) moveToHead(node *DLinkedNode) {this.removeNode(node)this.addToHead(node)
}func (this *LRUCache) addToHead(node *DLinkedNode) {node.prev = this.headnode.next = this.head.nextthis.head.next.prev = nodethis.head.next = node
}func (this *LRUCache) removeTail() *DLinkedNode {node := this.tail.prevthis.removeNode(node)return node
}func (this *LRUCache) removeNode(node *DLinkedNode) {node.prev.next = node.nextnode.next.prev = node.prev
}/*** Your LRUCache object will be instantiated and called as such:* obj := Constructor(capacity);* param_1 := obj.Get(key);* obj.Put(key,value);*/