题解 | #设计LRU缓存结构#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param operators string字符串ArrayList
     * @param param int整型ArrayList<ArrayList<>>
     * @param capacity int整型
     * @return string字符串ArrayList
     */


    private int len;  //缓存剩余容量
    private Map<Integer,Node> map; //哈希表
    private Node head; //链表头
    private Node tail; //链表尾
    //建立节点
    class Node {
        int key;
        int value;
        Node pre;
        Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public Solution(int capacity) {//构造器初始化
        this.len=capacity;//剩余量
        this.map=new HashMap<>();
        head=new Node(-1,-1);  //创建出链表头
        tail=new Node(-1,-1); //创建出一个链表尾 头和尾都是为了插入和删除方便
        head.next=tail;  //双向链表，头尾相连
        tail.pre=head;
    }

   


    public int get(int key) {
        int res = -1;
        if (map.containsKey(key)) {
            Node node = map.get(key);
            res = node.value;
            moveToHead(node);
        }
        return res;
    }

    //将元素插入LRU中
    public void set(int key, int val) {

        if (!map.containsKey(key)) {
            Node node = new Node(key, val);
            map.put(key, node);
            if (this.len > 0) {
                addToHead(node);
            } else {
                moveLast();
                addToHead(node);
            }
        } else {
            Node node = map.get(key); //这里利用map的特性直接锁定到双向链表中的那个Node 不需要再遍历查找
            node.value = val;
            map.put(key,node);
            moveToHead(node);
        }

    }

    public void addToHead(Node node) {
        node.next = head.next;
        node.pre = head;
        head.next.pre = node;
        head.next = node;
        this.len--;
    }

    public void moveLast() {
        map.remove(tail.pre.key);
        tail.pre.pre.next = tail;
        tail.pre = tail.pre.pre;
        this.len++;
    }

    public void moveToHead(Node node) {
        //如果是头结点
        if (node.pre == head) {
            return ; //不需要再进行操作
        }
        //如果不是头结点
        node.pre.next = node.next;
        node.next.pre = node.pre;
        this.len++;
        addToHead(node);
    }
}