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

import java.util.*;
/*
解题思路
主要使用map,和双端链表解决问题
map-> key,就是你传入的key
map->value 就是一个node节点
get(key) 表示你传入的key,查map，如果有值，调整链表node节点到头.返回node.val
set(key,val) 先判断当前key元素是否在Map中，如果已经存在，直接更新node.val,并且调整node节点到表头
如果不存在，先判断链表的大小，是否已经大于其容量，如果没有大于，直接存放，并调整链表，如果大于，删除最尾部node,把需要存放的元素，放到node链表的头部




*/
public class Solution {
    private int capacity;
    private Map<Integer, Node> map;
    private Node head;
    private Node tail;
    private int used;

    class Node {
        int key;
        int value;
        Node prev;
        Node next;

        Node(int key, int value, Node prev, Node next) {
            this.key = key;
            this.value = value;
            this.prev = prev;
            this.next = next;
        }
    }

    public Solution(int capacity) {
        //该出的逻辑是初始化当前双端链表的大小
        // write code here
        this.capacity = capacity;
        this.map = new HashMap<>();
        //表示链表使用情况
        this.used = 0;
    }

    public int get(int key) {
        // write code here
        if (!map.containsKey(key)) {
            return -1;
        }

        makeRecently(key);

        return map.get(key).value;
    }

    public void set(int key, int value) {
        // 如果 key 已存在，直接修改值，再移到链表头部
        if (map.containsKey(key)) {
            map.get(key).value = value;
            makeRecently(key);
            return;
        }

        // 如果达到容量上限，就要移除尾部节点，注意 HashMap 要 remove！！！
        if (used == capacity) {
            map.remove(tail.key);
            tail = tail.prev;
            tail.next = null;
            used--;
        }
        // 头节点为空，单独处理
        if (head == null) {
            head = new Node(key, value, null, null);
            tail = head;
        } else {
            Node node = new Node(key, value, null, head);
            head.prev = node;
            head = node;
        }
        map.put(key, head);

        used++;
    }

    // 把 key 对应的节点移到链表头部
    private void makeRecently(int key) {
        Node node = map.get(key);
        if(node == head){
            return;
        }
            if (node == tail) {
                tail = tail.prev;
                tail.next = null;
            } else {
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }

            node.prev = null;
            node.next = head;
            head.prev = node;
            head = node;
        
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */