力扣146LRU缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

classListNode:def__init__(self,key=0,value=0):self.key=key self.value=value self.prev=Noneself.next=NoneclassLRUCache(object):def__init__(self,capacity):self.capacity=capacity self.cache={}self.head=ListNode()self.tail=ListNode()self.head.next=self.tail self.tail.prev=self.headdef_remove_node(self,node):node.prev.next=node.nextnode.next.prev=node.prevdef_add_to_head(self,node):node.prev=self.head node.next=self.head.nextself.head.next.prev=node self.head.next=nodedef_move_to_head(self,node):self._remove_node(node)self._add_to_head(node)def_pop_tail(self):node=self.tail.prev self._remove_node(node)returnnode.keydefget(self,key):ifkeynotinself.cache:return-1node=self.cache[key]self._move_to_head(node)returnnode.valuedefput(self,key,value):ifkeyinself.cache:node=self.cache[key]node.value=value self._move_to_head(node)else:new_node=ListNode(key,value)self.cache[key]=new_node self._add_to_head(new_node)iflen(self.cache)>self.capacity:tail_key=self._pop_tail()delself.cache[tail_key]

这个题要求put和get函数时间复杂度为O(1),所以我们需要可以选双端链表+哈希表。
首先定义一些双端链表的实现方法，新增链表节点到头节点，删除链表节点，把链表节点移到头节点，删除链表尾节点。
get函数是提取哈希表中的值，如果不存在，就返回-1，提取完之后，把这个节点移动到链表头。
put函数是把节点放到哈希表中，如果key已经存在，就是改值，改完之后把这个节点移动到链表头，如果key不存在，就添加，然后这个节点移动到链表头，但是如果超过哈希表的容量了，就要删除链表的尾节点。