I have an assignment to build a linked list which can insert items in a sorted order... however I haven't been fully successful. I can insert items at the beginning and the end with no problem, but the middle is proving more difficult.

I'm sure I know what the problem is and where it exist in the program... I'm just not sure of how to correct it. Currently, my code seems to find the correct place to insert the new node... but it puts the new node before the one being evaluated... I need it to place it after it instead. I'm sure it is something simple that I'm missing but its driving me crazy and i"m running out of time.

I must apologize ahead of time... I have quit a few unneeded print() statements... I left them there though so the problem can be a lil more easily seen when trying to run the program.

Below is all my code... any help would be appreciated. I'd like to understand where I went wrong.

The problem lies here in Week5-6Program.cpp
Code:
//-----------------------The problem lies here--------------------------------------------
     if(ptr->data > newPtr->data){ // Item is > than ptr
       newPtr->nextPtr = ptr->nextPtr;  // Insert item after ptr
       ptr->nextPtr = newPtr;
       cout << "\n" << value << " belongs before " << ptr->data << " in middle of list\n";
       print();
       break;
       }//end if
//----------------------------------------------------------------------------------------
list_node.h
Code:
// Exercise 21.6 Solution: ListNode.h
// ListNode class template definition
#ifndef LISTNODE_H
#define LISTNODE_H

template< typename T > class ABook; // forward declaration

template< typename NODETYPE >
class AddressNode 
{
     friend class ABook< NODETYPE >; // make ABook a friend
  public:
    AddressNode( const NODETYPE & ); // constructor
    NODETYPE getData() const; // return the data in the node

// set nextPtr to nPtr
void setNextPtr( AddressNode *nPtr ) 
{ 
  nextPtr = nPtr; 
} // end function setNextPtr
   
// return nextPtr
AddressNode *getNextPtr() const 
{ 
  return nextPtr; 
} // end function getNextPtr

private:
   NODETYPE data; // data
   AddressNode *nextPtr; // next node in the ABook
   AddressNode *prevPtr; // points to node before
}; // end class AddressNode

// constructor
template< typename NODETYPE >
AddressNode< NODETYPE >::AddressNode( const NODETYPE &info )
{
   data = info;
   nextPtr = NULL;
   prevPtr = NULL;
} // end constructor

// return a copy of the data in the node
template< typename NODETYPE >
NODETYPE AddressNode< NODETYPE >::getData() const 
{ 
   return data; 
} // end function getData

#endif
Code:
#ifndef ABook_H
#define ABook_H
#include <iostream> 
#include <new>
#include<string>

#include "list_node.h"

using namespace std; 

template< typename NODETYPE >
class ABook 
{
  public:
    ABook(); // default constructor
    ~ABook(); // destructor

    void Insert( const NODETYPE & );//inserts at beginning of list
    void SortedInsert( const NODETYPE & );//inserts in Acending order
    bool Remove( NODETYPE & );//pops value from front of list and prints it to the screen

    bool empty() const;//checks to see if a list contains any nodes
    void print() const;//prints list
  private:
    AddressNode< NODETYPE > *topPtr; // pointer to first node
    AddressNode< NODETYPE > *lastPtr; // pointer to last node
    AddressNode< NODETYPE > *getNewNode( const NODETYPE & );// create new node
}; // end class template ABook

// default constructor
template< typename NODETYPE >
ABook< NODETYPE >::ABook() 
{ 
   topPtr = lastPtr = NULL; 
} // end constructor

// destructor
template< typename NODETYPE >
ABook< NODETYPE >::~ABook()
{
  if (!empty()){ // ABook is not empty
    AddressNode< NODETYPE > *currentPtr = topPtr;
    AddressNode< NODETYPE > *tempPtr;
    while ( currentPtr != 0 ){ // delete remaining nodes
      tempPtr = currentPtr;
      cout << "Destroying: " << tempPtr->data << '\n';
      currentPtr = currentPtr->nextPtr;
      delete tempPtr;
      } 
    } 
    cout << "\nDestructor Successful: All nodes destroyed\n\n";
    system("pause");//shows that destructor was successful
} // end destructor

// Insert a node at the front of the list
template< typename NODETYPE >
void ABook< NODETYPE >::Insert( const NODETYPE &value )
{
   AddressNode<NODETYPE> *newPtr = getNewNode( value );

   if ( empty() ){ 
   // checks to see if the list is empty if it is, inserts at front
      topPtr = lastPtr = newPtr;
      }
   else{ 
   //if its not empty insert at beginning and push everything else right
      newPtr->nextPtr = topPtr;
      topPtr = newPtr;

   } // end else
} // end function Insert

//Insert a node in order
template< typename NODETYPE >
void ABook< NODETYPE >::SortedInsert( const NODETYPE &value )
{
  AddressNode< NODETYPE > *newPtr = getNewNode(value);
 
  cout << "\nAfter inserting: " << value << "";
  if (empty()){
  //if there is nothing on the list yet make it the first node
    lastPtr = topPtr = newPtr;
    cout << "\n" << value << " is first item on list\n";
    print();
    }
  else if(newPtr->data < topPtr->data){
  //if new data is less than first element, insert as first element and push everything else right (assumes list is sorted)
    newPtr->nextPtr = topPtr;
    topPtr = newPtr;
    cout << "\n" << value << " belongs at front of List\n";
    print();
    }
  else{
   for( AddressNode< NODETYPE > *ptr = topPtr; ptr != NULL; ptr = ptr->nextPtr ){
//iterate through list till the proper place is found to insert the new item
//-----------------------The problem lies here--------------------------------------------
     if(ptr->data > newPtr->data){ // Item is > than ptr
       newPtr->nextPtr = ptr->nextPtr;  // Insert item after ptr
       ptr->nextPtr = newPtr;
       cout << "\n" << value << " belongs before " << ptr->data << " in middle of list\n";
       print();
       break;
       }//end if
//----------------------------------------------------------------------------------------
     if( ptr->nextPtr == NULL ){
//If it is the greatest value in the list, place it at the end
       lastPtr = ptr->nextPtr = newPtr;       // Insert at end
       newPtr->nextPtr = NULL;
       cout << "\n" << value << " belongs at end of list\n";
       print();
       }
   }//end for
 }//end if

}//end sortedinsert

// Delete a node from the front of the ABook
template< typename NODETYPE >
bool ABook< NODETYPE >::Remove( NODETYPE &value )
{
   if ( empty() ) // ABook is empty
      return false; // delete unsuccessful
   else 
   {
      AddressNode< NODETYPE > *tempPtr = topPtr;

      if ( topPtr == lastPtr )
         topPtr = lastPtr = NULL;
      else
         topPtr = topPtr->nextPtr;

      value = tempPtr->data; // data being removed

      delete tempPtr;
      return true; // delete successful
   } // end else
} // end function remove

// Is the ABook empty?
template< typename NODETYPE >
bool ABook< NODETYPE >::empty() const 
{ 
   return topPtr == NULL; 
} // end function isEmpty

// assigns pointer to a new node
template< typename NODETYPE >
AddressNode< NODETYPE > *ABook< NODETYPE >::getNewNode(const NODETYPE &value)
{
   AddressNode< NODETYPE > *ptr = new AddressNode< NODETYPE >( value );
   return ptr;
} // end function getNewNode


template< typename NODETYPE >
void ABook< NODETYPE >::print() const
{//Prints linked list
  if ( empty() ){ // empty ABook
    cout << "The ABook is empty\n";
    return;
    }
  AddressNode< NODETYPE > *currentPtr = topPtr;

  cout << "The ABook is:\n";

  while ( currentPtr != NULL ){ 
  // cycle through nodes until the end is reached
    cout << currentPtr->data << '\n';
    currentPtr = currentPtr->nextPtr;
    }
} // end function print
#endif

//----------------------------Week5-6Program.cpp-------------------------------
int main()
{
   ABook< string > Book; // storage for first ABook
   string newName[4] = {"Ken","Eileen","Frank","Precious"};//this does
   string nameToRemove[4] = {"Precious","Ken","Eileen","Frank"};//this doesn't use 4 names

cout << "input order: \n";   
   for(int i = 0; i < 4; i++)
     cout << newName[i] << '\n';
cout << '\n';   

     Book.SortedInsert(newName[0]);
     Book.SortedInsert(newName[1]);
     Book.SortedInsert(newName[2]);
     Book.SortedInsert(newName[3]); 
     Book.SortedInsert("Herman");
   
   cout << "\nFinal list is: \n";  
   Book.print();
   system("pause");
   return 0; // indicates successful termination
} // end main