This C++ program consists of Data Structures concepts, in particular, using Linked Lists. The program is built. All that has to be done is add two more functions: one that inserts from middle, and one that removes from middle. You will need to do a walkthrough in order to achieve this. Here are the instructions:

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:

insertMiddle

removeMiddle

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); // attempts to insert the value 345 // as the 5th item in the list L.removeMiddle(x, 10); // attempts to delete the 10th item in the // list and captures its value into x. 

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), insert at the front. For removeMiddle, return false if the position is invalid (without removing anything).

Here is "list.h":

#ifndef LIST_H #define LIST_H #include  using std::cout; #include  #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; 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 ... "; 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 << ' '; currentPtr = currentPtr->nextPtr; delete tempPtr; } } // cout << "All nodes destroyed "; } // 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 "; return; } // end if ListNode< NODETYPE > *currentPtr = firstPtr; cout << "The list is: "; while ( currentPtr != 0 ) { cout << currentPtr->data << ' '; currentPtr = currentPtr->nextPtr; } // end while cout << " "; } // end function print #endif 

and here's the file (listnode.h) that's included in list.h:

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

You can use this program to test your class:

#include  using std::cin; using std::endl; #include  using std::string; #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 "; instructions(); // display instructions int choice; T value; int pos; do { cout << "? "; cin >> choice; 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 "; listObject.print(); break; case 5: if ( listObject.removeFromBack( value ) ) cout << value << " removed from list "; listObject.print(); break; case 6: cout << "Enter position to delete: "; cin >> pos; if ( listObject.removeMiddle( value, pos ) ) cout << value << " removed from list "; listObject.print(); break; } // end switch } while ( choice != 7 ); // end do/while cout << "End list test "; } // end function testList // display program instructions to user void instructions() { cout << "Enter one of the following: " << " 1 to insert at beginning of list " << " 2 to insert at end of list " << " 3 to insert at anywhere in the list " << " 4 to delete from beginning of list " << " 5 to delete from end of list " << " 6 to delete from anywhere in the list " << " 7 to end list processing "; } // 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