146 LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

class doubleListNode
{
public:
    doubleListNode(int key_k, int value)
    {
        key = key_k;
        val = value;
        left = NULL;
        right = NULL;
    }
    doubleListNode *left;
    doubleListNode *right;
    int key;
    int val;
};
class LRUCache{
public:
    LRUCache(int capacity) {
        cache_capacity = capacity;
        size = 0;
        dummy = new doubleListNode(0,0);
        tail = dummy;
        
    }
    ~LRUCache()
    {
        delete dummy;
    }
    void insertNewNodeToHead(int key, int val);
    void removeToHead(doubleListNode * node);
    int get(int key) {
        if (mp.find(key)!=mp.end())
        {
            int res = mp[key]->val;
            removeToHead(mp[key]);
            return res;
        }
        else
            return -1;
    }
    void set(int key, int value) {
        if (mp.find(key)!=mp.end())
        {
            mp[key]->val = value;
            removeToHead(mp[key]);
        }
        else
        {
            if (size<cache_capacity)
            {
                insertNewNodeToHead(key,value);
                ++size;
            }
            else
            {
                if (tail!=dummy)
                {
                    mp.erase(tail->key);
                    tail = tail->left;
                    delete tail->right;
                }
                insertNewNodeToHead(key,value);
            }
        }
    }
    int cache_capacity;
    int size;
    unordered_map<int, doubleListNode*> mp;
    doubleListNode *dummy;
    doubleListNode *tail;
};
void LRUCache::insertNewNodeToHead(int key, int val)
{
    doubleListNode *newNode = new doubleListNode(key,val);
    newNode->right = dummy->right;
    if (dummy->right)
        dummy->right->left = newNode;
    dummy->right = newNode;
    newNode->left = dummy;
    if (tail == dummy)
        tail = dummy->right;
    mp[key]=newNode;
}
void LRUCache::removeToHead(doubleListNode * node)
{
    if (node)
    {
        if (node == tail)
        {
            tail = tail->left;
            tail->right = NULL;
        }
        else
        {
            node->left->right = node->right;
            node->right->left = node->left;
        }

        node->right = dummy->right;
        if (dummy->right)
            dummy->right->left = node;
        node->left = dummy;
        dummy->right = node;
        if (tail==dummy)
            tail = dummy->right;
    }
}