思路：使用hashmap储存key，vaule，使用双向链表以快速查到尾结点（待逐出的节点），链表的题一定要在纸上画一下，不然连着连着就不知道连在哪里去了
class LRUCache {
public class ListNode {
int key;
int value;
ListNode next;
ListNode pre;
ListNode() {
}
ListNode(int key , int value) {
this.key = key; this.value = value;}
ListNode(int kye, int value, ListNode next) {
this.key = key;this.value = value;this.next = next;}
ListNode(int kye, int value, ListNode next,ListNode pre) {
this.key = key;this.value = value;this.next = next;this.pre = pre;}
}
ListNode head;//头节点
ListNode tail;//指向尾结点的前一个节点，方便逐出最久未使用关键字
int capacity; //储存容量
int cur_capacity;//储存当前容量
Map<Integer,ListNode> map;//储存节点
public LRUCache(int capacity) {
this.head = new ListNode(0,0,null,null);
this.capacity = capacity;
this.cur_capacity = 0;
this.map = new HashMap<>();
this.tail = new ListNode(0,0,null,head);
this.head.next = tail;
}
public int get(int key) {
if(map.containsKey(key)) //最近使用到的key，将位置提前
{
if(map.get(key).next != null)
{
map.get(key).next.pre = map.get(key).pre;
map.get(key).pre.next = map.get(key).next;
}
map.get(key).next = head.next;
map.get(key).next.pre = map.get(key);
map.get(key).pre = head;
head.next = map.get(key);
return map.get(key).value;
}
else
return -1;
}
public void put(int key, int value) {
if(map.containsKey(key)) //存在,将位置提前
{
map.get(key).value = value;
if(map.get(key).next != null)
{
map.get(key).next.pre = map.get(key).pre;
map.get(key).pre.next = map.get(key).next;
}
map.get(key).next = head.next;
map.get(key).next.pre = map.get(key);
map.get(key).pre = head;
head.next = map.get(key);
}
else{
//不存在
if(this.cur_capacity < this.capacity) //容量足够，直接添加到头
{
ListNode temp = new ListNode();
temp.key = key;
temp.value = value;
temp.next = head.next;
if(temp.next != null)
temp.next.pre = temp;
temp.pre = head;
head.next = temp;
cur_capacity++;
map.put(key,temp);
}
else//容量不够，移出尾结点，添加新节点到头
{
ListNode tail_pre = tail.pre;
map.remove(tail_pre.key);
tail.pre.pre.next = tail;
tail.pre.next = null;
tail.pre = tail.pre.pre;
tail_pre.pre = null;
ListNode temp = new ListNode();
temp.key = key;
temp.value = value;
temp.next = head.next;
temp.next.pre = temp;
temp.pre = head;
head.next = temp;
map.put(key,temp);
}
}
}
}
/**
* 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);
*/
