THIS IS ALL THE INFORMATION I GOT FROM MY PROFESSOR AND IT SHOULD BE DONE BY C++
ID: 3750184 • Letter: T
Question
THIS IS ALL THE INFORMATION I GOT FROM MY PROFESSOR AND IT SHOULD BE DONE BY C++
oT-Mobile LTE 3:26 PM Back Lab 4 LinkedLists.pdf Lab 4- Linked Lists implementing Lists using Linked Lists What you will learn Implementing linked lists · The list ADT Templanes * Running timesis Coding exercise Extend the esample discussed in class to implement list functionalities using inked lists in a template called linkedListlist. desired are as Checks if ist is Returmi the sue of the lst Prints the elements of the lnt on the console boo1 isFul int listsize) const print) bool istte kttqualint,lenType) Checks if the item at position matches the Inserts ebjnct to end o the Int Removes ebject at What to turn in A aip fle containing the linkedlistlist.h file with your template declaration and implementation, anda main.cpp fle with test cases to show that your program works For each function, analyze the running time of your algorithm, Le, 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 pof When to turn in Tuesday labng. due on Wednesday 1 1:59pm tf you submit on Tuesday, you get 10 bonus ports. Thursday lab is due on Friday 11-59pm. If you submit on Thursdary, you gee 120 bonus points * 1 of 1 Courses Calendar To Do Notifications InboxExplanation / 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.