题解 | 设计LRU缓存结构

import java.util.*;


public class Solution {

    int cap;

    Map<Integer, Node> cache;
    Node dummy;

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

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

    public Solution(int capacity) {
        // write code here
        cache = new HashMap<>();
        dummy = new Node(-1, -1);
        dummy.next = dummy;
        dummy.pre = dummy;
        this.cap = capacity;
    }

    public int get(int key) {
        // write code here
        if (cache.get(key) == null) {
            return -1;
        }
        Node node = cache.get(key);
        removeNode(node); // 删除该节点
        addToHead(node); // 添加到链表头部
        return node.val;
    }

    private void removeNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void addToHead(Node node) {
        node.next = dummy.next;
        dummy.next.pre = node;
        node.pre = dummy;
        dummy.next = node;
    }

    public void set(int key, int value) {
// write code here
        Node node = cache.get(key);
        if (node != null) {
            node.val = value;
            removeNode(node);
            addToHead(node);
            return;
        }
        node = new Node(key, value);
        addToHead(node);
        cache.put(key, node);
            
        if (cache.size() > cap) {
            Node last = dummy.pre;
            removeNode(last);
            cache.remove(last.key);
        
        }
        
        
    }
}

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