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

import java.util.*;

public class Solution {
    class Node {
        int key, val;
        Node prex, next;
        Node() {};
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    Map<Integer, Node> cache = new HashMap<>();
    Node head = new Node();
    Node tail = new Node();
    int size;
    int capacity;
    public Solution(int capacity) {
        // write code here
        this.capacity = capacity;
        size = 0;
        head.next = tail;
        tail.prex = head;


    }

    public int get(int key) {
        // write code here
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 移除当前节点并添加到头部
        moveToHead(node);
        return node.val;
    }

    public void set(int key, int value) {
        // write code here
        Node node = cache.get(key);
        if (node != null) {
            node.val = value;
            // 移除当前节点并添加到头部
            moveToHead(node);
        } else {
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            size++;
            // 超过阈值就缓存移除尾部节点
            if (size > capacity) {
                Node removeNode = removeTail();
                cache.remove(removeNode.key);
                size--;
            }
        }
    }
    private void addToHead(Node node) {
        node.next = head.next;
        node.prex = head;
        head.next.prex = node;
        head.next = node;
    }
    private void remove(Node node) {
        node.prex.next = node.next;
        node.next.prex = node.prex;
    }
    private void moveToHead(Node node) {
        remove(node);
        addToHead(node);
    }
    private Node removeTail() {
        Node temp = tail.prex;
        remove(temp);
        return temp;
    }
}

解题思想：LRU最近最少使用特性，获取的时候移动到头结点，设置的时候加入到头结点，如果此时超过阈值，同时移除尾部节点。