题目
解题的关键在于LRU构造体和双向链表构造体的设计以及双向链表的四个性能函数的拆分这使得题解优雅而简洁
（想起来上学期苦楚的课程）
type LRUCache struct { size int capacity int cache map[int]*DLinkedNode head, tail *DLinkedNode}type DLinkedNode struct { key, value int prev, 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.tail l.tail.prev = l.head return l}//int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。//对于 get 操作，首先判断 key 是否存在：//如果 key 不存在，则返回 -1−1；//如果 key 存在，则 key 对应的节点是最近被应用的节点。通过哈希表定位到该节点在双向链表中的地位，并将其挪动到双向链表的头部，最初返回该节点的值。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}//void put(int key, int value)如果关键字key 曾经存在，则变更其数据值value ；如果不存在，则向缓存中插入该组key-value 。如果插入操作导致关键字数量超过capacity ，则应该 逐出 最久未应用的关键字。//对于 put 操作，首先判断 key 是否存在：//如果 key 不存在，应用 key 和 value 创立一个新的节点，在双向链表的头部增加该节点，并将 key 和该节点增加进哈希表中。而后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；//如果 key 存在，则与 get 操作相似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。func (this *LRUCache) Put(key int, value int) { if _, ok := this.cache[key]; !ok { node := initDLinkedNode(key, value) this.cache[key] = node this.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 = value this.moveToHead(node) }}func (this *LRUCache) addToHead(node *DLinkedNode) { node.prev = this.head node.next = this.head.next this.head.next.prev = node this.head.next = node}func (this *LRUCache) removeNode(node *DLinkedNode) { node.prev.next = node.next node.next.prev = node.prev}func (this *LRUCache) moveToHead(node *DLinkedNode) { this.removeNode(node) this.addToHead(node)}func (this *LRUCache) removeTail() *DLinkedNode { node := this.tail.prev this.removeNode(node) return node}