做过这题的都知道可以用LinkedHashMap解法，但是这篇文章是通过双向链表和哈希图结合来实现的，虽然复杂了点。但是能更好的帮助我们理解这个题的逻辑。题目我就不再在这里复述了，直接开讲。
这道题要求时间复杂度为O(1)。且有键值对的存在。所以我下意识的想到了Hashmap。但是hashmap存在一个问题。那就是hashmap中的键值对是没有排序的。这导致了我们没办法实现“先杀最不常用软件的后台”。所以我们们需要一个方法来帮我们排序。
那么我贴张图让大家看看这些数据结构的时间复杂度，从而选一个出来。
按照上面的表来看，好像没一个符合时间复杂度为O(1)的。但是链表的插入好像是满足了。又没完全满足。毕竟删除还是O(n)呢。那该怎么让删除也是O(1)呢？这个时候我们就想起了一个基于链表的数据结构——双向链表（Doublelinked list）。
所以我们现在要做的事是把Doublelinked list和Hashmap结合起来组成一个新的数据结构。
代码如下：
class LRUCache {
HashMap<Integer,Node> map = new HashMap<>();
DoubleLinkedlist cache = new DoubleLinkedlist();
int capacity;
class Node //定义Node类型
{
public int Value;
public int Key;
public Node pre;
public Node next;
public Node(int key,int value) //初始化Node
{
this.Key = key;
this.Value = value;
}
}
class DoubleLinkedlist{ //定义双向链表
Node head;
Node tail;
public DoubleLinkedlist() //初始化双向链表
{
head = new Node(0,0);
tail = new Node(0,0);
head.next = tail;
tail.pre = head;
}
public void addfirst(Node node) //双向链表add功能
{
node.next = head.next;
node.pre = head;
head.next.pre = node;
head.next = node;
}
public int delet(Node node) //delet后返回删除的key值
{
int keyvalue = node.Key;
node.next.pre=node.pre;
node.pre.next =node.next;
return keyvalue;
}
public int deletlast()
{
if(head.next == tail)
return -1;
return delet(tail.pre);
}
}
public LRUCache(int capacity)
{
this.capacity = capacity;
}
public void put(int key, int value) {
Node newnode = new Node(key,value);
if(map.containsKey(key))
{
cache.delet(map.get(key));
cache.addfirst(newnode);
map.put(key,newnode);
}
else
{
if(map.size() == capacity)
{
int k = cache.deletlast();
map.remove(k);
}
cache.addfirst(newnode);
map.put(key,newnode);
}
}
public int get(int key) {
if(!map.containsKey(key))
return -1;
Node val = map.get(key);
int a=val.Value;
put(key,a);
return a;
}
}