YunheWang0813
10/21/2019 - 10:48 PM

0146. LRU Cache

class Node {
public:
    int key;
    int value;
    Node* next;
    Node* pre;
    Node(int k, int v): key(k), value(v) {}
};
class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity;
        head = NULL;
        tail = NULL;
    }
    int get(int key) {
        Node* node = map[key];
        if (node == NULL) return -1;
        if (node != tail) {
            if (node == head) {
                head = head -> next;
            }
            else {
                node -> pre -> next = node -> next;
                node -> next -> pre = node -> pre;
            }
            tail -> next = node;
            node -> pre = tail;
            node -> next = NULL;
            tail = node;
        }
        return node -> value;
    }
    void put(int key, int value) {
        Node* node = map[key];
        if (node != NULL) {
            node -> value = value;
            if (node != tail) {
                if (node == head) {
                    head = head -> next;
                }
                else {
                    node -> pre -> next = node -> next;
                    node -> next -> pre = node -> pre;
                }
                tail -> next = node;
                node -> pre = tail;
                node -> next = NULL;
                tail = node;
            }
        }
        else {
            Node* newNode = new Node(key, value);
            if (cap == 0) {
                Node* tmp = head;
                head = head -> next;
                map.erase(tmp -> key);
                cap++;
            }
            if (head == NULL && tail == NULL) {
                head = newNode;
            }
            else {
                tail -> next = newNode;
                newNode -> pre = tail;
                newNode -> next = NULL;
            }
            tail = newNode;
            map[key] = newNode;
            cap--;
        }
    }
private:
    unordered_map<int, Node*> map;
    int cap;
    Node* head;
    Node* tail;
};

/**
 * 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);
 */