class LRUCache: public Cache{ public: LRUCache(int c){cp = c; tail = nullptr; head = nullptr;} virtual void set(int key, int value) override{ map::iterator it = mp.find(key); Node* node = nullptr; if(it == mp.end()){ node =new Node(nullptr, head, key, value); if(mp.size() >= cp){ tail = tail->prev; tail->next->prev = nullptr; mp.erase(tail->next->key); delete tail->next; tail->next = nullptr; }else{ } if(tail == nullptr) tail = node; if(head) head->prev = node; head = node; mp[key] = node; }else{ it->second->value = value; node = it->second; if(node != head){ if(head->next == tail){ /* replace the order for head and tail*/ head = head->next; tail = tail->prev; tail->next = nullptr; head->prev = nullptr; head->next = tail; tail->prev = head; }else{ if(node == tail){ /* put the tail as a head*/ tail = tail->prev; tail->next = nullptr; node->prev = nullptr; node->next = head; head->prev = node; head = node; }else{ /* put the middle node as a head*/ node->prev->next = node->next; node->next->prev = node->prev; node->next = head; node->prev = nullptr; head->prev = node; head = node; } } }else{ /* no change in order*/ } } }

virtual int get(int key)override{
    int value = -1;
    map<int,Node*>::iterator it = mp.find(key);
    if(it != mp.end()){
        value = it->second->value;
        Node* node = it->second;
        if(node != head){
            if(head->next == tail){
                /* replace the order for head and tail*/
                head = head->next;
                tail =  tail->prev;
                tail->next = nullptr;
                head->prev = nullptr;
                head->next = tail;
                tail->prev = head;
            }else{
                if(node == tail){
                    /* put the tail as a head*/
                    tail = tail->prev;
                    tail->next = nullptr;
                    node->prev = nullptr;
                    node->next = head;
                    head->prev = node;
                    head = node;
                }else{
                   /* put the middle node as a head*/
                   node->prev->next = node->next;
                   node->next->prev = node->prev;
                   node->next = head;
                   node->prev = nullptr; 
                   head->prev = node;
                   head = node;
                }
            }
        }else{
            /* no change in order*/
        }
    }
    return value;
}

};

My solution - I'm not a professional c++ dev but this was fun

class LRUCache : public Cache 
{
    private:
        int capacity;
        void move_node_to_head(Node* node);
        void remove_node_from_tail(Node* node);
    public:
        LRUCache(int capacity);
        int get(int key);
        void set(int key, int value);
};


LRUCache::LRUCache(int capacity)
{
    this->tail = nullptr;
    this->head = nullptr;
    this->capacity = capacity; 
}


int LRUCache::get(int key)
{
    if (mp[key] == nullptr) {
        return -1;
    }
    int cache_entry = mp[key]->value;
    move_node_to_head(mp[key]);
    return cache_entry;
}

void LRUCache::move_node_to_head(Node* new_head_node)
{
    // In case we are getting or setting a value at the head
    if (head == new_head_node) {
        return;
    }

    // IN case its the very first insert, we set head = tail
    if (tail == nullptr) {
        tail = new_head_node;
    }
    if (head == nullptr) {
        head = new_head_node;
        mp[new_head_node->key] = new_head_node;
        return;
    }

    if (tail->prev == nullptr) {
        tail->prev = head;
    }

    /**
     *  N1 -> next | prv <- N2 -> next 
     * We take the currrent head and move it to the next position, so the new head node next, will point to the current head node previous node
     */
    new_head_node->next = head;   
    new_head_node->prev = nullptr; // A head doesn't have any previous node
    head = new_head_node;

  
    mp[new_head_node->key] = new_head_node;
}


/**
 * Need to remove the tail node and shifting the nodes to the right
 */
void LRUCache::remove_node_from_tail(Node* node)
{
    if (tail == nullptr) {
        return;
    }
    Node* old_tail = tail;
    if (tail->prev != nullptr) {
        tail->prev->next = nullptr; // remove the tail also from the node before
    }
   
    mp.erase(tail->key);
    delete old_tail;
}


void LRUCache::set(int key, int value)
{
    Node* new_node = new Node(key, value);

    // first entry in the list

    if (mp[key] != nullptr) {
        // the Node is existing, so we update the value move to the head
        Node* node = mp[key];
        node->value = value;
        move_node_to_head(new_node);
    } else {
         // Cache is full
        if (mp.size() > this->capacity) {
            // remove node from tail
            remove_node_from_tail(new_node);
        }
        move_node_to_head(new_node);
    } 
}

In c++14, compiler warns about the initialising order - prev is initialised before next... and editor doesn't allow to change the code to fix that.

struct Node{ Node* next; Node* prev; int value; int key; Node(Node* p, Node* n, int k, int val):prev(p),next(n),key(k),value(val){}; Node(int k, int val):prev(NULL),next(NULL),key(k),value(val){}; };

include

include

include

include

include

include

include

using namespace std;

struct Node { Node* next; Node* prev; int value; int key; Node(Node* p, Node* n, int k, int val) :prev(p), next(n), key(k), value(val) {}; Node(int k, int val) :prev(NULL), next(NULL), key(k), value(val) {}; };

class Cache {

protected: map mp; //map the key to the node in the linked list int cp; //capacity Node* tail; // double linked list tail pointer Node* head; // double linked list head pointer Cache(int capacity) : cp(capacity) { tail = nullptr; head = nullptr; } public: virtual void set(int, int) = 0; //set function virtual int get(int) = 0; //get function virtual ~Cache() { Node* p; while (head) { p = head; head = head->next; delete p; } }

};

class LRUCache final : public Cache { public: LRUCache(int capacity) : Cache(capacity) { }

void set(int key, int value) override {
    auto result = mp.find(key);
    if (result != mp.end()) {
        Node* p = result->second;
        p->value = value;
        moveToFrontNode(p);
    } else {
        Node* p = new Node(key, value);
        AddToFrontNode(p);
        mp[key] = p;
        if (mp.size() > cp) {
            mp.erase(tail->key);
            removeLastNode();
        }
    }
}

int get(int key) override {
    auto result = mp.find(key);
    if (result != mp.end()) {
        Node* p = result->second;
        moveToFrontNode(p);
        return p->value;
    }
    return -1;
}

private: void moveToFrontNode(Node* p) { if (p == head) return; if (p == tail) { tail = p->prev; tail->next = nullptr; } else { p->prev->next = p->next; p->next->prev = p->prev; } p->prev = nullptr; p->next = head; head = p; p->next->prev = p; }

void AddToFrontNode(Node* p) {
    p->prev = nullptr;
    p->next = head;
    head = p;
    if (p->next) {
        p->next->prev = p;
    }
    if (!tail) {
        tail = p;
    }
}

void removeLastNode() {
    if (tail) {
        Node* p = tail;
        tail = tail->prev;
        if (tail) {
            tail->next = nullptr;
        }
        else {
            head = nullptr;
        }
        delete p;
    }
}

};

int main() { int n, capacity, i; cin >> n >> capacity; LRUCache l(capacity); for (i = 0; i < n; i++) { string command; cin >> command; if (command == "get") { int key; cin >> key; cout << l.get(key) << endl; } else if (command == "set") { int key, value; cin >> key >> value; l.set(key, value); } } return 0; }