In the lecture we have seen two different implementations of List: array-based and singly link-based. For this assignment, your job is to investigate the complexity and the actual running time of these two different implementation methods of List. You are provided with a start-up code for array list (arrayList.h) and singly link list (SLinkList.h). Your task is as follows:
1.Complete the missing parts for each implementation method.
2.Write a test program:
a.Generate 500 random integers and populate your list
b.Once you populate your list, measure the system running time of each function in the list below for the three possible implementation methods.
c.For each function, record the running time in a table, similar to the one provided below. (To get accurate results, make sure you are not running multiple application on your machine when you are running the code). Comment on the obtained data.
3.Repeat step 2 for 1000, 2000, 4000, 8000, and 16000 random integers.
Here is the description of the functions that you need to measure running time:
a-insertFirst(item e): Inserts an item e at the beginning of the list.
b-insertLast(item e): Inserts an item e at the end of the list.
c-removeFirst(): delete the first item of the list.
d-removeLast():delete the last item of the list.
e-removeSecondLast(): delete the second to last element from the list.
f-insertAtPosition(int index, item e): add an item e at the indexth position the list. If the list is implement using an array, then the new added element will be inserted at list[index]. For the single and double link list, you can assume that the first node in the list has index 0, the second node has index 1, and so on. When you are testing your code, you can just generate a random number between 0 and the size of the list, and use that number as the index to insert your new item at.
g-DestroyList(): destroy the whole list.
Table 1: Time analysis for function insertFirst(item e) see image.
arrayList.h
class arrayList
{
public:
arrayList(); //default constructor, Initializes the list to an empty state.
void insertFirst(int newItem); //Function to insert newItem in the list.
void insertLast(int newItem); //Function to return newItem at the end of the list.
void destroyList(); //destroys the entire list
void insertAt(int loc, const int newItem); //inserts newItem at a given location (list indexing starts with 0)
void removeFirst(); //removes the first element from the list
void removeLast(); //removes the last element from the list
void removeSecondLast(); // removes the second last element from the list
protected:
int *list; //array to hold the list elements
int length; //to store the length of the list
int maxSize; //to store the maximum size of the list
};
void arrayList::arrayList()
{
//complete the constructor (intialize the array to empty state)
}
void arrayList::insertFirst(const int& newItem)
{
//complete the code
}
void arrayList::insertLast(const int& insertItem)
{
if(length >= maxSize) //the list is full
cerr<<"Cannot insert in a full list."< else
{
list[length] = insertItem; //insert the item at the end
length++; //increment length
}
}
void arrayList::destroyList()
{
//complete the code
}
void arrayList::insertAt (int loc, const int& newItem)
{
if(loc < 0 || loc >= maxSize)
cerr<<"The position of the item to be inserted "
<<"is out of range."< else
if (length >= maxSize) //list is full
cerr<<"Cannot insert in a full list"< else
{
for(int i = length; i > loc; i--)
list[i] = list[i - 1]; //move the elements down
list[loc] = newItem; //insert the item at the specified position
length++; //increment the length
}
} //end insertAt
void arrayList::removeFirst()
{
//complete the code
}
void arrayList::removeLast()
{
//complete the code
}
void arrayList::removeSecondLast()
{
//complete the code
}
SLinkList.h
struct node
{
int info;
node *link;
};
class SLinkList
{
public:
SLinkList(); //default constructor, Initializes the list to an empty state.
void insertFirst(const int& newItem); //Function to insert newItem in the list.
void insertLast(const int& newItem); //Function to return newItem at the end of the list.
void destroyList(); //destroys the entire list
void insertAt(int loc, const int& newItem); //inserts newItem at a given location (list indexing starts with 0)
void removeFirst(); //removes the first element from the list
void removeLast(); //removes the last element from the list
void removeSecondLast(); // removes the second last element from the list
protected:
int count; //variable to store the number of elements in the list
node *first; //pointer to the first node of the list
node *last; //pointer to the last node of the list
};
SLinkList::SLinkList() // default constructor
{
first = NULL;
last = NULL;
count = 0;
}
void SLinkList::insertFirst(const int& newItem)
{
node *newNode; //pointer to create the new node
newNode = new node; //create the new node
assert(newNode != NULL); //If unable to allocate memory,
//terminate the program
newNode->info = newItem; //store the new item in the node
newNode->link = first; //insert newNode before first
first = newNode; //make first point to the actual first node
count++; //increment count
if(last == NULL) //if the list was empty, newNode is also
//the last node in the list
last = newNode;
}
void SLinkList::insertLast(const int& newItem)
{
node *newNode; //pointer to create the new node
newNode = new node; //create the new node
assert(newNode != NULL); //If unable to allocate memory, terminate the program
newNode->info = newItem; //store the new item in the node
newNode->link = NULL; //set the link field of newNode to NULL
if(first == NULL) //if the list is empty, newNode is both the first and last node
{
first = newNode;
last = newNode;
count++; //increment count
}
else //the list is not empty, insert newNode after last
{
last->link = newNode; //insert newNode after last
last = newNode; //make last point to the actual last node
count++; //increment count
}
}
void SLinkList::destroyList()
{
node *temp; //pointer to deallocate the memory
//occupied by the node
while(first != NULL) //while there are nodes in the list
{
temp = first; //set temp to the current node
first = first->link; //advance first to the next node
delete temp; //deallocate memory occupied by temp
}
last = NULL; //initialize last to NULL; first has already
//been set to NULL by the while loop
count = 0;
}
void SLinkList::insertAt(int loc, const int& newItem)
{
//complete the code
}
void SLinkList::removeFirst()
{
//complete the code
}
void SLinkList::removeLast()
{
//complete the code
}
void SLinkList::removeSecondLast()
{
//complete the code
}
