146. LRU 缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。

实现 LRUCache 类：

• LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

思路：上图是我打开app的顺序，从左到右，从上到下。最近打开的app是天气，往后依次是小黑盒，微博，tim。如果我切换到tim，那么tim就会插入到最前面，其他所有的应用都要往后挪。

设计一个链表与哈希表结合的数据结构，链表的结点Node既保存key又保存value，而哈希表只保存key和对应的Node。

• LRUCache(int capacity)这个容量需要保存下来，为后面的put操作判断是否超过容量作准备
• int get(int key) ，如果哈希表中存在这个关键字，则返回对应Node中的value，然后将对应的node移到列表头。反之，如果不存在，则返回-1.
• void put(int key, int value)，相当于重新打开一个新的app，此时它在列表中的位置应该是最前面。如果此时超过了容量，即内存不够，则要删除，挂在后台没有使用最久的应用，在添加新的app进去。

这样频繁使用到链表头和链表尾的操作，双向链表是一个非常适合的数据结构。

代码:

struct Node {
    int key;// 链表的键
    int val;// 链表的值
    Node* prev;// 指向前一个结点的指针
    Node* next;// 指向后一个结点的指针
    Node(int key, int val) :key(key), val(val), prev(nullptr), next(nullptr) {}
};
struct my_list {
    Node* head;
    int size;
    my_list() {//链表初始化时，prev和next都指向头结点，形成环状，形成循环链表
        size = 0;
        head = new Node(-1, -1);
        head->next = head;
        head->prev = head;
    }
};
// 添加一个结点   prev--->node--->next
//				prev<---node<---next
// 这里的prev和next都代表一个结点，node是要添加的结点
void _add_node(Node* prev, Node* next, int key, int val) {
    Node* node = new Node(key, val);
    node->prev = prev;
    prev->next = node;

    node->next = next;
    next->prev = node;
}

// 和上面的函数同理
void _add_node(Node* prev, Node* next, Node* node) {
    node->prev = prev;
    prev->next = node;

    node->next = next;
    next->prev = node;
}

// 链表头添加
void add_head(my_list* list, int key, int val) {
    _add_node(list->head, list->head->next, key, val);
    list->size++;
}

// 链表尾添加
void add_tail(my_list* list, int key, int val) {
    _add_node(list->head->prev, list->head, key, val);
    list->size++;
}

// 把一个结点node移动，先让node的前一个结点的next指针指向node的下一个结点
// 然后让node的下一个结点的prev指针指向node的前一个结点
void _move(Node* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

// 将一个结点移动到链表末尾
void move_to_tail(my_list* list, Node* node) {
    _move(node);
    _add_node(list->head->prev, list->head, node);
}

// 将一个链表中的结点删除
void delete_node(my_list *list,Node* node) {
    _move(node);
    list->size--;
}

// 删除头节点
void delete_head(my_list* list) {
    delete_node(list, list->head->next);
}

class LRUCache {
private:
    my_list* list;
    int capacity;
    unordered_map<int, Node*>umap;
public:
    LRUCache(int capacity):capacity(capacity) {
        list = new my_list();
    }

    int get(int key) {
        // 如果链表中键为key的结点，说明应用链表中存在这个app，现在把它打开
        // 它就在链表的最前面了（这里把链表尾作为最前面）
        if (umap.count(key)) {
            int val = umap[key]->val;
            move_to_tail(list, umap[key]);// 移动到末尾
            return val;
        }
        return -1;
    }

    void put(int key, int value) { 
        // 如果链表中存在键key的结点，此时要更新它的值
        // 然后将它移动到链表的最前面
        if (umap.count(key)) {
            umap[key]->val = value;
            move_to_tail(list, umap[key]);
            return;
        } 
        // 如果超过了容量，则删除最末尾的app（最久没有使用的），然后把新开的app
        // 添加到最前面
        if (list->size >= capacity) {
            umap.erase(list->head->next->key);
            delete_head(list);
        }
        add_tail(list, key, value);
        umap[key] = list->head->prev;
    }
};