146. LRU 缓存

要实现时间复杂度为 O ( 1 ) O(1) O(1) 的存取操作，就需要使用双向链表进行头插与删除，使用哈希表对存取时已存在的结点进行锁定。

struct LinkList{
    int k, val;
    LinkList *prev;
    LinkList *next;
    LinkList(): k(0), val(0), prev(nullptr), next(nullptr) {};
    LinkList(int key, int value): k(key), val(value), prev(nullptr), next(nullptr) {};
};

class LRUCache {
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        head = new LinkList();
        tail = new LinkList();
        head->next = tail;
        tail->prev = head;
        size = 0;
    }
    
    int get(int key) {
        if(!cache.count(key))
            return -1;
        LinkList *node = cache[key];
        node->prev->next = node->next;
        node->next->prev = node->prev;
        insert(node);
        return node->val;
    }
    
    void put(int key, int value) {
        LinkList *node = new LinkList(key, value);
        if(cache.count(key)) {
            LinkList *rm_node = cache[key];
            cache.erase(key);
            erase(rm_node);
            insert(node);
            cache[key] = node;
        }
        else {
            insert(node);
            cache[key] = node;
            if(++size > capacity) {
                LinkList *rm_node = tail->prev;
                cache.erase(rm_node->k);
                erase(rm_node);
                --size;
            }
        }
    }

    void insert(LinkList *node) {
        node->next = head->next;
        head->next->prev = node;
        node->prev = head;
        head->next = node;
    }

    void erase(LinkList *node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
        delete node;
    }

private:
    LinkList *head, *tail;
    unordered_map cache;
    int capacity, size;
};