I'm trying to add insert functionality to a textbook code example. I have an "off by one" error and I can't think of a way to fix it. Here's my attempt below:
template< class NODETYPE >
void List< NODETYPE >::insertMiddle( const NODETYPE &value, int position )
{
ListNode< NODETYPE > *newPtr = getNewNode( value );
ListNode< NODETYPE > *curr = firstPtr;
ListNode< NODETYPE > *curr2 = firstPtr;
if ( isEmpty() )
firstPtr = lastPtr = newPtr;
else {
if (position == 1)
insertAtFront( value );
cout << "curr->data is: "<<curr->data<<endl;
for (int i = 1; i != position; ++i)
curr = curr->nextPtr;
newPtr->nextPtr = curr->nextPtr;
curr->nextPtr = newPtr;
//curr = newPtr;
cout << "curr->data is: "<<curr->data<<endl;
cout << "curr->nextPtr->data is: "<<curr->nextPtr->data<<endl;
}
}
LIST.H --------------
// Fig. 21.4: list.h
// Template List class definition.
#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 & );
void insertMiddle( const NODETYPE &, int);
bool removeFromFront( NODETYPE & );
bool removeFromBack( NODETYPE & );
bool removeMiddle( NODETYPE &, int );
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 ...\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
template< class NODETYPE >
void List< NODETYPE >::insertMiddle( const NODETYPE &value, int position )
{
ListNode< NODETYPE > *newPtr = getNewNode( value );
ListNode< NODETYPE > *curr = firstPtr;
ListNode< NODETYPE > *curr2 = firstPtr;
if ( isEmpty() )
firstPtr = lastPtr = newPtr;
else {
if (position == 1)
insertAtFront( value );
cout << "curr->data is: "<<curr->data<<endl;
for (int i = 1; i != position; ++i)
curr = curr->nextPtr;
newPtr->nextPtr = curr->nextPtr;
curr->nextPtr = newPtr;
//curr = newPtr;
cout << "curr->data is: "<<curr->data<<endl;
cout << "curr->nextPtr->data is: "<<curr->nextPtr->data<<endl;
}
}
// 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
template<class NODETYPE >
bool List< NODETYPE >::removeMiddle( NODETYPE &value, int position )
{
return true;
}
// 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
#endif
Menu8.cpp
// Test program for HW 8
//
#include <iostream>
using std::cin;
using std::endl;
#include <string>
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\n";
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\n";
listObject.print();
break;
case 5:
if ( listObject.removeFromBack( value ) )
cout << value << " removed from list\n";
listObject.print();
break;
case 6:
cout << "Enter position to delete: ";
cin >> pos;
if ( listObject.removeMiddle( value, pos ) )
cout << value << " removed from list\n";
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