LRU Cache

code2

class node {
public:
    int val;
    int key;
    node* next;
    node (int key = 0, int val = 0)
    {
        this->val = val;
        this->key = key;
        this->next = NULL;
    }
};

class LRUCache{
public:

    map<int, node*> hash;
    node* first;
    node* last;
    int capacity;

    LRUCache(int capacity) {
        first = new node(0, 0);
        last = NULL;
        this->capacity = capacity;
    }

    void moveToTail(int key)
    {
        node* prev = hash[key];
        if(prev == first)
        {
            return ;
        }

        node* cur = prev->next;
        if(cur == last)
        {
            last = prev;
        }

        prev->next = prev->next->next;
        if(prev->next != NULL)
        {
            hash[prev->next->key] = prev;
        }

        cur->next = first->next;
        //if(first->next != NULL)
        //{
            hash[first->next->key] = cur;
        //}

        first->next = cur;
        hash[cur->key] = first;
    }

    int get(int key) {
        if(hash.find(key) == hash.end())
        {
            return -1;
        }
        else
        {
            moveToTail(key);
            return hash[key]->next->val;
        }
    }

    void set(int key, int value) {

        if(hash.find(key) != hash.end())
        {
            moveToTail(key);
            hash[key]->next->val = value;
            return ;
        }

        node* newnode = new node(key, value);
        if(hash.size() == capacity)
        {
            node* prev = hash[last->key];
            prev->next = NULL;
            hash.erase(last->key);
            delete last;
            last = prev;
        }

        newnode->next = first->next;
        if(first->next != NULL)
        {
            hash[first->next->key] = newnode;
        }

        first->next = newnode;
        hash[key] = first;
        if(newnode->next == NULL)
        {
            last = newnode;
        }
    }
};

code

class Node {
public:
    int key;
    int val;
    Node* next;
    Node(int key, int val)
    {
        this->key = key;
        this->val = val;
        this->next = NULL;
    }
};

class LRUCache{
public:
    // @param capacity, an integer

    map<int, Node*> hash;
    Node* first;
    Node* last;
    int capacity;

    LRUCache(int capacity) {
        // write your code here
        first = new Node(0, 0);
        last = NULL;
        this->capacity = capacity;
    }

    void moveToTail(int key)
    {
        Node* prev = hash[key];
        if(prev == first)
        {
            return ;
        }

        Node* cur = prev->next;
        if(cur == last)
        {
            last = prev;
        }
        prev->next = prev->next->next;
        if(prev->next != NULL)
        {
            hash[prev->next->key] = prev;
        }

        cur->next = first->next;
        hash[first->next->key] = cur;

        first->next = cur;
        hash[cur->key] = first;

    }

    // @return an integer
    int get(int key) {
        // write your code here
        if(hash.find(key) == hash.end())
        {
            return -1;
        }
        else
        {
            moveToTail(key);
            return hash[key]->next->val;
        }

    }

    // @param key, an integer
    // @param value, an integer
    // @return nothing
    void set(int key, int value) {
        // write your code here
        if(hash.find(key) != hash.end())
        {
            moveToTail(key);
            hash[key]->next->val = value;
            return ;
        }

        Node* newnode = new Node(key, value);
        if(hash.size() == capacity)
        {
            Node* prev = hash[last->key];
            hash.erase(last->key);
            prev->next = NULL;
            last = prev;
            capacity -= 1;
        }

        newnode->next = first->next;
        if(first->next != NULL)
        {
            hash[first->next->key] = newnode;
        }

        first->next = newnode;
        hash[key] = first;

        if(newnode->next == NULL)
        {
            last = newnode;
        }

        capacity += 1;

    }
};