2008 Pearson Education, Inc. All Rights Reserved.

1// Fig. 20.3: Listnode.h2// Template ListNode class definition.34#ifndef LISTNODE H#define LISTNODE H156789// forward declaration of class List required to announce that class// List exists so it can be used in the friend declaration at line 13template typename NODETYPE class List;10 template typename NODETYPE 11 class ListNode12 {131415161718192021222324Declare class List NODETYPE as a friendfriend class List NODETYPE ; // make List a friendpublic:ListNode( const NODETYPE & ); // constructorNODETYPE getData() const; // return data in nodeprivate:NODETYPE data; // dataListNode NODETYPE *nextPtr; // next node in list}; // end class ListNode// constructortemplate typename NODETYPE Member data stores a value oftype parameter NODETYPEMember nextPtr stores a pointer to thenext ListNode object in the linked list25 ListNode NODETYPE ::ListNode( const NODETYPE &info )26: data( info ), nextPtr( 0 )27 {28// empty body29 } // end ListNode constructor 2008 Pearson Education,Inc. All rights reserved.

3031 // return copy of data in node32 template typename NODETYPE 233 NODETYPE ListNode NODETYPE ::getData() const34 {35return data;36 } // end function getData3738 #endif 2008 Pearson Education,Inc. All rights reserved.

1// Fig. 20.4: List.h23// Template List class definition.#ifndef LIST H45678#define LIST H910111213#include "listnode.h" // ListNode class definition3#include iostream using std::cout;template typename NODETYPE class List{14 public:15List(); // constructor16 List(); // destructor17void insertAtFront( const NODETYPE & );18void insertAtBack( const NODETYPE & );19bool removeFromFront( NODETYPE & );private data members firsrtPtr (a pointer to20bool removeFromBack( NODETYPE & );the first ListNode in a List) and lastPtr (a21bool isEmpty() const;pointer to the last ListNode in a List)22void print() const;23 private:24ListNode NODETYPE *firstPtr; // pointer to first node2526272829 };30ListNode NODETYPE *lastPtr; // pointer to last node// utility function to allocate new nodeListNode NODETYPE *getNewNode( const NODETYPE & );// end class ListThis private utilityfunction is the keyto the ‘friendship’. 2008 Pearson Education,Inc. All rights reserved.

31 // default constructor432 template typename NODETYPE 33 List NODETYPE ::List()34: firstPtr( 0 ), lastPtr( 0 )35 {36// empty bodyInitialize both pointers to 0 (null)37 } // end List constructor3839 // destructor40 template typename NODETYPE 41 List NODETYPE :: List()42 {4344454647484950515253545556575859if ( !isEmpty() ) // List is not empty{cout "Destroying nodes .\n";ListNode NODETYPE *currentPtr firstPtr;ListNode NODETYPE *tempPtr;while ( currentPtr ! 0 ) // delete remaining nodes{tempPtr currentPtr;cout tempPtr- data '\n';currentPtr currentPtr- nextPtr;delete tempPtr;} // end while} // end ifEnsure that all ListNode objects ina List object are destroyed whenthat List object is destroyedcout "All nodes destroyed\n\n";60 } // end List destructor 2008 Pearson Education,Inc. All rights reserved.

6162 // insert node at front of list63 template typename NODETYPE 64 void List NODETYPE ::insertAtFront( const NODETYPE &value )65 {Use function getNewNode toallocate a new ListNodecontaining value andassign it to newPtr66ListNode NODETYPE *newPtr getNewNode( value ); // new node6768if ( isEmpty() ) // List is empty697071firstPtr lastPtr newPtr; // new list has only one nodeelse // List is not empty{727374newPtr- nextPtr firstPtr; // point new node to previous 1stfirstPtr newPtr; // aim firstPtr at new node} // end elseThread the75 } // end function insertAtFront7677787980If the list is empty, then bothfirstPtr and lastPtrnode are set to newPtrnew node into the list so thatthe new node points to the old first nodeandbackfirstPtrpoints to the new nodePlaces a new node at theof the list// insert node at back of listtemplate typename NODETYPE void List NODETYPE ::insertAtBack( const NODETYPE &value ){81828384ListNode NODETYPE *newPtr getNewNode( value ); // new node8586878889else // List is not empty{lastPtr- nextPtr newPtr; // update previous last nodelastPtr newPtr; // new last node} // end elseif ( isEmpty() ) // List is emptyfirstPtr lastPtr newPtr; // new list has only one node90 } // end function insertAtBack5Places a new node at the front of the listUse function getNewNode toallocate a new listNodecontaining value andassign it to newPtrIf the list is empty, then bothfirstPtr and lastPtrare set to newPtrThread the new node into the list so thatthe old last node points to the new node 2008 Pearson Education,and lastPtr points to the new nodeInc. All rights reserved.

9192939495Removes the front node of the list and copiesvalue to the reference parameter// delete node from front of listthe nodetemplate typename NODETYPE bool List NODETYPE ::removeFromFront( NODETYPE &value ){969798if ( isEmpty() ) // List is emptyreturn false; // delete unsuccessfulelse99100101{6Return false if an attempt is made toremove a node from an empty listSave a pointer to the first node,which will be removedListNode NODETYPE *tempPtr firstPtr; // hold tempPtr to delete102103104105if ( firstPtr lastPtr )firstPtr lastPtr 0; // no nodes remain after removalelsefirstPtr firstPtr- nextPtr; // point to previous 2nd node106107108value tempPtr- data; // return data being removeddelete tempPtr; // reclaim previous front node109return true; // delete successful110} // end else111 } // end function removeFromFrontIf the list has only one element,leave the list emptySet firstPtr to pointto the second node(the new first node)Copy the removed node’sdata to referenceparameter value112delete the removed node 2008 Pearson Education,Inc. All rights reserved.

113 // delete node from back of list114 template typename NODETYPE 115 bool List NODETYPE ::removeFromBack( NODETYPE &value )Return false if an attempt is made to116 {117118119120121122123124if ( isEmpty() ) // List is emptyremove a node from an empty listreturn false; // delete unsuccessfulelse{Save a pointer to the last node,ListNode NODETYPE *tempPtr lastPtr; // hold tempPtr to delete which will be removedif ( firstPtr lastPtr ) // List has one elementfirstPtr lastPtr 0; // no nodes remain after removal125else126127{128129130131132133Removes the back node of the list and copies7the node value to the reference parameterAssign currentPtr theaddress of the first node toprepare to “walk the list”ListNode NODETYPE *currentPtr firstPtr;// locate second-to-last elementwhile ( currentPtr- nextPtr ! lastPtr )currentPtr currentPtr- nextPtr; // move to next“Walknodethe list” until currentPtrpoints to the node before the lastnode, which will be the new last nodelastPtr currentPtr; // remove last node134135currentPtr- nextPtr 0; // this is now the last node} // end else136137value tempPtr- data; // return value from old last node138139140If the list has only one element,leave the list emptydelete tempPtr; // reclaim former last nodereturn true; // delete successful} // end elseMake the currentPtrnode the new last nodeCopy the removed node’s datato reference parameter valuedelete the removed node 2008 Pearson Education,Inc. All rights reserved.

141 } // end function removeFromBack8142143 // is List empty?144 template typename NODETYPE 145 bool List NODETYPE ::isEmpty() const146 {147return firstPtr 0;Determine whether theList is empty148 } // end function isEmpty149150 // return pointer to newly allocated node151 template typename NODETYPE 152 ListNode NODETYPE *List NODETYPE ::getNewNode(153const NODETYPE &value )154 {155return new ListNode NODETYPE ( value );Return a dynamically allocatedListNode object156 } // end function getNewNode157158 // display contents of List159 template typename NODETYPE 160 void List NODETYPE ::print() const161 {162if ( isEmpty() ) // List is empty163{164cout "The list is empty\n\n";165return;166} // end if 2008 Pearson Education,Inc. All rights reserved.

1671689ListNode NODETYPE *currentPtr firstPtr;169170171172173174175cout "The list is: ";while ( currentPtr ! 0 ) // get element data{cout currentPtr- data ' ';currentPtr currentPtr- nextPtr;Iterate through the list andoutput the value in each node176} // end while177178cout "\n\n";179 } // end function print180181 #endif 2008 Pearson Education,Inc. All rights reserved.

1// Fig. 20.5: Fig20 05.cpp2// List class test program.3#include iostream 456using std::cin;using std::cout;using std::endl;78#include string 109 using std::string;1011 #include "List.h" // List class definition1213 // function to test a List14 template typename T 15 void testList( List T &listObject, const string &typeName )16 {1718cout "Testing a List of " typeName " values\n";instructions(); // display instructions1920int choice; // store user choice2122T value; // store input value23242526do // perform user-selected actions{cout "? ";cin choice;27 2008 Pearson Education,Inc. All rights reserved.

282930switch ( choice ){case 1: // insert at beginning31cout "Enter " typeName ": ";32333435cin value;listObject.insertAtFront( value );listObject.print();break;3637case 2: // insert at endcout "Enter " typeName ": ";38cin value;394041424344listObject.insertAtBack( value );listObject.print();break;case 3: // remove from beginningif ( listObject.removeFromFront( value ) )cout value " removed from list\n";45464748listObject.print();break;case 4: // remove from end495051if ( listObject.removeFromBack( value ) )cout value " removed from list\n";52listObject.print();5354555611break;} // end switch} while ( choice ! 5 ); // end do.while 2008 Pearson Education,Inc. All rights reserved.

57cout "End list test\n\n";58 } // end function testList125960 // display program instructions to user61 void instructions()62 {6364cout "Enter one of the following:\n" " 1 to insert at beginning of list\n"65 "2 to insert at end of list\n"666768 " " "3 to delete from beginning of list\n"4 to delete from end of list\n"5 to end list processing\n";69 } // end function instructions7071 int main()72 {73747576777879// test List of int valuesList int integerList;testList( integerList, "integer" );// test List of double valuesList double doubleList;testList( doubleList, "double" );80return 0;81 } // end main 2008 Pearson Education,Inc. All rights reserved.

13Testing a List of integer valuesEnter one of the following:1 to insert at beginning of list2 to insert at end of list3 to delete from beginning of list4 to delete from end of list5 to end list processing? 1Enter integer: 1The list is: 1? 1Enter integer: 2The list is: 2 1? 2Enter integer: 3The list is: 2 1 3? 2Enter integer: 4The list is: 2 1 3 4? 32 removed from listThe list is: 1 3 4(continued at top of next slide. ) 2008 Pearson Education,Inc. All rights reserved.

(.continued from bottom of previous slide)14? 31 removed from listThe list is: 3 4? 44 removed from listThe list is: 3? 43 removed from listThe list is empty? 5End list testTesting a List of double valuesEnter one of the following:1 to insert at beginning of list2 to insert at end of list3 to delete from beginning of list4 to delete from end of list5 to end list processing? 1Enter double: 1.1The list is: 1.1? 1Enter double: 2.2The list is: 2.2 1.1(continued at top of next slide. ) 2008 Pearson Education,Inc. All rights reserved.

(.continued from bottom of previous slide)15? 2Enter double: 3.3The list is: 2.2 1.1 3.3? 2Enter double: 4.4The list is: 2.2 1.1 3.3 4.4? 32.2 removed from listThe list is: 1.1 3.3 4.4? 31.1 removed from listThe list is: 3.3 4.4? 44.4 removed from listThe list is: 3.3? 43.3 removed from listThe list is empty? 5End list testAll nodes destroyedAll nodes destroyed 2008 Pearson Education,Inc. All rights reserved.

2008 Pearson Education, Inc. All rights reserved. 1 1 // Fig. 20 .3: Listnode.h 2 //