Question
In C++
Part - 2: Implement a Double linked List ADT to store a collection of integers.
(You are allowed to extend the demo code posted on GitHub for this homework. link: https://github.com/Premdeep/CSC340-Summer-2017/tree/master/LinkedList ).
Make sure to provide an interactive user interface to test these new functions in the main() for grader . Your ADT will include the following member functions:
--- a default constructor
--- the "big-3": destructor, copy constructor and overloaded assignment operator
1. a member function pushFront(data) that inserts a node with data at the front of the list
2. a member function pushBack(data) that appends a node with data at the back of the list
3. a member function popFront() that removes first node of the list.
4. a member function popBack() that removes last node of the list.
5. a member function insert(index, val) that inserts a new node with value "val" at a specific position mentioned by the index argument.
6. a member function deleteDuplicates(val) that deletes a node with that number and all its copies from the list, where these copies can be located anywhere in the list.
7. a member function mtoLastElement(M) that returns Mth to the last element of a list such that when M = 0, the last element of the list is returned.
8. a member function size() that returns the size of the list.
9. an overloaded put operator (<<) to print out all the data items stored in a linked list. Note that you are recommended to overload this operator as a friend function of the LinkedList class.
10. a member function reverseList() that reverses a linked list without recreating a temporary copy of this linked list. In other words, your function CAN NOT use the 'new' operator. Here is an example, if a list contains the following data items, 3 -> 5 -> 1 -> 7; this reverse() function will change the list to 7 -> 1 -> 5 -> 3.
Explanation / Answer
#include #include #include using namespace std; /* List Node: */ template class MyNode { private: T data; public: MyNode* next; MyNode* previous; MyNode(T data); T getData(); string toString(); ~MyNode(); }; template MyNode::MyNode(T data) { this->data = data; } template T MyNode::getData() { return this->data; } template string MyNode::toString() { stringstream s; s head = NULL; this->tail = NULL; this->list_size = 0; } template T* MyList::getHead() { return this->head; } template T* MyList::getTail() { return this->tail; } template int MyList::size(bool update) { if (!update) { return this->list_size; } int size = 0; T* temp = this->head; while (temp) { size++; temp = temp->next; } this->list_size = size; return this->list_size; } template void MyList::addNodeAsTail(T* new_node) { new_node->next = NULL; new_node->previous = NULL; if (this->head == NULL) { this->head = new_node; this->tail = this->head; this->list_size = this->list_size + 1; } else { this->tail->next = new_node; new_node->previous = this->tail; this->tail = new_node; this->list_size = this->list_size + 1; } } template void MyList::addNodeAsHead(T* new_node) { new_node->next = NULL; new_node->previous = NULL; if (this->head == NULL) { this->head = new_node; this->tail = this->head; this->list_size = this->list_size + 1; } else { this->head->previous = new_node; new_node->next = this->head; this->head = new_node; this->list_size = this->list_size + 1; } } template void MyList::push(T* new_node) { this->addNodeAsHead(new_node); } template T* MyList::pop() { T* temp = this->head; this->head = this->head->next; this->head->previous = NULL; this->list_size = this->list_size - 1; return temp; } template T* MyList::peek() { return this->head; } template void MyList::enqueue(T* new_node) { this->addNodeAsTail(new_node); } template T* MyList::dequeue() { return this->pop(); } template T* MyList::get(int index) { if (index == 0) { return this->head; } else if (index == this->list_size - 1) { return this->tail; } else if (index < 0 || index >= this->list_size) { return NULL; } if (index list_size / 2) { T* temp = this->head; int i = 0; while (temp) { if (i == index) { return temp; } i++; temp = temp->next; } } else { T* temp = this->tail; int i = this->list_size - 1; while (temp) { if (i == index) { return temp; } i--; temp = temp->previous; } } return NULL; } template void MyList::printList() { cout head; while(temp) { cout next; } cout list_size - 1; this->head = next; } } void stackAsString() { MyList stack; int i = 0; cout