LRU

146. LRU 缓存

struct dListNode{
    dListNode* prev;
    dListNode* next;
    int key, value;
    dListNode():prev(nullptr), next(nullptr), key(0), value(0){};
    dListNode(int _key, int _value):prev(nullptr), next(nullptr), key(_key), value(_value){};
};
class LRUCache {
private:
    unordered_map<int, dListNode*> hashmap;
    int capacity, size;
    dListNode* front;
    dListNode* back;
public:
    LRUCache(int _capacity):capacity(_capacity), size(0){
        front = new dListNode();
        back = new dListNode();
        front->next = back;
        back->prev = front;
    }
    int get(int key) {
        if(!hashmap.count(key)){
            return -1;
        }
        dListNode* node = hashmap[key];
        moveTohead(node);
        return node->value;
    }
    void put(int key, int value) {
        if(hashmap.count(key)){
            dListNode* node = hashmap[key];
            node->value = value;
            moveTohead(node);
        }else{
            dListNode* node = new dListNode(key, value);
            addTohead(node);
            size ++;
            hashmap[key] = node;
            if(size > capacity){
                dListNode* tail = removeTail();
                size --;
                hashmap.erase(tail->key);
                delete tail;
            }
        }
    }
    void addTohead(dListNode* node){
        dListNode* nex = front->next;
        front->next = node;
        node->prev = front;
        node->next = nex;
        nex->prev = node;
    }
    void removeNode(dListNode* node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    void moveTohead(dListNode* node){
        removeNode(node);
        addTohead(node);
    }
    dListNode* removeTail(){
        dListNode* tail = back->prev;
        removeNode(tail);
        return tail;
    }
};