MAIN Driver include iostream using std cin using std endl include string using std string int choice T value int pos do cout cin choice include list h List class definition void instructions function to test a List template class T void testList List T listObject const string typeName cout Testing a List of typeName values n instructions display instructions switch choice case 1 cout Enter typeName cin value listObject insertAtFront value listObject print break case 2 cout Enter typeName cin value listObject insertAtBack value listObject print break case 3 cout Enter typeName cin value cout Enter position to insert cin pos listObject insertMiddle value pos listObject print break case 4 if listObject removeFromFront value cout value removed from list n listObject print break case 5 if listObject removeFromBack value cout value removed from list n listObject print break case 6 if listObject removeMiddle value pos cout value removed from list n cout Enter position to delete cin pos listObject print break end switch while choice 7 end do while cout End list test n n end function testList display program instructions to user void instructions cout Enter one of the following n 1 to insert at beginning of list n 2 to insert at end of list n 3 to insert at anywhere in the list n 4 to delete from beginning of list n 5 to delete from end of list n 6 to delete from anywhere in the list n 7 to end list processing n end function instructions int main test List of int values List int integerList testList integerList integer test List of double values List double doubleList testList doubleList double return 0 end main END MAIN H ifndef LIST H define LIST H include iostream using std cout include new include listnode h ListNode class definition template class NODETYPE 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 void insertMiddle NODETYPE int bool removeMiddle NODETYPE int private ListNode NODETYPE firstPtr pointer to first node ListNode NODETYPE lastPtr pointer to last node utility function to allocate new node ListNode NODETYPE getNewNode const NODETYPE end class List default constructor template class NODETYPE List NODETYPE List firstPtr 0 lastPtr 0 empty body end List constructor destructor template class NODETYPE List NODETYPE List if isEmpty List is not empty cout Destroying nodes n ListNode NODETYPE currentPtr firstPtr ListNode NODETYPE tempPtr while currentPtr 0 delete remaining nodes tempPtr currentPtr commented out the output no need to print what we are deallocating cout tempPtr data n currentPtr currentPtr nextPtr delete tempPtr cout All nodes destroyed n n end List destructor insert node at front of list template class NODETYPE void List NODETYPE insertAtFront const NODETYPE value ListNode NODETYPE 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 class NODETYPE void List NODETYPE insertAtBack const NODETYPE value ListNode NODETYPE 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 class NODETYPE bool List NODETYPE removeFromFront NODETYPE value if isEmpty List is empty return false delete unsuccessful else ListNode NODETYPE 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 class NODETYPE bool List NODETYPE removeFromBack NODETYPE value if isEmpty return false delete unsuccessful else ListNode NODETYPE tempPtr lastPtr if firstPtr lastPtr firstPtr lastPtr 0 else ListNode NODETYPE 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 class NODETYPE bool List NODETYPE isEmpty const return firstPtr 0 end function isEmpty return pointer to newly allocated node template class NODETYPE ListNode NODETYPE List NODETYPE getNewNode const NODETYPE value return new ListNode NODETYPE value end function getNewNode display contents of List template class NODETYPE void List NODETYPE print const if isEmpty cout The list is empty n n return end if ListNode NODETYPE currentPtr firstPtr cout The list is while currentPtr 0 cout currentPtr data currentPtr currentPtr nextPtr end while cout n n end function print template class NODETYPE void List NODETYPE insertMiddle NODETYPE value int num ListNode NODETYPE newPtr getNewNode value if isEmpty firstPtr lastPtr newPtr else if num 0 newPtr nextPtr firstPtr firstPtr newPtr else ListNode NODETYPE loopPtr firstPtr num for int i 0 i num loopPtr i loopPtr loopPtr nextPtr if loopPtr loopPtr nextPtr lastPtr nextPtr newPtr lastPtr newPtr else newPtr nextPtr loopPtr nextPtr loopPtr nextPtr newPtr template class NODETYPE bool List NODETYPE removeMiddle NODETYPE value int num bool glag falsel if isEmpty return false if num 0 return false ListNode NODETYPE tmpPtr firstPtr if num 0 if firstPtr lastPtr firstPtr lastPtr 0 else firstPtr firstPtr nextPtr else num ListNode NODETYPE loopPtr firstPtr flag true for int i 0 i num flag i if loopPtr nextPtr loopPtr nextPtr nextPtr loopPtr loopPtr nextPtr else flag false if flag loopPtr nextPtr return false if loopPtr nextPtr lastPtr tmpPtr lastPtr loopPtr nextPtr 0 lastPtr loopPtr else tmpPtr loopPtr nextPtr loopPtr nextPtr loopPtr nextPtr nextPtr endif ifndef STACK H define STACK H value tmpPtr getData delete tmpPtr return true include list h List class definition template class STACKTYPE class Stack private List STACKTYPE public push calls List function insertAtFront void push const STACKTYPE data insertAtFront data end function push pop calls List function removeFromFront bool pop STACKTYPE data return removeFromFront data end function pop isStackEmpty calls List function isEmpty bool isStackEmpty const return this isEmpty end function isStackEmpty printStack calls List function print void printStack const this print end function