Untitled

struct Node {
    int key;
    int value;
    Node* next;
    Node* prev;
    Node(int key_, int value_) {
        key = key_;
        value = value_;
        next = nullptr;
        prev = nullptr;
    }
};

class LRUCache {
public:
    int capacity;
    int length;
    Node* head;
    Node* tail;

    unordered_map<int, Node*> mp;

    LRUCache(int capacity) {
        this->capacity = capacity;
        this->length = 0;
        this->head = new Node(-1, -1);
        this->tail = new Node(-1, -1);
        this->head->next = this->tail;
        this->tail->prev = this->head;
    }

    int get(int key) {
        if (mp.find(key) != mp.end()) {
            Node* n = mp[key];
            this->remove(n);
            this->insert(n);
            return n->value;
        }
        return -1;
    }

    void put(int key, int value) {
        if (mp.find(key) != mp.end()) {
            Node* n = mp[key];
            n->value = value;
            this->remove(n);
            this->insert(n);
            return;
        }

        Node* node = new Node(key, value);
        mp.insert({key, node});
        this->insert(node);
        this->length++;
        if (this->length > this->capacity) {
            int k = this->head->next->key;
            this->remove(this->head->next);
        }
        // this->print();
    }

    void print() {
        Node* curr = this->head;
        while (curr) {
            cout << curr->value << " ";
            curr = curr->next;
        }
        cout << endl;
    }

    void insert(Node* node) {
        Node* prev = this->tail->prev;
        Node* next = this->tail;

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

    void remove(Node* node) {
        Node* prev = node->prev;
        Node* next = node->next;

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

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */