IN C++ Solve it using TEMPLATES Use sortedLinkedList.h and main.cpp file What yo
ID: 3756614 • Letter: I
Question
IN C++
Solve it using TEMPLATES
Use sortedLinkedList.h and main.cpp file
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
Answer :
#include<iostream>
using namespace std;
template<typename T>
struct Node
{
T data;
Node *next;
};
template<typename T>
class linkedlist
{
private:
Node<T> *head;
Node<T> *end;
int capacity;
int size;
public:
linkedlist(int s= 5)
{
head = NULL;
end = NULL;
capacity = s;
}
~linkedlist(){
}
bool isEmpty() const
{
return size==0;
}
bool isFull() const{
return size == capacity;
}
int listSize() const
{
return size;
}
int maxListSize() const
{
return capacity;
}
void print()
{
Node<T> *current = head;
while(current != NULL)
{
cout<<current->data<<" ";
current = current->next;
}
cout<<endl;
}
bool isItemAtEqual(int pos, T data)
{
if(pos >= size)
{
cout<<"invalid Position"<<endl;
return false;
}
Node<T> *current = head;
int currentPosition = 0;
while(current != NULL && currentPosition < pos)
{
current = current->next;
currentPosition++;
}
return current->data == data;
}
void insertAt(int pos, T data)
{
if(pos > size)
{
cout<<"can't insert at position "<<pos<<" as list size is "<<size<<endl;
return;
}
if(isFull())
{
cout<<"list is Full"<<endl;
return;
}
Node<T> *temp = (Node<T>*) malloc(sizeof(Node<T>));
temp->data = data;
temp->next = NULL;
if(pos == 0)
{
if(head == NULL)
{
head = end = temp;
return;
}
else{
temp->next = head;
head = temp;
}
size++;
return ;
}
if(pos == size)
{
insertEnd(data);
return;
}
Node<T> *current = head;
Node<T> *prev = NULL;
int currentPosition = 0;
while(current != NULL && currentPosition < pos)
{
prev = current;
current = current->next;
currentPosition++;
}
prev->next = temp;
temp->next = current;
size++;
}
void insertEnd(T data)
{
Node<T> *temp = (Node<T>*) malloc(sizeof(Node<T>));
temp->data = data;
temp->next = NULL;
if(end == NULL)
{
head = end = temp;
}
end->next = temp;
end = temp;
size++;
}
void removeAt(int pos)
{
if(isEmpty())
{
return;
}
if(pos >= size)
{
return ;
}
if(pos == 0)
{
head = head->next;
if(head == NULL)
end = NULL;
size--;
return;
}
Node<T> *current = head;
Node<T> *prev = NULL;
int currentPosition = 0;
while(current != NULL && currentPosition < pos)
{
prev = current;
current = current->next;
currentPosition++;
}
if(current->next == NULL)
{
prev->next = NULL;
end = prev;
size--;
return;
}
prev->next = current->next;
size--;
}
T retreiveAt(int pos)
{
if(pos == 0)
{
return head->data;
}
if(pos == size-1)
{
return end->data;
}
if(pos >= size){
cout<<"Not enough element in the list:"<<endl;
return -1;
}
Node<T> *current = head;
int currentPosition = 0;
while(current != NULL && currentPosition < pos)
{
current = current->next;
currentPosition++;
}
return current->data;
}
void replaceAt(int pos, T data)
{
if(pos == 0)
{
head->data = data;
return ;
}
if(pos == size-1)
{
end->data = data;
return;
}
if(pos >= size)
{
cout<<"Not enough element in the list:"<<endl;
return ;
}
Node<T> *current = head;
int currentPosition = 0;
while(current != NULL && currentPosition < pos)
{
current = current->next;
currentPosition++;
}
current->data = data;
}
void clearList()
{
while(head != NULL)
{
Node<T> *current = head;
head = head->next;
delete current;
}
size = 0;
}
void operator =(const linkedlist &l)
size = l.listSize();
capacity = l.maxListSize();
head = NULL;
end = NULL;
Node<T> *current = l.head;
while(current!= NULL){
insertEnd(current->data);
current = current->next;
}
}
};
#include<iostream>
#include "linkedlist.h"
using namespace std;
using namespace std;
int main(){
linkedlist<int> l(10);
l.insertEnd(5);
l.insertEnd(8);
l.insertEnd(1);
l.insertEnd(2);
l.insertEnd(10);
cout<<"After insertEnd() list is: "<<endl;
l.print();
cout<<"Testing insertAt()"<<endl;
l.insertAt(0,23);
l.insertAt(6,25);
cout<<"After insertAt list is: "<<endl;
l.print();
cout<<"Testing removeAt()"<<endl;
l.removeAt(0);
l.removeAt(2);
cout<<"List after removeAt is: "<<endl;
l.print();
cout<<"Testing replaceAt: "<<endl;
l.replaceAt(0,56);
cout<<"List after replaceAt:"<<endl;
l.print();
cout<<"testing listSize: "<<endl;
cout<<"listSize: "<<l.listSize()<<endl;
cout<<"testing max list size: "<<endl;
cout<<"Max list size is: "<<l.maxListSize()<<endl;
cout<<"testing isFull"<<endl;
cout<<l.isFull()<<endl;
cout<<"testing isEmpty"<<endl;
cout<<l.isEmpty();
cout<<"testing = operator overloading: "<<endl;
linkedlist<int> l1 = l;
cout<<"new list l1 is: "<<endl;
l1.print();
return 0;
}