数据结构为 DLNode + HashMap
import java.util.HashMap;
/**
* Created by Administrator on 2019/7/14 0014.
*/
class LRUCache {
private int count;
private int capacity;
private HashMapcache =new HashMap<>();
private DLNodepre;
private DLNodepost;
public LRUCache(int capacity) {
count =0;
this.capacity = capacity;
pre =new DLNode();
pre.setPre(null);
post =new DLNode();
post.setPost(null);
pre.setPost(post);
post.setPre(pre);
}
public int get(int key) {
DLNode node =cache.get(key);
if(node ==null){
return -1;
}
DLNode tempPre = node.getPre();
DLNode tempPost = node.getPost();
tempPre.setPost(tempPost);
tempPost.setPre(tempPre);
node.setPost(pre.getPost());
node.setPre(pre);
pre.getPost().setPre(node);
pre.setPost(node);
return node.value;
}
public void put(int key,int value) {
DLNode node =cache.get(key);
if(node ==null){//不存在
node =new DLNode(key,value);
cache.put(key,node);
count++;
if(count>capacity){//移除尾部
DLNode reNode =post.getPre();
reNode.getPre().setPost(node);
post.setPost(node);
node.setPre(reNode.getPre());
node.setPost(post);
cache.remove(reNode.key);
count--;
}else{
post.getPre().setPost(node);
node.setPre(post.getPre());
node.setPost(post);
}
}else{
DLNode tempPre = node.getPre();
DLNode tempPost = node.getPost();
node.value= value;
tempPre.setPost(tempPost);
tempPost.setPre(tempPre);
node.setPost(pre.getPost());
node.setPre(pre);
pre.getPost().setPre(node);
pre.setPost(node);
}
}
}
/**
* Created by Administrator on 2019/7/14 0014.
*/
public class DLNode {
public int key;
public int value;
private DLNodepre;
private DLNodepost;
public DLNode(){
}
public DLNode(int key,int value){
this.key = key;
this.value = value;
}
public DLNode getPre(){
return this.pre;
}
public void setPre(DLNode pre){
this.pre = pre;
}
public DLNode getPost(){
return this.post;
}
public void setPost(DLNode post){
this.post = post;
}
}
网友评论