Using C++:

Create a derived class from the List class. This version of the class is to investigate leaving blank spots in the array can reduce the number of moves when inserting.

Modify the AddItem method to insert an item halfway between any two items in the array where it belongs. It should only move items in the array if the inserting item sits between two items that are in contiguous locations.

Modify the RemoveItem method so that it will not move any items in the array.

Create a test program to test the performance of the 2 classes.

This should instantiate each of the two classes.

This should insert 30 randomly generated items into the array (using integers as the list data type might be the easiest way to do this).

This should remove 25 items from the array.

Individual insert and removal from steps b and c should be randomly selected rather than done sequentially.

Every comparison and move operation in the AddItem and RemoveItem methods should be counted (except checks to see if an array location holds a nullptr). The total count at the end of the run should be displayed to measure efficiency of the class.

Every insert/remove operation should be identically performed against all 2 of the class instances.

List Class Code Below:

#include using namespace std;

class Exception {//exception class for throwing error public: Exception(const string& msg) : msg_(msg) {} ~Exception() {}

string getMessage() const {return(msg_);} private: string msg_; };

// We can use this for any data type that supports template class OrderedList{//template class public: T *array;//create array of size 20 int size; public: OrderedList(int size){//constructor array = new T[size]; this->size=size; } //The AddItem method should start at the front of the array when searching //for a place to insert a new item. void AddItem(T data) { try{ if(IsFull()){//if array is full throw error throw(Exception("Error :Array is full")); } }catch(Exception& e) { cout << e.getMessage() << endl; } for(int i=0;i if(IsEmpty(i)){ array[i]=data; cout<<"Data inserted"; break; } } } //The RemoveItem method should ensure that the items in the array are still //in order and there are no empty spots between items.

void RemoveItem (int data) { bool item_exists=false; for(int i=0;i if(array[i]==data){ item_exists=true; array[i]=NULL;//remove item of specific index } } try{ if(!item_exists){ throw(Exception("Error :Item does not exists")); } cout<<"Data removed"; T *arr=array;//create temporary array to store pointer array data int j=0; //insert data into array again in order without any null in betweeb for(int i=0;i if(arr[i]!=NULL){ array[j]=arr[i]; j++; } array[i]=NULL; } }catch(Exception& e) { cout << e.getMessage() << endl; } } bool IsEmpty(int index){ return array[index]==NULL;//if pointer array index is empty return true else false } bool IsFull () { bool full; for(int i=0;i if(!IsEmpty(i)){//if array index is not empty full=true;//set true } else{ full=false;//else set false } } return full; } void MakeEmpty() { for(int i=0;i array[i]=NULL;//set array to null } } void print() { cout<<" Array contents are index\tdata "; for (int i = 0; i < size; i++) cout< cout< } }; template class List2 : public List { void AddItem2(T data) { for(int i=0;i if(IsEmpty(i)){ array[i]!=data; cout<<"Data inserted"; break; } } } };

int main() { int SIZE=20;//decloare size to 20 int data;//set datatype of data to integer OrderedList o(SIZE); int ch; do{//loop until user does not input 4 cout<<"1.AddItem 2.RemoveItem 3.MakeEmpty 4.exit "; cin>>ch; switch(ch){ case 1: cout<<"Enter data to insert "; cin>>data;//input data of declared datatype o.AddItem(data); o.print(); break; case 2: cout<<"Enter data to remove "; cin>>data; o.RemoveItem(data); o.print(); break; case 3: o.MakeEmpty(); o.print(); break; } }while(ch!=4); return 0; }