笔记 - LeetCode LRU缓存 Java

内容：

参考：
https://baijiahao.baidu.com/s?id=1767380323139541543

代码：

// LRU缓存
public class LRUCache {
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(5);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.put(3, 3);
        lruCache.put(4, 4);
        lruCache.put(5, 5);
        lruCache.put(6, 6);
        lruCache.put(7, 7);
        int i = lruCache.getValue(8);
        System.out.println("i= " + i);
        int i1 = lruCache.getValue(3);
        System.out.println("i1= " + i1);
    }

    Node[] table; // 使用数组存储缓存数据，数组下标作为key，进行直接定位。
    int size = 0, count = 0;
    Node head, tail;

    public LRUCache(int size) {
        this.size = size;
        table = new Node[1000];
        head = new Node(-1, -1); // 定义头节点
        tail = new Node(-1, -1); // 定义尾节点
        head.next = tail;
        tail.pre = head;
    }

    public int getValue(int key) {
        Node node;
        if ((node = table[key]) == null) return -1; // 如果不存在，直接返回-1
        moveToTail(node); // 将node节点移动到末尾（位置是tail节点的pre节点）
        return node.value;
    }

    public void put(int key, int value) {
        Node node;
        if ((node = table[key]) != null) { // 已存在节点，直接修改value值
            node.value = value;
        } else { // 不存在节点，则新建Node
            if (count < size) { // 没有到达容量上限
                count++;
            } else { // 超出容量上限，则需要删除“最近最少使用”的节点
                table[head.next.key] = null;
                deleteNode(head.next);
            }
            node = new Node(key, value);
            table[key] = node;
        }
        moveToTail(node); // 将node节点移动到末尾
    }

    // 删除节点操作
    public void deleteNode(Node node) {
        if (node.pre == null || node.next == null) {
            return;
        }
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    // 将节点移动到“末尾”操作（位置是tail节点的pre节点）
    public void moveToTail(Node node) {
        if (tail.pre == node) {
            return; // 如果已经是“末尾”节点，则不操作
        }
        deleteNode(node); // 删除该节点的前后关联，下面会进行重新关联操作
        tail.pre.next = node;
        node.pre = tail.pre;
        node.next = tail;
        tail.pre = node;
    }

    // 双向链表结构
    class Node {
        public int key, value;
        public Node pre, next;

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