LeetCode 146. LRU 缓存 双向链表题解，熟悉LRU实现。

题目

146. LRU 缓存

https://leetcode.cn/problems/lru-cache/

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存

int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

思路

题干中要求复杂度必须O(1)，我们只能上双向链表的版本了。具体分析参考：LRU基本实现及优化。

基于双向链表

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

public class LRUCache {

    /**
     * 执行用时：
     * 57 ms
     * , 在所有 Java 提交中击败了
     * 15.16%
     * 的用户
     * 内存消耗：
     * 113.9 MB
     * , 在所有 Java 提交中击败了
     * 26.87%
     * 的用户
     * 通过测试用例：
     * 22 / 22
     */

    int size;
    int capacity;
    Node head;
    Node tail;

    Map<Integer, Node> key2Node;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.prev = head;

        key2Node = new HashMap<>();
    }

    public int get(int key) {
        Node node = key2Node.get(key);
        if (node == null) {
            return -1;
        }
        deleteNode(node);
        insertNode2Head(node);
        return node.val;
    }

    private void insertNode2Head(Node node) {
        if (size == 0) {
            tail.prev = node;
        }
        node.next = head.next;
        node.prev = head;

        head.next.prev = node;

        head.next = node;

        ++size;
        key2Node.put(node.key, node);
    }

    private void deleteNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        --size;
        key2Node.remove(node.key);
    }

    public void put(int key, int value) {
        Node node = key2Node.get(key);
        if (node == null) {
            // 原来没有的新节点
            if (size == capacity) {
                deleteNode(tail.prev);
            }
            insertNode2Head(new Node(key, value));
        } else {
            // 原来有，先删，后增
            deleteNode(node);
            node.val = value;
            insertNode2Head(node);
        }
    }

    public void print() {
        System.out.println("size:" + size + " capacity:" + capacity);
        Node curr = head.next;
        while (curr != null) {
            System.out.print(curr.val + "-->");
            curr = curr.next;
        }
        System.out.println();
    }

    static class Node {
        int key;
        int val;

        Node prev;
        Node next;

        public Node() {
        }

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

Ref