LRU缓存结构:手写双向链表不借助LinkedHashMap

import java.util.;
public class Solution {
/*
* lru design
* @param operators int整型二维数组 the ops
* @param k int整型 the k
* @return int整型一维数组
/
class DubbleList{
int key,value;
DubbleList pre,next;
public DubbleList(int key,int value){
this.key=key;
this.value=value;
}
}
private Map<Integer,DubbleList> map;
//容量
private int capacity;
//虚拟头节点
private DubbleList head;
//虚拟尾节点
private DubbleList tail;
//链表大小
private int size=0;
public int[] LRU (int[][] operators, int k) {
List<integer> list=new ArrayList<>();
map=new HashMap<>(k);
capacity=k;
head=new DubbleList(-2</integer>10^9-1,-210^9-1);
tail=new DubbleList(-210^9-1,-2*10^9-1);
head.next=tail;
tail.pre=head;
for(int i=0;i<operators.length;i++){
if(operators[i][0]==1){
set(operators[i][1],operators[i][2]);
}else{
list.add(get(operators[i][1]));
}
}
int [] ans=new int[list.size()];
for(int i=0;i<ans.length;i++){
ans[i]=list.get(i);
}
return ans;
}
public int get(int key){
if(!map.containsKey(key)){
return -1;
}
//存在这个健就找到它
DubbleList node=map.get(key);
//把此键移动到链表头部
moveToHead(node);
//返回此键的值
return node.value;
}
public void set(int key,int value){
//要插入的键值对不存在
if(!map.containsKey(key)){
DubbleList node=new DubbleList(key,value);
//插入操作超内存
if(size==capacity){
//删除尾节点
DubbleList nodeTail =removeTail();
//同时返回尾结点信息方便哈希表进行删除
map.remove(nodeTail.key);
}
//没超内存头部插入
addFirst(node);
//同时map更新
map.put(key,node);
}else{
//要插入的键值对存在
DubbleList val=map.get(key);
//判断要插入的value和原来的value是否相等
//不相等则更新
if(val.value!=value){
val.value=value;
map.put(key,val);
}
//不要忘记移动到头部
moveToHead(val);
}
}
//双向链表头部插入节点
public void addFirst(DubbleList list){
list.pre=head;
list.next=head.next;
DubbleList next=head.next;
head.next=list;
next.pre=list;
size++;
}
//双向链表删除尾部节点(返回删除的节点)
public DubbleList removeTail(){
DubbleList list=tail.pre;
//虚拟尾结点前驱先指向待删除节点的上一个节点
tail.pre=tail.pre.pre;
//上一个节点的后继指向虚拟尾结点
tail.pre.next=tail;
size--;
return list;
}
//删除双向链表中指定节点
public void remove(DubbleList list){
list.pre.next=list.next;
list.next.pre=list.pre;
size--;
}
//移动双向链表的指定节点到头部
public void moveToHead(DubbleList list){
remove(list);
addFirst(list);
}
}