leetcode: LRU 缓存

LRU 全称为 Least Recently Used，最近最少使用，常常用于缓存机制，比如 cpu 的 cache 缓存，使用了 LRU 算法。LRU 用于缓存机制时，关键的是当缓存满的时候有新数据需要加载到缓存的，这个时候需要淘汰谁的问题。

如下图所示，表示 LRU 算法的过程。假如有一个缓存，共有 4 个存储空间，按访问时间进行排序，最左边的存储空间存储的是最近访问的数据，最右边的存储空间存储的是最长时间没有访问的数据。

（1）一开始，缓存是空的，这个时候向缓存中放入一个数据 100，100 放到最左边的存储空间

（2）向缓存中放入一个数据 50，此时缓存有空余空间，所以将已有的数据向后移动，将 50 放到缓存的最左边

（3）向缓存中放入数据 500, 步骤与上一步相同

（4）向缓存中放入数据 1000，步骤与上一步相同

（5）读取数据 100，读取之后 100 就是最后访问的数据了，所以将 100 移到缓存的最左边，其它数据依次向后移动

（6）向缓存中放入数据 1，此时缓存是满的，所以需要先淘汰一个数据，从访问时间来看，最后一次访问 50 的间隔时间最长，也就是排在最右边的数据，所以将 50 淘汰，其它数据向后移动，将新数据 1 放入最左边的位置

如下是题目描述，题目的最后要求 get() 和 put() 的时间复杂度都要是 O(1) 的。使用数组来表示缓存难以满足 O(1) 的要求，因为在 put 或者 get 的时候，会引起数组数据的移动，数组中数据的移动时间复杂度是 O(n) 的。所以需要使用链表来表示缓存，当访问一个数据的时候需要将当前这个数据从原来的位置上删除，然后加到链表的头部，删除一个节点的话，需要将这个节点的前一个节点和下一个节点连接起来，如果使用单向链表的话，那么只能找到这个节点的下一个节点，找不到上一个节点，所以需要使用双向链表。

 

（1）使用双向循环链表来表示缓存

（2）为了满足时间复杂度是 O(1) 的要求，使用 data_addr_ 数组来保存节点的地址，数组的下标是 key，题目中说明了 key 的取值范围是 [0, 10000]，所以可以使用一个数组来表示。使用 map 也不能保证时间复杂度是 O(1) 的，map 一般使用红黑树来实现，时间复杂度是 O(logn) 的。把数组的下标当 key，数组元素的值就是值，数组本省也可以当做一个简单的 map 来使用。

（3）当 put 数据时，要进行判断现在缓存是不是满了，如果满的话需要删除最久没有访问的数据，head_->next 保存最新访问的数据，head_->prev 保存最久没有访问的数据

struct Node {
    int key;
    int value;

    struct Node *next;
    struct Node *prev;
};

class LRUCache {
public:
    LRUCache(int capacity) {
      capacity_ = capacity;
      head_ = new Node();
      head_->next = head_;
      head_->prev = head_;
    }
    
    int get(int key) {
        Node *node = data_addr_[key];
        if (node == nullptr) {
            return -1;
        }

        ListUnLink(node);
        ListLinkHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
      if (data_addr_[key] != nullptr) {       
        Node *node = data_addr_[key];
        ListUnLink(node);
        node->value = value;
        ListLinkHead(node);
      } else {
        Node *new_node = new Node();
        new_node->key = key;
        new_node->value = value;
        new_node->next = nullptr;
        new_node->prev = nullptr;

        if (count_ == capacity_) {
            Node *to_delete = head_->prev;
            ListUnLink(to_delete);
            data_addr_[to_delete->key] = nullptr;
            delete to_delete;
            count_--;
        }
        
        ListLinkHead(new_node);
        data_addr_[key] = new_node;
        count_++;
      }
    }

    void ListLinkHead(struct Node *ele) {
        ele->next = head_->next;
        ele->next->prev = ele;

        head_->next = ele;
        ele->prev = head_;
    }

    void ListUnLink(struct Node *ele) {
        ele->prev->next = ele->next;
        ele->next->prev = ele->prev;
    }

private:
    int capacity_ = 0;
    int count_ = 0;
    Node *data_addr_[10001] = {nullptr};
    struct Node *head_ = nullptr;
    
};