DATA STRUCTURES & ALGORITHM

??

Submission Instructions: Submit separate C++ files for the code as follows (so, a total of FOUR.cpp files as mentioned below): Question 1-(i: 32 pts) The entire .cpp file for the singly linked list-based implementation of the List ADT incorporating the code for the delete DuplicateElements() function. Question 2-[i: 27 pts) The entire .cpp file for the singly linked list-based implementation of the List ADT incorporating the code for the Swap Min MaxData(List) function Question 3-(i: 12 pts) The entire.cpp file for the dynamic array-based List ADT implementation with the main function extended to measure the average time per insertion at the beginning of the list. Question 3-(ii: 12 pts) The entire .cpp file for the singly linked list-based List ADT implementation with the main function extended to measure the average time per insertion at the beginning of the list. Submit a single PDF file that includes your screenshots and analysis for all the three questions put together as mentioned below (clearly label your screenshots/responses for each question): Question 1-ii: 3 pts) Screenshot of the execution of the implementation (using the testing procedure described for Question 1) submitted as a jpeg or in some other image file format. Question 2-(ii: 3 pts) Screenshot of the execution of the implementation (using the testing procedure described for Question 2) submitted as a jpeg or in some other image file format. Question 3-(iii: 4 pts) Present your results in the form of a table, wherein you compare the average time per insertion for the dynamic array and singly linked list-based implementations of the List ADT with respect to insertions at the beginning of the list as well as at the end of the list. Question 3-(iv: 3 pts) Include screenshots of your outputs for each case. Question 3-(v: 4 pts) Interpret your results and validate/conclude whether the results reflect our hypothesis (that the dynamic array based implementation will incur lower times for insertions at the end of the list and the singly linked list based implementation will incur lower times for insertions at the beginning of the list). Question 2 - 30 pts) In this question, you will write a code/function to swap the minimum and maximum data values of the nodes in a singly linked list-based implementation of the List ADT. You are given the code for the singly linked list-based implementation of the List ADT along with a main function that creates an IntegerList (an object of class List) and fills it up with random integers in the range [1...max Value]. The initial contents of the IntegerList are printed. The main function then calls the SwapMinMaxData(List) function and passes the Integer List as the argument. In the SwapMinMaxData(List list) function, the parameter list is scanned once from the head node to the last data node and as part of this process, the addresses of the nodes with the minimum and maximum data values are identified. Using the addresses of the two nodes, the data (i.e., the minimum and maximum values) of these two nodes are then swapped. The final contents of the Integer List are printed after the call to the SwapMinMaxData(List) function. The SwapMinMaxData(List) function should be implemented in O(n) time, where n is the number of elements in the list. You would test run your code with max Value as 50 and listSize as 10 passed as inputs. Take a screenshot of the output. A sample output is shown below (7 and 46 are respectively the minimum and maximum data values): Enter the maximum value in the list: 50 Enter the size for the list: 10 Before min-max swap 13 11 9 30 23 7 46 12 43 7 After min-max swap 13 11 9 30 23 46 7 12 43 7 #include #include #include #include #include #include using namespace std; // implementing the dynamic List ADT using Linked List class Node{ private: int data; Node* nextNodePtr; public: Node() { } void setData(int d) { data = d; } int getData(){ return data; } void setNextNodePtr (Node* nodePtr) { nextNodePtr = nodePtr; } Node* getNextNodePtr() { return nextNodePtr; } }; class List{ private: Node *headPtr; public: List() { headPtr = new Node(); headPtr->setNextNodePtr(0); } Node* getHeadPtr() { return headPtr; } bool isEmpty() { if (headPtr->getNextNodePtr() == 0) return true; return false; } void insert(int data) { Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; while (currentNodePtr != 0){ prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); } Node* newNodePtr = new Node(); newNodePtr->setData (data); newNodePtr->setNextNodePtr(0); prevNodePtr->setNextNodePtr(newNodeptr); } void insert Sortedorder(int data) { // Implement the function // the data should get inserted at an appropriate index/location in the list 1/ such that the list stays sorted after the insertion } void insertAtIndex(int insert Index, int data) { Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; int index = 0; while (currentNodePtr != 0 ) { if (index == insertIndex) break; prevNodePtr currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); index++; } Node* newNodePtr = new Node(); newNodePtr->setData(data); newNodePtr->setNextNodePtr (currentNodePtr); prevNodePtr->setNextNodePtr(newNodePtr); } int read (int readIndex) { Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; int index = 0; while (currentNodePtr != 0){ if (index == readIndex) return currentNodePtr->getData(); prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); index++; } return -1; // an invalid value indicating // index is out of range } void modifyElement(int modifyIndex, int data) { Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; int index = 0; while (currentNodePtr != 0){ if (index == modifyIndex) { currentNodePtr->setData(data); return; } prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); currentNodePtr = currentNodePtr->getNextNodePtr(); index++; } } void deleteElement(int deleteIndex) { Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; Node* nextNodePtr = headPtr; int index = 0; while (currentNodePtr != 0){ if (index == deleteIndex) { nextNodePtr = currentNodePtr->getNextNodePtr(); break; } prevNodePtr = currentNodePtr; currentNo EN Ptr->getNextNodePtr(); index++; } prevNodePtr->setNextNodePtr (nextNodePtr); } void IterativePrint() { Node* currentNodePtr = headPtr->getNextNodePtr(); while (currentNodePtr != 0){ cout getData() getNextNodePtr(); } cout > maxValue; int listSize; cout > list Size; 1/srand(time(NULL)); srand( static_cast(time(nullptr))); using namespace std::chrono; List IntegerList; for (int i = 0; i