146. LRU 缓存

LRU：最近最少未使用，很少被请求的数据才会被淘汰掉

本质：让不经常访问的数据往下排，经常访问的数据往上排。

这样会导致：冷门数据在最下边，热门数据在最上边。
如果访问的数据缓存中没有且缓存已经满了：把最下边的数据淘汰掉，再把刚访问的数据放到上边（换页）

分析：

选用什么数据结构？
数组：添加一个节点，所有节点都要往后移动，时间复杂度O(n)
链表：添加节点、删除节点只需要改变节点指向，时间复杂度O(1)。只需要改变指针的指向即可。由于不仅要直到节点的下一位，还需要直到节点的上一位，所以使用双向链表。

怎么找到链表的某个节点？
正常查询链表的某个节点，需要逐个遍历链表元素，时间复杂度O(n)。那有没有办法优化到O(1)的时间复杂度呢？

hashMap的查询时间复杂度是O(1)，可以用hashMap来存储链表节点。

最后选择数据结构如下：

双向链表数据结构

class Node {
public:    
    int key;
    int value;
    Node *pre;
    Node *next;
    Node(int key, int value) {
        this->key = key;
        this->value = value;
        this->pre = nullptr;
        this->next = nullptr;
    }
    Node() {
        this->key = 0;
        this->value = 0;
        this->pre = nullptr;
        this->next = nullptr;
    }
};

class LRUCache {
public:
    int capacity;
    int size;

    Node *head; // 头节点（哨兵）
    Node *tail; // 尾节点（哨兵）

    unordered_map<int, Node*> mp; // map

    LRUCache(int capacity) {
        this->capacity = capacity;
        this->size = 0;
        // 初始化双向链表
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->pre = head;
    }
    
    int get(int key) {
        if(mp.find(key) == mp.end()) { // 未找到
            return -1;
        }
        Node *node = mp[key];
        deleteNodeAndInsertHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if(mp.find(key) == mp.end()) { // 缓存中没有
            if(size == capacity) { // 缓存已满，调页
                Node *delNode = tail->pre; // 要调出的节点
                deleteNode(delNode); // 调出
                mp.erase(delNode->key);// 更新map
            }else {
                // 缓存未满 - 直接提到头部
                ++size; //更新size
            }
            Node *node = new Node(key, value);
            insertHead(node); // 提到头部
            mp[key] = node; // 更新map
        }else {
            // 缓存中有 - 更新 - 提到头部
            Node *node = mp[key];
            node->value = value; // 更新node
            mp[key] = node; // 更新map
            deleteNodeAndInsertHead(node); // 提到头部
        }
    }
private:
    // 删除节点
    void deleteNode(Node *node) {
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }
    // 插入头部
    void insertHead(Node *node) {
        head->next->pre = node;
        node->next = head->next;
        node->pre = head;
        head->next = node;
    }
    // 删除节点插入头部的连续操作(正常访问一个节点，都需要做这两步操作)
    void deleteNodeAndInsertHead(Node *node) {
        deleteNode(node);
        insertHead(node);
    }
};

时间复杂度: O(n)
空间复杂度: O(1)