运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
代码语言：javascript复制LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4解：题目要求实现O(1)时间复杂度的获取数据和写入数据。哈希表可以实现O(1)复杂度的获取数据，但是没有办法写入数据，因为没有办法判断大小，就不知道这个数据应该写到哪里。双向链表可以以O(1)时间复杂度，很方便地实现数据的插入和删除，但是没有办法直接定位。所以我们采用哈希表和双向链表相结合的方法。之所以选择双向链表而不是单链表，是为了可以从中间任意结点修改链表结构，而不必从头结点开始遍历。
- 获取数据的时候： 如果密钥存在于缓存中，那么返回缓存的value值，同时在列表中将该节点删除并且插入到链表的最前端； 如果密钥不存在于缓存中，返回-1。
- 写入数据的时候： 如果密钥存在，在链表中将该结点删除并插入到最前端； 如果密钥不存在，如果缓存容量达到上限删除链表的最后一个元素，然后将该节点插入到链表的最前端；哈希表中插入该元素。
以下是纯手打ac解，效率不是很高，可优化的地方，可以再增加一个全局变量双向链表尾部，删除最少用的缓存时可以快速删除；可以再设置一个当前容量变量，无须每次计算链表长度;map里面可以保存一个entry里面保存前后指针和值，这样删除的时候无须从头遍历，最大化使用双向链表优势。我这代码写得有点用单链表的感觉。
参考
代码语言：javascript复制class LinkedNode {
int val;
LinkedNode pre;
LinkedNode next;
LinkedNode(int x) {
val = x;
}
}
public class LRUCache {
//缓存容量
private int capacity;
//双向链表实现插入删除的时间复杂度o(1)，保存的值为缓存的key
//双向链表头部
private LinkedNode head;
//哈希表实现查找的O(1)时间复杂度，并保存缓存的key/value
private HashMap<Integer, Integer> map;
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>();
this.head = new LinkedNode(-1);
this.head.pre = null;
this.head.next = null;
}
public int get(int key) {
if (map.containsKey(key)) {
//如果缓存存在则更新链表后，返回值
delLinkedNode(key);
addLinkedNode(key);
return map.get(key);
} else {
//如果缓存不存在直接返回
return -1;
}
}
public void put(int key, int value) {
if (map.containsKey(key)) {
//如果缓存存在则更新链表后，赋新值
delLinkedNode(key);
addLinkedNode(key);
map.put(key, value);
} else {
//如果缓存不存在,未达到上限，插入链表最前端，并且加入map
if (lenLinkedNode(head) < capacity) {
addLinkedNode(key);
map.put(key, value);
} else {
//如果缓存不存在,达到上限，删除尾端节点，删除map值，插入链表最前端，并且加入map
LinkedNode dummy = head;
while (dummy.next != null) {
dummy = dummy.next;
}
delLinkedNode(dummy.val);
addLinkedNode(key);
map.remove(dummy.val);
map.put(key, value);
}
}
}
/**
* 删除一个节点
*
* @param key
*/
private void delLinkedNode(int key) {
LinkedNode dummy = head;
while (dummy.next != null) {
if (dummy.next.val == key) {
dummy.next = dummy.next.next;
if (dummy.next != null) {
dummy.next.pre = dummy;
}
break;
} else {
dummy = dummy.next;
}
}
}
/**
* 在链表头部增加一个节点
*
* @param key
*/
private void addLinkedNode(int key) {
LinkedNode tmp = head.next;
head.next = new LinkedNode(key);
head.next.pre = head;
head.next.next = tmp;
if (head.next.next != null) {
head.next.next.pre = head.next;
}
}
/**
* 计算双向链表长度
*
* @param head
* @return
*/
private int lenLinkedNode(LinkedNode head) {
LinkedNode dummy = head;
int len = 0;
while (dummy.next != null) {
len ;
dummy = dummy.next;
}
return len;
}
public static void main(String[] args) {
LRUCache cache = new LRUCache(2 /* 缓存容量 */);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
}
}
