最近最少未用LRUjava实现

//定义双向链表的结构
class ListNode{
public int key;
public int value;
public ListNode pre;
public ListNode next;
public ListNode(int key,int value){
this.key = key;
this.value = value;
}
}
//定义LRU缓存的结构
class LRUCache {
//为了设计最近最少未用的缓存并且时间复杂度都为O(1)
//我们首先想到时间复杂度为O（1）的查找使用hashmap来做
//但是单单使用到hash结构无法保证最近最少使用的特点于是我们想到要使用一个双向的链表来维护每次操作元素都将其移动到链表的最后表示该元素是最新被使用的，于是链表的头元素就是最近最久未用的
public int capacity;
public ListNode head;
public ListNode tail;
HashMap map;
public LRUCache(int capacity){
map = new HashMap<>();

    head = new ListNode(-1,-1);
    tail = new ListNode(-1,-1);
    head.next = tail;
    tail.pre = head;

    this.capacity = capacity;
}

public int get(int key) {
    //先判断缓存中是否存在元素
    ListNode node = map.get(key);
    if(node == null){
        return -1;
    }
    //将查询元素的双向链表节点移到尾部
    moveToTail(node,node.value);
    //返回元素
    return node.value;
}

public void put(int key, int value) {
    //判断元素是否已经存在缓存中
    if(map.containsKey(key)){
        //存在则先移动到尾部再去修改值
        ListNode node = map.get(key);
        moveToTail(node,value);
    }else{
        //判断缓存是否满了
        if(map.size() == this.capacity){
            ListNode node = head.next;
            //满了删除头节点
            delete(node);
            //删除map中的元素
            map.remove(node.key);
        }
        //插入到尾结点
        ListNode newNode = new ListNode(key,value);
        insertTail(newNode);
        map.put(key,newNode);
    }
}

//删除本节点插入到尾节点
public void moveToTail(ListNode node,int value){
    //删除当前节点
    delete(node);
    //插入到尾节点
    insertTail(node);
    //修改值
    node.value = value;
}

//删除节点
public void delete(ListNode node){
    //将前节点的尾指针指向本节点的下一个节点
    node.pre.next = node.next;
    //将尾结点的前指针指向本节点的前一个节点
    node.next.pre = node.pre;
}


//插入到尾节点
public void insertTail(ListNode node){
    //先将本节点指向最后一个节点和最后一个节点前节点
    node.pre = tail.pre;
    node.next = tail;
    //最后一个节点的后指针指向本节点
    tail.pre.next = node;
    //尾节点的前指针指向本节点
    tail.pre = node;
}

}