USE C++ ONLY

Implement a Doubly Linked-list of integers that maintains a head and a tail. Implement the following functions in your Doubly Linked-list.

insertHead(value) : Inserts the value at the beginning of the linked-list. Expected Complexity O(1).

insertTail(value) : Inserts the value at the end of the linked-list. Expected Complexity O(1).

insertMid(value) : Inserts the value at the middle of the linked-list. Expected Complexity O(n).

print() : Prints the linked-list starting from head. Expected Complexity O(n).

merge(LinkedList a) : This function takes as input a LinkedList and merges the LinkedList a at the back of the current linked-list. Expected Complexity O(1).

Your implementation for this problem should look like this. You may write any extra functions that you need.

class Node{

int value;

Node* nxt;

Node* prv;

};

class LinkedList{

Node* head;

Node* tail;

LinkedList()

{

//Write your code

}

void insertHead(int value)

{

//Write your code

}

void insertTail(int value)

{

//Write your code

}

void insertMid(int value)

{

//Write your code

}

void print()

{

//Write your code

}

void Merge(LinkedList a)

{

//Merge a at the back of this linked-list

//Write your code

}

};

int main()

{

LinkedList a;

LinkedList b;

a.insertHead(1);

a.insertTail(5);

a.insertMid(3);

a.insertHead(0);

a.insertTail(10);

a.print(); // prints 0 1 3 5 10

b.insertHead(10);

b.insertTail(50);

b.insertMid(30);

b.insertHead(9);

b.insertTail(100);

b.print(); // prints 9 10 30 50 100

a.Merge(b);

a.print(); // prints 0 1 3 5 10 9 10 30 50 100

b.print(); // prints 9 10 30 50 100

}