W Question 3 - 35 pts) We saw in class that a dynamic array-based implementation of the List ADT is preferable when the insert operations to the List is repeatedly done at the end of the List, whereas the singly linked list-based implementation is preferable when the insert operations are done close to the head node (i.e., the new node is inserted as the node next to the head node). In this question, we will quantitatively estimate this tradeoff and determine the average time per insertion at the beginning of the list vs. at the end of the list with both the dynamic array and singly linked list-based implementations. You are given a singly linked list-based implementation as well as a dynamic array-based implementation of the List ADT along with a main function that creates an Integerlist_InsertArEnd object of class List and fills it up with random integers generated in the range of... maxValue). The random integers are inserted at the end of the list in each case The average time per insertion in each case is printed as well. Your task in this question is to come up with a code to insert at the beginning of the list object Integerlist InsertAtBeginning) in the main functions for both the singly linked list and dynamic array- based implementations and measure the average time per insertion at the beginning of the lists for both the implementations, You will run your code for both the singly linked list and dynamic array-based implementations for the following values of listSize: 10000, 100000 and 1000000; maxValue is 50000 in each case. Present your results in the form of a table, wherein you compare the average time per insertion for the dynamic arruy 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. 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). #include #include #include #include #include using namespace std; // implementing the dynamic List ADT using array il operations to be implemented: read, Modify, delete, isEmpty, insert, countElements class List{ private: int *array; int maxSize; // useful to decide if resizing (doubling the array size) is needed int endOfArray; public: List() List(int size) { array = new int[size]; maxSize = size; endOfArray = -1; } void deleteList(){ delete[] array; } void SetUp(int size) { maxSize = size; maxSize = size; array = new int[maxSize); endOfArray = -1; } bool isEmpty(){ if (endOfArray == -1) return true; return false; } void resize(int s) { int tempArray = array; array = new int[s]; for (int index = 0; index endOfArray+1) insertindex = endOfArray+1; if (endOfArray == maxSize-1) resize(2*maxSize); for (int index = endOfArray; index >= insertIndex; index--) array[index+1] = array[index]; array[insertindex] = data; endOfArray++; } int read(int index){ return array[index); } void modifyElement(int index, int data) { array[index] = data; } void deleteElement(int deleteIndex){ || shift elements one cell to the left starting from deleteIndex+1 to endOfArray-1 // i.e., move element at deletelndex + 1 to deletelndex and so on for (int index = deleteIndex; index > maxValue; int listSize; cout > listSize; // srand(time(NULL)); srand( static_cast(time(nullptr))); using namespace std::chrono; List IntegerList_InsertAtEnd(1); high_resolution_clock::time_point t1 = high_resolution_clock::now(); for (int i = 0; i insertionTime_AtEnd_nano = t2 - t1; double insertionTime_AtEnd = insertionTime_AtEnd_nano.count(); | Write your code to determine the average time per insertion at the beginning of the list || and print it out as insertionTime_AtBeginning/listSize as mentioned below cout #include #include #include #include using namespace std; // implementing the dynamic List ADT using array il operations to be implemented: read, Modify, delete, isEmpty, insert, countElements class List{ private: int *array; int maxSize; // useful to decide if resizing (doubling the array size) is needed int endOfArray; public: List() List(int size) { array = new int[size]; maxSize = size; endOfArray = -1; } void deleteList(){ delete[] array; } void SetUp(int size) { maxSize = size; maxSize = size; array = new int[maxSize); endOfArray = -1; } bool isEmpty(){ if (endOfArray == -1) return true; return false; } void resize(int s) { int tempArray = array; array = new int[s]; for (int index = 0; index endOfArray+1) insertindex = endOfArray+1; if (endOfArray == maxSize-1) resize(2*maxSize); for (int index = endOfArray; index >= insertIndex; index--) array[index+1] = array[index]; array[insertindex] = data; endOfArray++; } int read(int index){ return array[index); } void modifyElement(int index, int data) { array[index] = data; } void deleteElement(int deleteIndex){ || shift elements one cell to the left starting from deleteIndex+1 to endOfArray-1 // i.e., move element at deletelndex + 1 to deletelndex and so on for (int index = deleteIndex; index > maxValue; int listSize; cout > listSize; // srand(time(NULL)); srand( static_cast(time(nullptr))); using namespace std::chrono; List IntegerList_InsertAtEnd(1); high_resolution_clock::time_point t1 = high_resolution_clock::now(); for (int i = 0; i insertionTime_AtEnd_nano = t2 - t1; double insertionTime_AtEnd = insertionTime_AtEnd_nano.count(); | Write your code to determine the average time per insertion at the beginning of the list || and print it out as insertionTime_AtBeginning/listSize as mentioned below cout