Linked List Construction

• Space : O(n)

using namespace std;

class Node {
public:
  int value;
  Node *prev;
  Node *next;

  Node(int value);
};

// Feel free to add new properties and methods to the class.
class DoublyLinkedList {
public:
    Node *head;
    Node *tail;
    unordered_map<int, unordered_set<Node*>> mp;

    DoublyLinkedList() {
        head = nullptr;
        tail = nullptr;
    }

    void setHead(Node *node) { //O(1)
        if(containsNodeWithValue(node->value)) {
            remove(node);
        }
        mp[node->value].insert(node);
        if(head) {
            head->prev = node;
            node->next = head;
        } else tail = node;
        head = node;
        node->prev = nullptr;
    }

    void setTail(Node *node) { //O(1)
        if(containsNodeWithValue(node->value)) {
            remove(node);
        }
        mp[node->value].insert(node);
        if(tail) {
            tail->next = node;
            node->prev = tail;
        } else head = node;
        tail = node;
        tail->next = nullptr;
    }

    void insertBefore(Node *node, Node *nodeToInsert) { // O(1)
        if(containsNodeWithValue(nodeToInsert->value)) {
            remove(nodeToInsert);
        }
        if(node == head)
            setHead(nodeToInsert);
        else {
            mp[nodeToInsert->value].insert(nodeToInsert);
            nodeToInsert->prev = node->prev;
            nodeToInsert->next = node;
            node->prev->next = nodeToInsert;
            node->prev = nodeToInsert;
        }
    }

    void insertAfter(Node *node, Node *nodeToInsert) { // O(1)
        if(containsNodeWithValue(nodeToInsert->value)) {
            remove(nodeToInsert);
        }
        if(node == tail)
            setTail(nodeToInsert);
        else {
            mp[nodeToInsert->value].insert(nodeToInsert);
            nodeToInsert->next = node->next;
            nodeToInsert->prev = node;
            node->next->prev = nodeToInsert;
            node->next = nodeToInsert;
        }
    }

    void insertAtPosition(int position, Node *nodeToInsert) { // O(position)
        Node* tmp = head;
        while(--position)
            tmp = tmp->next;
        insertBefore(tmp, nodeToInsert);
    }

    void removeNodesWithValue(int value) { //O(number of value nodes)
        if(containsNodeWithValue(value)) {
            while(mp[value].size()) {
                remove(*begin(mp[value]));
            }
        }
    }

    void remove(Node *node) { //O(1)
        mp[node->value].erase(node);
        if(node->prev)
            node->prev->next = node->next;
        if(node->next)
            node->next->prev = node->prev;
        if(node == head)
            head = head->next;
        if(node == tail)
            tail = tail->prev;
        node->prev = nullptr;
        node->next = nullptr;
    }

    bool containsNodeWithValue(int value) { //O(1)
        return mp[value].size();
    }
};