#ifndef H_circularLinkedList #define H_circularLinkedList #include <iostream> #i
ID: 3906803 • Letter: #
Question
#ifndef H_circularLinkedList
#define H_circularLinkedList
#include <iostream>
#include <cassert>
using namespace std;
template <class Type>
struct nodeType
{
Type info;
nodeType<Type> *link;
};
template <class Type>
class circularLinkedList
{
public:
const circularLinkedList<Type>& operator=
(const circularLinkedList<Type>&);
//Overloads the assignment operator.
void initializeList();
//Initializes the list to an empty state.
//Postcondition: first = nullptr, last = nullptr,
// count = 0
bool isEmptyList();
//Function to determine whether the list is empty.
//Postcondition: Returns true if the list is empty;
// otherwise, returns false.
void print() const;
int length();
//Function to return the number of nodes in the
//list.
//Postcondition: The value of count is returned.
void destroyList();
//Function to delete all the nodes from the list.
//Postcondition: first = nullptr, last = nullptr,
// count = 0
Type front();
//Function to return the first element of the list.
//Precondition: The list must exist and must not be
//empty.
//Postcondition: If the list is empty, then the
// program terminates; otherwise,
// the first element of the list is
// returned.
Type back();
//Function to return the last element of the
//list.
//Precondition: The list must exist and must not
//be empty.
//Postcondition: If the list is empty, then the
// program terminates; otherwise,
// the last element of the list is
// returned.
bool search(const Type& searchItem);
//Function to determine whether searchItem is in
//the list.
//Postcondition: Returns true if searchItem is found
// in the list; otherwise, it returns
// false.
void insertNode(const Type& newitem);
void deleteNode(const Type& deleteItem);
//Function to delete deleteItem from the list.
//Postcondition: If found, the node containing
// deleteItem is deleted from the
// list, first points to the first
// node, and last points to the last
// node of the updated list.
circularLinkedList();
//Default constructor
//Initializes the list to an empty state.
//Postcondition: first = nullptr, last = nullptr,
// count = 0
circularLinkedList(const circularLinkedList<Type>& otherList);
//Copy constructor
~circularLinkedList();
//Destructor
//Deletes all the nodes from the list.
//Postcondition: The list object is destroyed.
protected:
int count; //variable to store the number of
//elements in the list
nodeType<Type> *first; //pointer to the first node of
//the list
nodeType<Type> *last; //pointer to the last node of
//the list
private:
void copyList(const circularLinkedList<Type>& otherList);
//Function to make a copy of otherList.
//Postcondition: A copy of otherList is created
// and assigned to this list.
};
template <class Type>
bool circularLinkedList<Type>::isEmptyList()
{
// function to determine if list is empty
}
template <class Type>
circularLinkedList<Type>::circularLinkedList() // default constructor
{
first = nullptr;
count = 0;
}
template <class Type>
void circularLinkedList<Type>::destroyList()
{
// function to destroy the list
}
template <class Type>
void circularLinkedList<Type>::initializeList()
{
destroyList(); //if the list has any nodes, delete them
}
template <class Type>
int circularLinkedList<Type>::length()
{
// function to find the length of the list
} // end length
template <class Type>
Type circularLinkedList<Type>::front()
{
assert(first != nullptr);
return first->link->info; //return the info of the first node
}//end front
template <class Type>
Type circularLinkedList<Type>::back()
{
assert(first != nullptr);
return first->info; //return the info of the first node
}//end back
template <class Type>
bool circularLinkedList<Type>::search(const Type& searchItem)
{
// function to search the list for a given item
}//end search
template <class Type>
void circularLinkedList<Type>::insertNode(const Type& newitem)
{
// function to insert an item into the list
}//end insertNode
template <class Type>
void circularLinkedList<Type>::deleteNode(const Type& deleteItem)
{
// function to delete an item from the list
} //end deleteNode
//Overloading the stream insertion operator
template <class Type>
void circularLinkedList<Type>::print() const
{
// function to print the list
}
template <class Type>
circularLinkedList<Type>::~circularLinkedList() // destructor
{
destroyList();
}//end destructor
template <class Type>
void circularLinkedList<Type>::copyList
(const circularLinkedList<Type>& otherList)
{
// function to copy the list
}//end copyList
//copy constructor
template<class Type>
circularLinkedList<Type>::circularLinkedList
(const circularLinkedList<Type>& otherList)
{
first = nullptr;
copyList(otherList);
}//end copy constructor
//overload the assignment operator
template <class Type>
const circularLinkedList<Type>& circularLinkedList<Type>::operator=
(const circularLinkedList<Type>& otherList)
{
if (this != &otherList) //avoid self-copy
{
copyList(otherList);
}//end else
return *this;
}
#endif
(Circular linked lists) This chapter defined and identified various operations on a circular linked list.
Write the definitions of the class circularLinkedListand its member functions. (You may assume that the elements of the circular linked list are in ascending order.)
I was given a main.cpp of:
//This program tests various operation of a linked list
//45 67 23 89 -999
#include <iostream>
#include "circularLinkedList.h"
using namespace std;
void testCopyConstructor(circularLinkedList<int> oList);
int main()
{
circularLinkedList<int> list1, list2;
int num;
cout << "Enter number ending with -999" << endl;
cin >> num;
while (num != -999)
{
list1.insertNode(num);
cin >> num;
}
cout << endl;
cout << "List 1: ";
list1.print();
cout << endl;
cout << "Length List 1: " << list1.length() << endl;
cout << "Enter the number to be searched: ";
cin >> num;
cout << endl;
if (list1.search(num))
cout << num << " found in the list" << endl;
else
cout << num << " not in the list" << endl;
cout << "Enter the number to be deleted: ";
cin >> num;
cout << endl;
list1.deleteNode(num);
cout << "After deleting the node, "
<< "List 1: ";
list1.print();
cout << endl;
cout << "Length List 1: " << list1.length() << endl;
list2 = list1;
cout << "List 2: ";
list2.print();
cout << endl;
cout << "Length List 2: " << list2.length() << endl;
testCopyConstructor(list1);
cout << "List 1: ";
list1.print();
cout << endl;
return 0;
}
void testCopyConstructor(circularLinkedList<int> oList)
{
}
and i was given a circularLinkedList.h of:
Explanation / Answer
CircularLinkedList.hpp
class Node{
public :
Node();
int data;
Node *next;
};
class LinkedList{
private :
Node *head;
Node *tail;
int nodes;
public :
LinkedList();
void addInList(int data);
void display();
bool search(int n);
void deleteNode(int data);
LinkedList* copyConstructor(LinkedList *p);
int getSize();
};
CircularLinkedList.cpp
#include<iostream>
using namespace std;
#include "circularLinkedList.hpp"
//Node class constructor
Node :: Node()
{
data=0;
next=NULL;
}
//default constructor ,set size of list as zero
LinkedList::LinkedList()
{
head=NULL;
tail=NULL;
nodes=0;//nodes count is 0
}
//function to add data in a list
void LinkedList::addInList(int data){
Node *node=new Node();//create a new node
node->data=data;//set nodes data
node->next=NULL;//set the pointer next as null
//if list is empty
if(head==NULL)
{
head=node;//make the node as head
tail=node;//make the tail point to node
}
else{
tail->next=node;//else add at the end of the list,ie. after tail node
tail=node;//make the node as tail
}
nodes++;//increment the count of nodes in the list
tail->next=head;//make the LinkedList a circular Linked List by pointing tail next to head
}
//function to display the linked list
void LinkedList::display(){
Node *trav=this->head;
if(trav==NULL)
{//if list is empty
cout<<"The list is EMPTY."<<endl;
return;//return
}
cout<<trav->data<<" ";//print head data
trav=trav->next;//set trav=head next
//while trav not becomes head again , circular linked list
while(trav!=this->head)
{
cout<<trav->data<<" ";//print the trav->data
trav=trav->next;//make the trav point to the next node
}
cout<<endl<<endl;
}
//function to know whether a data exists in the linked list already ?
bool LinkedList::search(int n){
Node *trav=head;
if(trav==NULL)
{
//if list is empty return false,means no such data exists in list
return false;
}
if(trav->data==n)//if head data=n return true
return true;
trav=trav->next;
while(trav!=head)
{//while trav again not equals to head check for every nodes data
if(trav->data==n)//if data found return true
return true;
trav=trav->next;//point trav to next node
}
return false;//no data found
}
//function to delete the node with corresponding data
void LinkedList::deleteNode(int data){
Node *trav=head;
if(trav==NULL)
{//if the list is empty return
return;
}
if(trav->data==data)//if the data to be deleted is of head node
{
Node *temp=trav;
head=trav->next;//head points to next location node
tail=head;//make a circular linked list
delete temp;//delete node from heap space
return;
}
trav=trav->next;//trav is the next node to head
Node *prev=head;//prev is the head node
while(trav!=head)//check for every nodes data
{
if(trav->data==data)
{//found the node to be deleted
Node *temp=trav;
prev->next=trav->next;
delete temp;//free up the deleted node space on heap
return;
}
prev=trav;//make trav as prev
trav=trav->next;//incrementing the trav to next node
}
nodes--;//decrement the count of number of nodes in the linked list
}
//function to copy a linked list
LinkedList* LinkedList::copyConstructor(LinkedList *p){
Node *phead=p->head;
Node *ptail=p->tail;
if(phead==NULL)//if list is empty return null
return NULL;
LinkedList *list=new LinkedList();//create a new linked list
list->addInList(phead->data);//add the first head nodes value
ptail=phead->next;
while(ptail!=phead)//copy each nodes data to new list
{
list->addInList(ptail->data);
ptail=ptail->next;
}
return list;//return the new list pointer
}
//function to get the count of nodes in the linked list
int LinkedList::getSize()
{
return nodes;//return the count of nodes in the linked list
}
//main method to test the linked list class
int main()
{
LinkedList *list=new LinkedList();
list->addInList(1);
list->addInList(2);
list->addInList(3);
list->addInList(4);
list->addInList(5);
//printing the list
cout<<"The original List is : "<<endl;
list->display();
//finding some element
bool isThere=list->search(5);//prints 1,true means
cout<<(isThere==1?"Found 5":"Not found 5")<<endl;
bool isThere2=list->search(6);
cout<<(isThere2==1?"Found 6":"Not found 6")<<endl<<endl;//prints 0 means not found
//copy constructor test
LinkedList *copylist=new LinkedList();
copylist=copylist->copyConstructor(list);
//printing the copied list
cout<<"The copied list is : "<<endl;
copylist->display();
cin.get();//to pause the console screen
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.