请你设计并实现一个满足 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,key0,value0):self.keykey self.valuevalue self.prevNoneself.nextNoneclassLRUCache(object):def__init__(self,capacity):self.capacitycapacity self.cache{}self.headListNode()self.tailListNode()self.head.nextself.tail self.tail.prevself.headdef_remove_node(self,node):node.prev.nextnode.nextnode.next.prevnode.prevdef_add_to_head(self,node):node.prevself.head node.nextself.head.nextself.head.next.prevnode self.head.nextnodedef_move_to_head(self,node):self._remove_node(node)self._add_to_head(node)def_pop_tail(self):nodeself.tail.prev self._remove_node(node)returnnode.keydefget(self,key):ifkeynotinself.cache:return-1nodeself.cache[key]self._move_to_head(node)returnnode.valuedefput(self,key,value):ifkeyinself.cache:nodeself.cache[key]node.valuevalue self._move_to_head(node)else:new_nodeListNode(key,value)self.cache[key]new_node self._add_to_head(new_node)iflen(self.cache)self.capacity:tail_keyself._pop_tail()delself.cache[tail_key]这个题要求put和get函数时间复杂度为O(1),所以我们需要可以选双端链表哈希表。首先定义一些双端链表的实现方法新增链表节点到头节点删除链表节点把链表节点移到头节点删除链表尾节点。get函数是提取哈希表中的值如果不存在就返回-1提取完之后把这个节点移动到链表头。put函数是把节点放到哈希表中如果key已经存在就是改值改完之后把这个节点移动到链表头如果key不存在就添加然后这个节点移动到链表头但是如果超过哈希表的容量了就要删除链表的尾节点。