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

import java.util.*;


public class Solution {
// 容器
    private Map<Integer, Node> cache = new HashMap<>();
    private int size;
    private int capacity;
    private Node dummyHead, dummyTail;

    class Node {
        int key;
        int val;
        Node pre;
        Node next;

        Node() {}
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }

        Node(int key, int val, Node pre, Node next) {
            this.key = key;
            this.val = val;
            this.pre = pre;
            this.next = next;
        }
    }

    public Solution(int capacity) {
// write code here
        this.capacity = capacity;
        // 头尾相连
        dummyHead = new Node();
        dummyTail = new Node();
        dummyHead.next = dummyTail;
        dummyTail.pre = dummyHead;

        this.size = 0;
    }

    public int get(int key) {
        // write code here
        Node node = cache.get(key);
        if (null == node) return -1;
        moveToHead(node);
        return node.val;
    }

    public void set(int key, int value) {
        // write code here
        Node node = cache.get(key);
        if (null == node) {
            // 创建
            Node newNode = new Node(key, value);
            cache.put(key, newNode);
            addHead(newNode);
            this.size++;

            if (size > capacity) {
                Node tmp = removeTail();
                cache.remove(tmp.key);
                --this.size;
            }
        } else {
            // 更新键值和位置
            node.val = value;
            moveToHead(node);
        }
    }

    // 对链表的操作
    // 添加到头节点
    private void addHead(Node node) {
        node.pre = dummyHead;
        node.next = dummyHead.next;
        dummyHead.next.pre = node;
        dummyHead.next = node;
    }

    // 删除节点
    private void removeNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    // 将当前节点移到头部
    private void moveToHead(Node node) {
        removeNode(node);
        addHead(node);
    }

    // 删除尾部节点，返回值使得键值表中删除
    private Node removeTail() {
        Node node = dummyTail.pre;
        removeNode(node);
        return 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);
 */