DATA STRUCTURES AND ALGORITHM

ANNSWER ALL

Note: 1) You will have to use the student version code assigned for each question and develop/extend the code to answer the question. If you use any other code to answer the question, you will get a ZERO for the question. 2) You should not use built-in C++ data structures (other than the ones, if any, used in the student version code assigned to answer a question. You will get a ZERO for the question if you use any such built-in data structures. 3) If the instructor notices that one or more students are involved in copying with regards to even a single question, all the concerned students will get a ZERO for the entire EXAM. 4) Submission instructions should be strictly followed, as mentioned in the last page (Page 3) of this exam. 5) E-mail based submissions after the Feb. 23rd (11.59 PM) deadline will NOT be accepted. Question 1 - 35 pts) Design and implement an algorithm to delete all the duplicate elements in a List ADT implemented as a singly linked list. You are given the code for the singly linked list-based implementation of a List ADT. The main function in this program is already setup to generate random integers and fill up the contents of the list (IntegerList). The delete DuplicateElements() function is called on the IntegerList to delete the duplicate occurrences of all the elements in the list. Your task is to implement the delete DuplicateElements() function in the singly linked list-based implementation of the List ADT. Your algorithm/implementation should run in time less than or equal to r comparisons (which is the basic operation), where n is the number of elements in the list before the deletions. The main function is written in such a way that it will print the contents of the list before and after the deletions. You would test your code by entering 15 as the list size and 5 as the maximum value for any element. The list will be then filled with random integers in the range [1..5). As there are going to be 15 integers in the list, it will be definitely the case that there will be more than one occurrence for one or more integers in the list. A sample output is shown below: Enter the maximum value in the list: 5 Enter the size for the list: 15 Before deletion: 5 3 2 5 3 2 2 11554315 After deletion: 53214 #include #include #include #include #include #include schrono> using namespace std; Il implementing the dynamic List ADT using Linked List class Nodel private: int data; NodenextNodePt; public: Node00 void setData(int d) { data = d; } int getData() return data; } void setNextNodePtr(Node nodePtr){ nextNodePtr = nodePtr; } Node* getNextNodePro return nextNodePt; } }; class List private: Node "headPt; public: List headPtr = new Node(); headPtr->setNextNodePtr(0): } Node* getHeadPtr return houden 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 != 0X prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr- >getNextNodePtr(); } Node newNodePtr = new Node(); newNodePtr->setData(data); newNodePtr->setNextNodePtr(0); prevNodePtr->setNextNodePtr(newNodePtr); } void insertAtIndex(int insertindex, int data) Node currentNodePtr = headPtr- >getNextNodePtr(); Node prevNodePtr = headPtr; int index = 0; while (currentNodePtr != 0){ if (index == insertindex) break; prevNodePtr = currentNodePtr; currentNodepu currentNodePtr- 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- >getNextNodePt(): index++; } return -1; // an invalid value indicating // index is out of range } void modify Element(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(); index++; } } void deleteElement(int deleteIndex){ Node currentNodePtr = headPtr- >getNextNodePtr(); Node prevNodePtr = headPtr; Node. nextNodePtr = headPtr; int index = 0; while (currentNodePtr != OX if (index == deleteIndex){ nextNodePtr = currentNodePtr- >getNextNodePtr(); break; ) prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr- >getNextNodePtr(); index++; } prevNodePtr->setNextNodePtr(nextNodePtr); } void delete DuplicateElements void IterativePrint Node* currentNodePtr = headPtr- >getNextNodePtr(; while (currentNodePtr != OX cout getData() getNextNodePtr(); } cout > maxValue; int listSize; cout > listSize; srand(time(NULL)); srand( static_cast unsigned int>(time(nullptr))); using namespace std::chrono; List Integerlist: l/high_resolution_clock:time_point t1 = high_resolution_clock::now(); for (int i = 0; i > maxValue; int listSize; cout > listSize; I/srand(time(NULL)); srand( static_cast unsigned int>(time(nullptr))): using namespace std::chrono; List IntegerList; l/high_resolution_clock::time_point t1 = high_resolution_clock::now(); for (int i = 0; i