16.1)Extend the class linkedListType by adding the following operations:

Find and delete the node with the smallest info in the list. (Delete only the first occurrence and traverse the list only once.)

Find and delete all occurrences of a given info from the list. (Traverse the list only once.). For example, if the original list looks like this: 1, 2, 3, 4, 2, 5, 2 the revised list should look like this after deleting all occurrences of nodes with 2 in the info field: 1, 3, 4, 5

Add these as abstract functions in the class linkedListType and provide the definitions of these functions in the class unorderedLinkedList. Also, write a program to test these functions.

Turn in

All your template files

Your test program

The results of running your test program

below is the source code for linkedlistType and unorderedlinkedListType:

#ifndef H_LinkedListType #define H_LinkedListType #include #include

using namespace std;

//Definition of the node

template struct nodeType { Type info; nodeType *link; };

template class linkedListIterator { public: linkedListIterator(); //Default constructor //Postcondition: current = NULL;

linkedListIterator(nodeType *ptr); //Constructor with a parameter. //Postcondition: current = ptr;

Type operator*(); //Function to overload the dereferencing operator *. //Postcondition: Returns the info contained in the node.

linkedListIterator operator++(); //Overload the pre-increment operator. //Postcondition: The iterator is advanced to the next // node.

bool operator==(const linkedListIterator& right) const; //Overload the equality operator. //Postcondition: Returns true if this iterator is equal to // the iterator specified by right, // otherwise it returns the value false.

bool operator!=(const linkedListIterator& right) const; //Overload the not equal to operator. //Postcondition: Returns true if this iterator is not // equal to the iterator specified by // right; otherwise it returns the value // false.

private: nodeType *current; //pointer to point to the current //node in the linked list };

template linkedListIterator::linkedListIterator() { current = NULL; }

template linkedListIterator:: linkedListIterator(nodeType *ptr) { current = ptr; }

template Type linkedListIterator::operator*() { return current->info; }

template linkedListIterator linkedListIterator::operator++() { current = current->link;

return *this; }

template bool linkedListIterator::operator== (const linkedListIterator& right) const { return (current == right.current); }

template bool linkedListIterator::operator!= (const linkedListIterator& right) const { return (current != right.current); }

//***************** class linkedListType ****************

template class linkedListType { public: const linkedListType& operator= (const linkedListType&); //Overload the assignment operator.

void initializeList(); //Initialize the list to an empty state. //Postcondition: first = NULL, last = NULL, count = 0;

bool isEmptyList() const; //Function to determine whether the list is empty. //Postcondition: Returns true if the list is empty, // otherwise it returns false.

void print() const; //Function to output the data contained in each node. //Postcondition: none

int length() const; //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 = NULL, last = NULL, count = 0;

Type front() const; //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, the program // terminates; otherwise, the first // element of the list is returned.

Type back() const; //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, the program // terminates; otherwise, the last // element of the list is returned.

virtual bool search(const Type& searchItem) const = 0; //Function to determine whether searchItem is in the list. //Postcondition: Returns true if searchItem is in the // list, otherwise the value false is // returned.

virtual void insertFirst(const Type& newItem) = 0; //Function to insert newItem at the beginning of the list. //Postcondition: first points to the new list, newItem is // inserted at the beginning of the list, // last points to the last node in the list, // and count is incremented by 1.

virtual void insertLast(const Type& newItem) = 0; //Function to insert newItem at the end of the list. //Postcondition: first points to the new list, newItem // is inserted at the end of the list, // last points to the last node in the list, // and count is incremented by 1.

virtual void deleteNode(const Type& deleteItem) = 0; //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, last // points to the last node of the updated // list, and count is decremented by 1.

linkedListIterator begin(); //Function to return an iterator at the begining of the //linked list. //Postcondition: Returns an iterator such that current is // set to first.

linkedListIterator end(); //Function to return an iterator one element past the //last element of the linked list. //Postcondition: Returns an iterator such that current is // set to NULL.

linkedListType(); //default constructor //Initializes the list to an empty state. //Postcondition: first = NULL, last = NULL, count = 0;

linkedListType(const linkedListType& otherList); //copy constructor

~linkedListType(); //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 *first; //pointer to the first node of the list nodeType *last; //pointer to the last node of the list

private: void copyList(const linkedListType& otherList); //Function to make a copy of otherList. //Postcondition: A copy of otherList is created and // assigned to this list. };

template bool linkedListType::isEmptyList() const { return(first == NULL); }

template linkedListType::linkedListType() //default constructor { first = NULL; last = NULL; count = 0; }

template void linkedListType::destroyList() { nodeType *temp; //pointer to deallocate the memory //occupied by the node while (first != NULL) //while there are nodes in the list { temp = first; //set temp to the current node first = first->link; //advance first to the next node delete temp; //deallocate the memory occupied by temp } last = NULL; //initialize last to NULL; first has already //been set to NULL by the while loop count = 0; }

template void linkedListType::initializeList() { destroyList(); //if the list has any nodes, delete them }

template void linkedListType::print() const { nodeType *current; //pointer to traverse the list

current = first; //set current so that it points to //the first node while (current != NULL) //while more data to print { cout << current->info << " "; current = current->link; } }//end print

template int linkedListType::length() const { return count; } //end length

template Type linkedListType::front() const { assert(first != NULL);

return first->info; //return the info of the first node }//end front

template Type linkedListType::back() const { assert(last != NULL);

return last->info; //return the info of the last node }//end back

template linkedListIterator linkedListType::begin() { linkedListIterator temp(first);

return temp; }

template linkedListIterator linkedListType::end() { linkedListIterator temp(NULL);

return temp; }

template void linkedListType::copyList (const linkedListType& otherList) { nodeType *newNode; //pointer to create a node nodeType *current; //pointer to traverse the list

if (first != NULL) //if the list is nonempty, make it empty destroyList();

if (otherList.first == NULL) //otherList is empty { first = NULL; last = NULL; count = 0; } else { current = otherList.first; //current points to the //list to be copied count = otherList.count;

//copy the first node first = new nodeType; //create the node

first->info = current->info; //copy the info first->link = NULL; //set the link field of //the node to NULL last = first; //make last point to the //first node current = current->link; //make current point to //the next node

//copy the remaining list while (current != NULL) { newNode = new nodeType; //create a node newNode->info = current->info; //copy the info newNode->link = NULL; //set the link of //newNode to NULL last->link = newNode; //attach newNode after last last = newNode; //make last point to //the actual last node current = current->link; //make current point //to the next node }//end while }//end else }//end copyList

template linkedListType::~linkedListType() //destructor { destroyList(); }//end destructor

template linkedListType::linkedListType (const linkedListType& otherList) { first = NULL; copyList(otherList); }//end copy constructor

//overload the assignment operator template const linkedListType& linkedListType::operator= (const linkedListType& otherList) { if (this != &otherList) //avoid self-copy { copyList(otherList); }//end else

return *this; }

#endif

#ifndef H_LinkedListType #define H_LinkedListType #include #include

using namespace std;

//Definition of the node

template struct nodeType { Type info; nodeType *link; };

template class linkedListIterator { public: linkedListIterator(); //Default constructor //Postcondition: current = NULL;

linkedListIterator(nodeType *ptr); //Constructor with a parameter. //Postcondition: current = ptr;

Type operator*(); //Function to overload the dereferencing operator *. //Postcondition: Returns the info contained in the node.

linkedListIterator operator++(); //Overload the pre-increment operator. //Postcondition: The iterator is advanced to the next // node.

bool operator==(const linkedListIterator& right) const; //Overload the equality operator. //Postcondition: Returns true if this iterator is equal to // the iterator specified by right, // otherwise it returns the value false.

bool operator!=(const linkedListIterator& right) const; //Overload the not equal to operator. //Postcondition: Returns true if this iterator is not // equal to the iterator specified by // right; otherwise it returns the value // false.

private: nodeType *current; //pointer to point to the current //node in the linked list };

template linkedListIterator::linkedListIterator() { current = NULL; }

template linkedListIterator:: linkedListIterator(nodeType *ptr) { current = ptr; }

template Type linkedListIterator::operator*() { return current->info; }

template linkedListIterator linkedListIterator::operator++() { current = current->link;

return *this; }

template bool linkedListIterator::operator== (const linkedListIterator& right) const { return (current == right.current); }

template bool linkedListIterator::operator!= (const linkedListIterator& right) const { return (current != right.current); }

//***************** class linkedListType ****************

template class linkedListType { public: const linkedListType& operator= (const linkedListType&); //Overload the assignment operator.

void initializeList(); //Initialize the list to an empty state. //Postcondition: first = NULL, last = NULL, count = 0;

bool isEmptyList() const; //Function to determine whether the list is empty. //Postcondition: Returns true if the list is empty, // otherwise it returns false.

void print() const; //Function to output the data contained in each node. //Postcondition: none

int length() const; //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 = NULL, last = NULL, count = 0;

Type front() const; //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, the program // terminates; otherwise, the first // element of the list is returned.

Type back() const; //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, the program // terminates; otherwise, the last // element of the list is returned.

virtual bool search(const Type& searchItem) const = 0; //Function to determine whether searchItem is in the list. //Postcondition: Returns true if searchItem is in the // list, otherwise the value false is // returned.

virtual void insertFirst(const Type& newItem) = 0; //Function to insert newItem at the beginning of the list. //Postcondition: first points to the new list, newItem is // inserted at the beginning of the list, // last points to the last node in the list, // and count is incremented by 1.

virtual void insertLast(const Type& newItem) = 0; //Function to insert newItem at the end of the list. //Postcondition: first points to the new list, newItem // is inserted at the end of the list, // last points to the last node in the list, // and count is incremented by 1.

virtual void deleteNode(const Type& deleteItem) = 0; //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, last // points to the last node of the updated // list, and count is decremented by 1.

linkedListIterator begin(); //Function to return an iterator at the begining of the //linked list. //Postcondition: Returns an iterator such that current is // set to first.

linkedListIterator end(); //Function to return an iterator one element past the //last element of the linked list. //Postcondition: Returns an iterator such that current is // set to NULL.

linkedListType(); //default constructor //Initializes the list to an empty state. //Postcondition: first = NULL, last = NULL, count = 0;

linkedListType(const linkedListType& otherList); //copy constructor

~linkedListType(); //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 *first; //pointer to the first node of the list nodeType *last; //pointer to the last node of the list

private: void copyList(const linkedListType& otherList); //Function to make a copy of otherList. //Postcondition: A copy of otherList is created and // assigned to this list. };

template bool linkedListType::isEmptyList() const { return(first == NULL); }

template linkedListType::linkedListType() //default constructor { first = NULL; last = NULL; count = 0; }

template void linkedListType::destroyList() { nodeType *temp; //pointer to deallocate the memory //occupied by the node while (first != NULL) //while there are nodes in the list { temp = first; //set temp to the current node first = first->link; //advance first to the next node delete temp; //deallocate the memory occupied by temp } last = NULL; //initialize last to NULL; first has already //been set to NULL by the while loop count = 0; }

template void linkedListType::initializeList() { destroyList(); //if the list has any nodes, delete them }

template void linkedListType::print() const { nodeType *current; //pointer to traverse the list

current = first; //set current so that it points to //the first node while (current != NULL) //while more data to print { cout << current->info << " "; current = current->link; } }//end print

template int linkedListType::length() const { return count; } //end length

template Type linkedListType::front() const { assert(first != NULL);

return first->info; //return the info of the first node }//end front

template Type linkedListType::back() const { assert(last != NULL);

return last->info; //return the info of the last node }//end back

template linkedListIterator linkedListType::begin() { linkedListIterator temp(first);

return temp; }

template linkedListIterator linkedListType::end() { linkedListIterator temp(NULL);

return temp; }

template void linkedListType::copyList (const linkedListType& otherList) { nodeType *newNode; //pointer to create a node nodeType *current; //pointer to traverse the list

if (first != NULL) //if the list is nonempty, make it empty destroyList();

if (otherList.first == NULL) //otherList is empty { first = NULL; last = NULL; count = 0; } else { current = otherList.first; //current points to the //list to be copied count = otherList.count;

//copy the first node first = new nodeType; //create the node

first->info = current->info; //copy the info first->link = NULL; //set the link field of //the node to NULL last = first; //make last point to the //first node current = current->link; //make current point to //the next node

//copy the remaining list while (current != NULL) { newNode = new nodeType; //create a node newNode->info = current->info; //copy the info newNode->link = NULL; //set the link of //newNode to NULL last->link = newNode; //attach newNode after last last = newNode; //make last point to //the actual last node current = current->link; //make current point //to the next node }//end while }//end else }//end copyList

template linkedListType::~linkedListType() //destructor { destroyList(); }//end destructor

template linkedListType::linkedListType (const linkedListType& otherList) { first = NULL; copyList(otherList); }//end copy constructor

//overload the assignment operator template const linkedListType& linkedListType::operator= (const linkedListType& otherList) { if (this != &otherList) //avoid self-copy { copyList(otherList); }//end else

return *this; }

#endif