设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
- put(key, value)：将记录(key, value)插入该结构
- get(key)：返回key对应的value值
对于put(key, value)来说，我们需要考虑两部分：
- 如果缓存中存在，那么直接将缓存中对应的元素移动到缓存头部
- 如果缓存中不存在，那么把元素添加到缓存头部，如果此时缓存的大小超出了预先设定的值，那么则将缓存尾部的元素删除
对于get(key)来说，我们还是需要考虑两部分：
- 如果缓存中存在，那么返回该值，并且将这个值移动到缓存头部
- 如果缓存中不存在，那么返回-1
综上所述：对于一个LRU缓存来说，主要包含以下三种操作。
- 查找一个元素。
- 在缓存末尾删除一个元素。
- 在缓存头部添加一个元素。
所以，我们最容易想到的实现方式就是通过双端链表+哈希表来实现这个问题，最终实现代码如下：
class LRUCache {
private HashMap<Integer,ListNode> cache;
private int capacity;
private ListNode head,tail;
class ListNode{
int key;
int value;
ListNode prev;
ListNode next;
public ListNode(){
}
public ListNode(int key,int value){
this.key=key;
this.value=value;
}
}
public LRUCache(int capacity) {
this.capacity =capacity;
cache = new HashMap<>();
head = new ListNode();
tail = new ListNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
//首先判断一下是否存在key
ListNode node = cache.get(key);
if(node==null){
return -1;
}
//如果存在，把缓存移动到头部，返回value
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
//判断是否存在
ListNode node = cache.get(key);
//如果不存在，添加到头部,如果容量到达上限，则删除队尾的元素,如果存在直接移动到头部
if(node==null){
ListNode newNode = new ListNode(key,value);
cache.put(key,newNode);
addNode(newNode);
if(cache.size()>capacity){
ListNode last = popTail();
cache.remove(last.key);
}
}else{
node.value=value;
moveToHead(node);
}
}
public void addNode(ListNode node){
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
public void removeNode(ListNode node){
ListNode prevNode = node.prev;
ListNode NextNode = node.next;
prevNode.next = NextNode;
NextNode.prev = prevNode;
}
public void moveToHead(ListNode node){
removeNode(node);
addNode(node);
}
public ListNode popTail(){
ListNode lastNode = tail.prev;
removeNode(lastNode);
return lastNode;
}
}