146. LRU 缓存

146. LRU 缓存

核心数据结构
双链表 + 哈希表

双链表节点
由于删除链表最后一个节点时，需要删除对应 map 中的数据，所以数据域需要保存 key ，当然 value 也是必须的。

双链表实现 3 个方法

1. addNode(node) ：在链表头部插入一个节点。
2. removeNode(node) ：删除链表中任意一个节点。
3. removeLast()：删除链表最后一个节点并返回该节点，目的是得到 key ，方便 map 也删除对应元素。可以复用 removeNode(node) 。

构造方法

• 由于需要删除链表最后一个节点，所以需要一个尾指针 tail ，便于找到最后一个节点。
• 记得初始化 head 和 tail 的指针。

get 和 put 逻辑

• 分两种情况：map 中是否存在该 key。
• 更新 node 的方法：先删除，再添加一遍。

class LRUCache {
    class Node{
        int key, val;
        Node pre, next;
        public Node() {}
        public Node(int key, int val) { this.key = key; this.val = val; }
    }
    Node head = new Node(), tail = new Node();
    HashMap<Integer, Node> map = new HashMap<>();
    int capacity, size;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        if(!map.containsKey(key)) return -1;
        Node node = map.get(key);
        removeNode(node);
        addNode(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        if(!map.containsKey(key)){
            Node node = new Node(key, value);
            addNode(node);
            map.put(key, node);
            
            size++;
            if(size > capacity){
                Node last = removeLast();
                map.remove(last.key);
                // size--;  // 可以不加, 因为题目没有删除方法, 不影响结果
            }
        }else{
            Node node = map.get(key);
            node.val = value;
            removeNode(node);
            addNode(node);
        }
    }

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

    void addNode(Node node){
        node.next = head.next;
        node.pre = head;
        head.next.pre = node;
        head.next = node;
    }

    Node removeLast(){
        Node node = tail.pre;
        removeNode(node);  // 复用 removeNode
        return node;
    }
}
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