// Fig. 21.3: listnode.h // Template ListNode class definition. #ifndef LISTNODE_H #define LISTNODE_H // forward declaration of class List template class List; template class ListNode { friend class List; // make List a friend public: ListNode( const NODETYPE & ); // constructor NODETYPE getData() const; // return data in node private: NODETYPE data; // data ListNode *nextPtr; // next node in list }; // end class ListNode // constructor template ListNode::ListNode( const NODETYPE &info ) : data( info ), nextPtr( 0 ) { // empty body } // end ListNode constructor // return copy of data in node template NODETYPE ListNode::getData() const { return data; } // end function getData #endif 

/*----------------------------------------------------------------------------------------------- LIST.H ---------------------------------------------------------------------------------------*/

// Fig. 21.4: list.h // Template List class definition. #ifndef LIST_H #define LIST_H #include  using std::cout; #include  #include "listnode.h" // ListNode class definition template class List { public: List(); // constructor ~List(); // destructor void insertAtFront( const NODETYPE & ); void insertAtBack( const NODETYPE & ); bool removeFromFront( NODETYPE & ); bool removeFromBack( NODETYPE & ); bool isEmpty() const; void print() const; private: ListNode *firstPtr; // pointer to first node ListNode *lastPtr; // pointer to last node // utility function to allocate new node ListNode *getNewNode( const NODETYPE & ); }; // end class List // default constructor template List::List() : firstPtr( 0 ), lastPtr( 0 ) { // empty body } // end List constructor // destructor template List::~List() { if ( !isEmpty() ) { // List is not empty // cout  *currentPtr = firstPtr; ListNode *tempPtr; while ( currentPtr != 0 ) // delete remaining nodes { tempPtr = currentPtr; // commented out the output -- no need to print what we are deallocating // cout data nextPtr; delete tempPtr; } } // cout  void List::insertAtFront( const NODETYPE &value ) { ListNode *newPtr = getNewNode( value ); if ( isEmpty() ) // List is empty firstPtr = lastPtr = newPtr; else { // List is not empty newPtr->nextPtr = firstPtr; firstPtr = newPtr; } // end else } // end function insertAtFront // insert node at back of list template void List::insertAtBack( const NODETYPE &value ) { ListNode *newPtr = getNewNode( value ); if ( isEmpty() ) // List is empty firstPtr = lastPtr = newPtr; else { // List is not empty lastPtr->nextPtr = newPtr; lastPtr = newPtr; } // end else } // end function insertAtBack // delete node from front of list template bool List::removeFromFront( NODETYPE &value ) { if ( isEmpty() ) // List is empty return false; // delete unsuccessful else { ListNode *tempPtr = firstPtr; if ( firstPtr == lastPtr ) firstPtr = lastPtr = 0; else firstPtr = firstPtr->nextPtr; value = tempPtr->data; // data being removed delete tempPtr; return true; // delete successful } // end else } // end function removeFromFront // delete node from back of list template bool List::removeFromBack( NODETYPE &value ) { if ( isEmpty() ) return false; // delete unsuccessful else { ListNode *tempPtr = lastPtr; if ( firstPtr == lastPtr ) firstPtr = lastPtr = 0; else { ListNode *currentPtr = firstPtr; // locate second-to-last element while ( currentPtr->nextPtr != lastPtr ) currentPtr = currentPtr->nextPtr; lastPtr = currentPtr; currentPtr->nextPtr = 0; } // end else value = tempPtr->data; delete tempPtr; return true; // delete successful } // end else } // end function removeFromBack // is List empty? template bool List::isEmpty() const { return firstPtr == 0; } // end function isEmpty // return pointer to newly allocated node template ListNode *List::getNewNode( const NODETYPE &value ) { return new ListNode( value ); } // end function getNewNode // display contents of List template void List::print() const { if ( isEmpty() ) { cout  *currentPtr = firstPtr; cout data nextPtr; } // end while cout  
 *---------------------------------------------------------------------------------------------------- STACK.H ---------------------------------------------------------------------------------------*/
 
 
 
// Fig. 21.15: Stackcomposition.h // Template Stack class definition with composed List object. #ifndef STACKCOMPOSITION_H #define STACKCOMPOSITION_H #include "list.h" // List class definition template class Stack { public: // no constructor; List constructor does initialization // push calls stackList object's insertAtFront member function void push( const STACKTYPE &data ) { stackList.insertAtFront( data ); } // end function push // pop calls stackList object's removeFromFront member function bool pop( STACKTYPE &data ) { return stackList.removeFromFront( data ); } // end function pop // isStackEmpty calls stackList object's isEmpty member function bool isStackEmpty() const { return stackList.isEmpty(); } // end function isStackEmpty // printStack calls stackList object's print member function void printStack() const { stackList.print(); } // end function printStack private: List stackList; // composed List object }; // end class Stack #endif 
 
 
 
PROGRAM QUESTION
 
  Modify the List class (file list.h so that it has two more functions, which will allow inserts and removes from anywhere in the linked list. Your functions should be called: insertkiddle romoveMiddle Your functions should have all the same features as the given insert and remove functions, except that yours each have one extra parameter. The second parameter on each of your functions should be of type int representing the position at which to insert (or delete). Sample calls for a list of integers: L.insertMiddle(345, 5)1 Iattempts to insert the value 345 // as the 5th item in the list 5th Bert // attempts to delete the 10th item in the / list and captures its value into x. L.removeMiddle(, 10) For insertMiddle, if the position number is larger than the number of items in the list, just insert the item at the back. If it's too small (i.e. 0 or less), nsert at the front. For removeMiddle, return false if the position is invalid (without removing anything)