IN C++ Solve it using TEMPLATES What you will learn . Implementing a sorted link
ID: 3756494 • Letter: I
Question
IN C++
Solve it using TEMPLATES
What you will learn . Implementing a sorted linked list Templates Running time analysis Coding exercise Implement a sorted linked list in a template called sortedLinkedList. Functionalities desired are as follows: Function Constructors Destructors bool isEmpty() const bool isFull) const int listsize() const int maxListsize) const void print() bool contains (elemType) void insert (elemType) void remove (elemType) elemType retreiveAt(int) void clearList() operator Description Checks if list is em 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 Checks if the item is present in the linked list Inserts element into the sorted linked list Removes an element from the sorted linked list Retrieves object in the given position Empties the list Overload the assignment operator The list should always be sorted, i.e., each element should always be less than its next element and smaller than its previous element. You can use a singly or doubly linked list implementation What to turn in A zip file containing the sortedLinkedList.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
#include<iostream>
using namespace std;
#include<conio.h>
template<class T>
class Nodes
{
public:
T info;
Nodes<T> Links;
};
template<class T>
class list
{
private:
Nodes<T> start;
public:
list();
list();
void create_List();
void del();
void insert();
void view();
};
template<class T>
list<T>::list()
{
start=NULL;
}
template<class T>
list<T>::~list()
{
Nodes<T> next;
while(start)
{
next=start->Links;
delete start;
start=next;
}
}
template<class T>
void list<T>::create_List()
{
T a;
Nodes<T> current,pointerr;
cout<<" Enter info Of New Node (Enter 0 To Have other options):";
cin>>a;
while(a)
{
current=new Nodes<T>;
current->info=a;
current->Links=NULL;
if(start==NULL)
start=current;
else
pointerr->Links=current;
pointerr=current;
cout<<" Enter info Of New Node (Enter 0 To Have other options):";
cin>>a;
}
}
template<class T>
void list<T>::insert()
{
Nodes<T> current,pointerr;
T ele;
char ch;
pointerr=start;
current=new Nodes<T>;
cout<<" Enter info Of New Node:";
cin>>current->info;
current->Links=NULL;
cout<<" Do u wish to insert at the start [y/n]:";
cin>>ch;
if(ch=='Y'||ch=='y')
{
current->Links=start;
start=current;
}
else
{
cout<<" Specify after which element do u want to insert :";
cin>>ele;
while(pointerr!=NULL)
{
if(pointerr->info==ele)
{
current->Links=pointerr->Links;
pointerr->Links=current;
break;
}
else
{
pointerr=pointerr->Links;
}
}
}
}
template<class T>
void list<T>::del()
{
T ele;
char choice;
Nodes<T> pointerr,ptr1;
if(start==NULL)
{
cout<<" Sorry list is empty.";
}
else
{
pointerr=start;
cout<<" Do u want to delete start element? [y/n]:";
cin>>choice;
if(choice=='y'||choice=='Y')
{
start=start->Links;
delete pointerr;
}
else
{
cout<<" Specify which element do u want to delete :";
cin>>ele;
while(pointerr!=NULL)
{
if(pointerr->Links->info==ele)
{
ptr1=pointerr->Links;
pointerr->Links=ptr1->Links;
delete ptr1;
return;
}
else
{
pointerr=pointerr->Links;
}
}
}
}
}
template<class T>
void list<T>::view()
{
Nodes<T> pointerr;
if(start==NULL)
{
cout<<" Sorry list is empty..";
}
else
{
pointerr=start;
while(pointerr!=NULL)
{
cout<<pointerr->info<<" ";
pointerr=pointerr->Links;
}
}
}
int main()
{
int n;
list <int> l;
l.create_List();
do
{
cout<<" 1.Insertion 2.Deletion 3.Print List 4.Exit ";
cout<<" Enter your option : ";
cin>>n;
switch(n)
{
case 1: l.insert();
break;
case 2: l.del();
break;
case 3: l.view();
break;
case 4:
exit(0);
break;
}
}while(n<=4);
getch();
return 0;
}