题目力扣

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

我们可以直接继承Java中的双向列表来实现相关功能：

class LRUCache extends LinkedHashMap{private int capacity;public LRUCache(int capacity) {super(capacity, 0.75F, true);this.capacity = capacity;}public int get(int key) {return super.getOrDefault(key, -1);}public void put(int key, int value) {super.put(key, value);}@Overrideprotected boolean removeEldestEntry(Map.Entry eldest) {return size() > capacity; }
}

 其中LRUCache(int capacity) 函数为构造函数，我们这里设置负载因子为0.75，当容量达到初始量的0.75时就进行扩容处理；设置accessOrder为true，把访问过的元素放在链表后面；重写removeEldestEntry方法，当容器中的数量大于capacity时移除最旧的元素。

但是这道题的本意应该是让我们去自己实现一个双向列表，所以我们要自己使用哈希表和双向列表实现相关功能

代码：

class LRUCache {class Node {int key;int value;Node prev;Node next;public Node() {}public Node(int _key,int _value) {this.key=_key;this.value=_value;}}private Map cache = new HashMap();private int size;private int capacity;private Node head,tail;public LRUCache(int capacity) {this.size=0;this.capacity=capacity;head=new Node();tail=new Node();head.next=tail;tail.prev=head;}public int get(int key) {Node node = cache.get(key);if(node==null){return -1;}movetoHead(node);return node.value;}public void put(int key, int value) {Node node =cache.get(key);if(node==null){Node newnode=new Node(key,value);addToHead(newnode);size++;cache.put(key,newnode);if(size>capacity){size--;Node tail = removetail();cache.remove(tail.key);}}else{node.value=value;movetoHead(node);}}private void addToHead(Node node){node.prev=head;node.next=head.next;head.next.prev=node;head.next=node;}private void removeNode(Node node){node.prev.next=node.next;node.next.prev=node.prev;}private void movetoHead(Node node){removeNode(node);addToHead(node);}private Node removetail(){Node node=tail.prev;removeNode(node);return 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);*/