题解 | #设计LRU缓存结构，双向链表+hash表#

import java.util.*;

//双向链表
class Node {
    int key ;//键
    int val ;//值
    Node pre ;
    Node nxt ;
    Node(int key , int val) {
        this.key = key ;
        this.val = val ;
    }
}
public class Solution {
    HashMap<Integer , Node> map ;//存储数据+查询
    int maxSize ;//最大容量
    int size ;//当前容量
    //双向链表保存数据的访问时间情况，链头为最近使用，链尾为最久未使用
    Node head_pre ;//最近使用的结点 的上一个结点（辅助结点，免去考虑在链头、链尾操作的特殊情况）
    Node tail_nxt ;//最久未使用的结点的 上一个结点（辅助结点）
    public Solution(int capacity) {
        map = new HashMap<>() ;
        this.size = 0 ;
        this.maxSize = capacity ;
        head_pre = new Node(-1,-1) ;
        tail_nxt = new Node(-1,-1) ;
        head_pre.nxt = tail_nxt ;//构建双向链表
        tail_nxt.pre = head_pre ;
    }

    public int get(int key) {
         if(!map.containsKey(key)) {
             return -1 ;
         } else {
             Node find = map.get(key) ;
             moveToHead(find) ;//将访问的节点移动到最近使用的位置（即，链表头）
             return find.val ;
         }
    }

    public void set(int key, int value) {
         if(map.containsKey(key)) {
             Node find = map.get(key) ;
             find.val = value ;
             moveToHead(find) ;
         } else {
             Node newNode = new Node(key , value) ;
             if(this.size == this.maxSize) {
                 Node last = removeTail() ;//移除最久未使用的
                 map.remove(last.key) ;
                 map.put(key , newNode) ;
                 insertHead(newNode) ;
             } else {
                 map.put(key , newNode) ;
                 insertHead(newNode) ;
                 this.size ++ ;
             }
         }
    }
    
    //将节点移动到最近使用的位置（即，链表头）
    public void moveToHead(Node node) {
        if(node.pre == head_pre) {
            return ;
        } else {
            node.pre.nxt = node.nxt ;
            node.nxt.pre = node.pre ;
            node.nxt = null ;
            node.pre = null ;
            insertHead(node) ;
        }
    }
    //在链表头插入
    public void insertHead(Node node) {
        node.nxt = head_pre.nxt ;
        head_pre.nxt = node ;
        node.nxt.pre = node ;
        node.pre = head_pre ;
    }
    //移除最后一个结点（最久未使用的），然后返回这个结点
    public Node removeTail() {
        if(head_pre.nxt == tail_nxt) return null ;
        Node target = tail_nxt.pre ;
        target.pre.nxt = target.nxt ;
        target.nxt.pre = target.pre ;
        target.pre = null ;
        target.nxt = null ;
        return target ;
    }
}

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