* answer this question using data structure and object oriented programming with c++ language :

Q) read the the following linkedListType.h very well and answer the question after it :

Note : you will need stackType.h , it will be after the linkedList.h

#include using namespace std;

#ifndef LINKEDLISTTYPE_H_INCLUDED #define LINKEDLISTTYPE_H_INCLUDED //Definition of the node template struct nodeType { Type info; nodeType *link; };

template class linkedListType { public: void initializeList(); bool isEmptyList() const; void print() const; int length() const; void destroyList(); Type front() const; Type back() const; bool search(const Type& searchItem) const; void insertFirst(const Type& newItem); void insertLast(const Type& newItem); void deleteNode(const Type& deleteItem); nodeType* begin(); nodeType* end(); linkedListType(); ~linkedListType(); linkedListType(const linkedListType& otherList); const linkedListType& operator= (const linkedListType&);//no

protected: int count; nodeType *first; nodeType *last; private: void copyList(const linkedListType& otherList); };

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 { 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; }

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 nodeType* linkedListType::begin() { return first; }

template nodeType* linkedListType::end() { return last; }

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(); }

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

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

template bool linkedListType:: search(const Type& searchItem) const { nodeType *current; //pointer to traverse the list bool found = false; current = first; //set current to point to the first //node in the list while (current != NULL && !found) //search the list if (current->info == searchItem) //searchItem is found found = true; else current = current->link; //make current point to //the next node return found; }//end search

template void linkedListType::insertFirst(const Type& newItem) { nodeType *newNode; //pointer to create the new node newNode = new nodeType; //create the new node newNode->info = newItem; //store the new item in the node newNode->link = first; //insert newNode before first first = newNode; //make first point to the //actual first node count++; //increment count if (last == NULL) //if the list was empty, newNode is also //the last node in the list last = newNode; }//end insertFirst

template void linkedListType::insertLast(const Type& newItem) { nodeType *newNode; //pointer to create the new node newNode = new nodeType; //create the new node newNode->info = newItem; //store the new item in the node newNode->link = NULL; //set the link field of newNode //to NULL if (first == NULL) //if the list is empty, newNode is //both the first and last node { first = newNode; last = newNode; count++; //increment count } else //the list is not empty, insert newNode after last { last->link = newNode; //insert newNode after last last = newNode; //make last point to the actual //last node in the list count++; //increment count } }//end insertLast

template void linkedListType::deleteNode(const Type& deleteItem) { nodeType *current; //pointer to traverse the list nodeType *trailCurrent; //pointer just before current bool found; if (first == NULL) //Case 1; the list is empty cout << "Cannot delete from an empty list." << endl; else { if (first->info == deleteItem) //Case 2 { current = first; first = first->link; count--; if (first == NULL) //the list has only one node last = NULL; delete current; } else //search the list for the node with the given info { found = false; trailCurrent = first; //set trailCurrent to point //to the first node current = first->link; //set current to point to //the second node while (current != NULL && !found) { if (current->info != deleteItem) { trailCurrent = current; current = current-> link; } else found = true; }//end while

if (found) //Case 3; if found, delete the node { trailCurrent->link = current->link; count--; if (last == current) //node to be deleted //was the last node last = trailCurrent; //update the value //of last delete current; //delete the node from the list } else cout << "The item to be deleted is not in " << "the list." << endl; }//end else }//end else }//end deleteNode

stackType.h :

#ifndef STACKADT_H_INCLUDED #define STACKADT_H_INCLUDED //Header file: myStack.h #include #include using namespace std;

template class stackType { public: const stackType& operator=(const stackType&); void initializeStack(); bool isEmptyStack() const; bool isFullStack() const; void push(const Type& newItem); Type top() const; void pop(); stackType(int stackSize = 100); stackType(const stackType& otherStack); ~stackType();

private: int maxStackSize; //variable to store the maximum stack size int stackTop; //variable to point to the top of the stack Type *list; //pointer to the array that holds the stack elements void copyStack(const stackType& otherStack); };

template void stackType::initializeStack() { stackTop = 0; }//end initializeStack

template bool stackType::isEmptyStack() const { return (stackTop == 0); }//end isEmptyStack

template bool stackType::isFullStack() const { return (stackTop == maxStackSize); } //end isFullStack

template void stackType::push(const Type& newItem) { if (!isFullStack()) { list[stackTop] = newItem; //add newItem to the //top of the stack stackTop++; //increment stackTop } else cout << "Cannot add to a full stack." << endl; }//end push

template Type stackType::top() const { assert(stackTop != 0); //if stack is empty, //terminate the program return list[stackTop - 1]; //return the element of the //stack indicated by //stackTop - 1 }//end top

template void stackType::pop() { if (!isEmptyStack()) stackTop--; //decrement stackTop else cout << "Cannot remove from an empty stack." << endl; }//end pop

template stackType::stackType(int stackSize) { if (stackSize <= 0) { cout << "Size of the array to hold the stack must " << "be positive." << endl; cout << "Creating an array of size 100." << endl; maxStackSize = 100; } else maxStackSize = stackSize; //set the stack size to //the value specified by //the parameter stackSize stackTop = 0; //set stackTop to 0 list = new Type[maxStackSize]; //create the array to //hold the stack elements }//end constructor

template stackType::~stackType() //destructor { delete [] list; //deallocate the memory occupied //by the array }//end destructor

template void stackType::copyStack(const stackType& otherStack) { delete [] list; maxStackSize = otherStack.maxStackSize; stackTop = otherStack.stackTop; list = new Type[maxStackSize]; //copy otherStack into this stack for (int j = 0; j < stackTop; j++) list[j] = otherStack.list[j]; } //end copyStack

template stackType::stackType(const stackType& otherStack) { list = nullptr; copyStack(otherStack); }//end copy constructor

template const stackType& stackType::operator= (const stackType& otherStack) { if (this != &otherStack) //avoid self-copy copyStack(otherStack); return *this; } //end operator=

#endif // STACKADT_H_INCLUDED

#endif // LINKEDLISTTYPE_H_INCLUDED you'r HOMEWORK is to do the following :

Write the implementation of the following member functions to deal with a linked list: 1. Modify the implementation of the member function search so that it returns a pointer to the node if the node info is found in the list and NULL otherwise. 2. Modify the implementation of the member function print and rewrite it using recursion. 3. ReversePrint1: this function should use recursion to print the elements of the linkedlist in the reverse order. 4. ReversePrint2: this function should use stackType to print the elements of the linkedlist in the reverse order. 5. insertAt: this function inserts a new node in the location specified in the parameter list. 6. insertAfter: this function adds a new node after the node with the value specified in the parameter list. 7. A function to overload [] operator, that returns a pointer to the ith node in the linked list.