题解 | #设计LRU#

哈希表+双向链表

import java.util.*;


public class Solution {
    class Node {
        Node pre;
        Node next;
        int key;
        int value;
        public Node(int key, int value) {
            this.value = value;
            this.key = key;
        }
    }
    HashMap<Integer, Node> table = new HashMap<>();
    int capacity;
    Node head;
    Node tail;
    public Solution(int capacity) {
        // write code here
        this.capacity = capacity;
        this.head = new Node(-1, -1);
        this.tail = new Node(-1, -1);
        this.head.next = tail;
        this.tail.pre = head;
    }

    public int get(int key) {
        // write code here
        Node node = table.get(key);
        if (node == null) {
            return -1;
        }
        //更新缓存
        removeNode(node);
        addToHead(node);
        return node.value;
    }

    public void set(int key, int value) {
        // write code here
        Node node = table.get(key);
        if (node == null) {
            node = new Node(key, value);
            table.put(key, node);
        } else {
            node.value = value;
            removeNode(node);
        }
        addToHead(node);
        //超过容量则删除最后一个数据节点
        if (table.size() == capacity + 1) {
            Node last = table.get(this.tail.pre.key);
            removeNode(last);
            table.remove(last.key);
        }
    }
    //将node节点从双向链表中移除
    public void removeNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    //将node节点添加到第一个数据节点
    public void addToHead(Node node) {
        node.next = this.head.next;
        this.head.next.pre = node;
        node.pre = this.head;
        this.head.next = node;
    }
}