C++ Declare and implement the functions given in the question. Implementing List
ID: 3750927 • Letter: C
Question
C++Declare and implement the functions given in the question.
Implementing Lists using Linked Lists What you will learn Implementing linked lists The list ADT .Templates . Running time analysis Coding exercise Extend the example discussed in class to implement list functionalities using linked lists in a template called linkedListList. Functionalities desired are as follows: Function Constructors Destructors bool isEmpty() const bool isFull) const int listsize() const int maxListSize() const void print() bool isItemAtEqual (int, elemType) Checks if the item at position matches the 2n parameter void insertAt (int, elemType) void insertEnd(elemType) void removeAt (int) elemType retreiveAt(int) void replaceAt (int, elemType) void clearList operator Description Checks if list is emp Checks if list is full Returns the size of the list Returns the maximum possible size of the list Prints the elements of the list on the console Inserts 2nd parameter at position Inserts object to end of the list Removes object at position Retrieves object at position Replaces object at position with 2d parameter Empties the list Overload the assignment operator What to turn in A zip file containing the linkedListlist.h file with your template declaration and implementation, and a main.cpp file with test cases to show that your program works. For each function, analyze the running time of your algorithm, i.e.,the time complexity of your algorithms in big-O notation. Report it in a file called report.pdf. Include your sources as references in report.pdf
Explanation / Answer
linkedListList.h
#include <iostream>
using namespace std;
template <class elemType>
class Node // Node class template
{
public:
elemType data;
Node *next;
Node(elemType d);
Node(elemType d, Node *n);
};
template <class elemType>
Node<elemType>::Node(elemType d) //single parameter constructor
{ //O(1) running time
data = d;
next = NULL;
}
template <class elemType>
Node<elemType>::Node(elemType d, Node<elemType> *n) //two parameter constructor
{ //O(1) running time
data = d;
next = n;
}
template <class elemType>
class linkedListList
{
public:
Node<elemType> *front;
linkedListList();
~linkedListList();
bool isEmpty() const;
bool isFull() const;
int listSize() const;
int maxListSize() const;
void print() const;
bool isItemAtEqual(int ind, elemType x);
void insertAt(int ind, elemType x);
void insertEnd(elemType x);
void removeAt(int ind);
elemType retrieveAt(int ind);
void replaceAt(int ind, elemType x);
void clearList();
void operator= (linkedListList rhs);
};
template <class elemType>
linkedListList<elemType>::linkedListList() //0 parameter constructor
{ //O(1) running time
front = NULL;
}
template <class elemType>
linkedListList<elemType>::~linkedListList() //destructor
{ //O(1) running time
clearList();
}
template <class elemType>
bool linkedListList<elemType>::isEmpty() const //checks if front is NULL
{ //O(1) running time
return front == NULL;
}
template <class elemType>
bool linkedListList<elemType>::isFull() const //checks if current size is max size
{ //O(n) running time because listSize is O(n)
return listSize() == maxListSize();
}
template <class elemType>
int linkedListList<elemType>::listSize() const //counts the number of nodes
{ //O(n) running time because listSize is O(n)
Node<elemType> *t = front; //pointer to run through the list
int counter = 0; //initialize counter
while (t != NULL)
{
counter++; //increment counter
t = t->next; //advance pointer
}
//The iterator has to run through every element in the list hence it takes O(n) time
}
template <class elemType>
int linkedListList<elemType>::maxListSize() const //returns maximum size that can be stored
{ //O(1) running time
return 2147483647;
}
template <class elemType>
void linkedListList<elemType>::print() const //prints all elements in order
{ //O(n) running time
Node<elemType> *t = front; //pointer to run through the list
while (t != NULL)
{
cout << t->data << " "; //print data of node
t = t->next; //advance pointer
}
cout << " ";
//The iterator has to run through every element in the list hence it takes O(n) time
}
template <class elemType>
//checks if the element at ind is equal to second parameter
bool linkedListList<elemType>::isItemAtEqual(int ind, elemType x)
{ //O(n) running time
Node<elemType> *t = front; //pointer to run through the list
//loop will run until required index or until it reaches end of list
while (t != NULL && ind--)
t = t->next; //advance pointer
return t->data == x; //return whether the indexed data and second parameter are equal
//The iterator has to run through every element in the list in the worst case
//hence it takes O(n) time
}
template <class elemType>
//insert at index
void linkedListList<elemType>::insertAt(int ind, elemType x)
{ //O(n) running time
if (ind == 0)
front = new Node<elemType>(x, front); //special case when index is zero
else
{
Node<elemType> *t = front;
//advance pointer until it points to the element before insertion
while (t->next != NULL && --ind)
t = t->next;
t->next = new Node<elemType>(x, t->next); //use the 2 parameter construtor
}
//The iterator has to run through every element
//in the list in the worst case hence it takes O(n) time
}
template <class elemType>
//insert at end
void linkedListList<elemType>::insertEnd(elemType x)
{ //O(n) running time
if (front == NULL)
front = new Node<elemType>(x, NULL); //special case when front is NULL
else
{
Node<elemType> *t = front;
//advance pointer until it points to the last element
while (t->next != NULL) //t->next = NULL indicates t is last element
t = t->next;
t->next = new Node<elemType>(x, NULL); //use the 2 parameter construtor
}
//The iterator has to run through every element in the list hence it takes O(n) time
}
template <class elemType>
//remove element at index
void linkedListList<elemType>::removeAt(int ind)
{ //O(n) running time
if (ind == 0)
{
Node<elemType> *t = front; //special case when index is 0
front = front->next;
delete t;
}
else
{
Node<elemType> *t = front;
//we want to stop at the element before index
while (--ind) //loop will run ind - 1 times
t = t->next;
Node<elemType> *k = t->next;
t->next = t->next->next; //link to next node
delete k; //delete original node
}
//The iterator has to run through every element
//in the list in the worst case hence it takes O(n) time
}
template <class elemType>
//retrieve element at index
elemType linkedListList<elemType>::retrieveAt(int ind)
{ //O(n) running time
Node<elemType> *t = front;
while (t->next != NULL && ind--) //advance iterator index times and check for overshooting
t = t->next;
return t->data; //return desired element or
//in case of overshooting, the last element
//The iterator has to run through every element
//in the list in the worst case hence it takes O(n) time
}
template <class elemType>
//replace element at index
void linkedListList<elemType>::replaceAt(int ind, elemType x)
{ //O(n) running time
Node<elemType> *t = front;
while (t->next != NULL && ind--) //advance iterator index times and check for overshooting
t = t->next;
t->data = x; //replace desired element or
//in case of overshooting, the last element
//The iterator has to run through every element
//in the list in the worst case hence it takes O(n) time
}
template <class elemType>
//replace element at index
void linkedListList<elemType>::clearList()
{ //O(n) running time
//loop runs until front is NULL ie. list is empty
while (front != NULL)
{
Node<elemType> *t = front; //store current front in t
front = front->next; //advance front
delete t; //delete node
}
//The iterator has to run through every element in the list hence it takes O(n) time
}
template <class elemType>
//replace element at index
void linkedListList<elemType>::operator=(linkedListList rhs)
{ //O(n^2) running time
clearList(); //remove current list
Node<elemType> *t = rhs.front; //iterator through second list
while (t != NULL)
{
insertEnd(t->data); //insert elements at the end of first list
t = t->next; //advance t
}
//The iterator has to run through every element in list rhs
//and has to insert it at the end of first list which takes O(n) time
//So it takes n * O(n) time ie. O(n^2) time
}
main.cpp
#include <iostream>
#include "linkedListList.h"
using namespace std;
int main()
{
linkedListList<int> l1, l2;
l1.insertEnd(1);
l1.insertEnd(2);
l1.insertEnd(4);
l1.insertEnd(5);
l1.insertAt(2, 3);
l1.print();
l2 = l1;
l2.print();
return 0;
}
Running time analysis for each function has been given in the comments in the function definition.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.