请你设计并实现一个满足  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) 的平均时间复杂度运行

 

class LinkNode{
//第一步，建立哈希表和双向链表
//哈希表的目的是在于可以迅速找到key对应的链表节点
//双向链表的目的是在于可以快速地进行更新和删除操作，维护头结点和尾节点，便于进行插入和删除操作int key;//哈希表的键int val;//哈希表的值LinkNode front;LinkNode next;public LinkNode(int key,int val){this.key = key;this.val = val;}
}
class LRUCache {
//定义缓存大小int  capacity;Map<Integer,LinkNode> map = new HashMap<>();//声明链表head和tail方便使用LinkNode head = new LinkNode(0,0);LinkNode tail = new LinkNode(0,0);public LRUCache(int capacity) {this.capacity = capacity;head.next = tail;tail.front = head;}public int get(int key) {/*** 如果包含此节点，取其值，并将其移动到头节点*/if(map.containsKey(key)){LinkNode node=map.get(key);moveNodeToTop(node);return node.val;}else{return -1;}}public void put(int key, int value) {
//首先写put//判断是否存在此节点if(!map.containsKey(key)){
//如果当前节点数量超过容量，删除最后一个节点if(map.size()==capacity) deleteLastNode();//如果不存在，添加新的节点LinkNode temp = head.next;LinkNode newNode = new LinkNode(key,value);head.next = newNode;newNode.front = head;newNode.next =temp;temp.front =newNode;map.put(key,newNode);}else{LinkNode node = map.get(key);node.val=value;moveNodeToTop(node);}}/*** 删除最后一个节点*/private void deleteLastNode(){LinkNode lastNode = tail.front;lastNode.front.next=tail;tail.front=lastNode.front;map.remove(lastNode.key);}//移动到头节点private void moveNodeToTop(LinkNode node){node.front.next=node.next;node.next.front=node.front;LinkNode temp = head.next;node.front=head;head.next=node;node.next=temp;temp.front=node;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/