Adding To The Middle Of A Linked List

Hi I have a singly linked list and know how to add to the end of it but am unsure of how to add it to the linked list so that a node is placed inbetween nodes of similar CustomerNumber, I even have the locate node function to find a node witha similar customer number, im just unsure how to modify the add function to place it it either before or after that node.. If there are any simple modifications that i could make, it would be much appreciated

Code:

---

class Orders
{
        public:
                long CustomerNumber;
                string PartCode;
                string PaymentType;
                string CCType;
                string CCNumber;
                string NameOnCard;                       
                string ExpiryDate;
                bool CompletionStatus;
                long OrderNumber;
       
                Orders* next;
                Orders(long, string, string, string, string, string, string, bool, long, Orders*);
                ~Orders();
        private:
};

Orders::Orders(long tempCustomerNumber, string tempPartCode, string tempPaymentType,
                                string tempCCType, string tempCCNumber, string tempNameOnCard,
                                string tempExpiryDate, bool tempCompletionStatus, long tempOrderNumber,
                                Orders* tempNext):CustomerNumber(tempCustomerNumber), PartCode(tempPartCode),
                                PaymentType(tempPaymentType), CCType(tempCCType), CCNumber(tempCCNumber),
                                NameOnCard(tempNameOnCard), ExpiryDate(tempExpiryDate),
                                CompletionStatus(tempCompletionStatus), OrderNumber(tempOrderNumber),
                                next(tempNext){}

Orders::~Orders(){}

typedef Orders* OrdersPtr;
OrdersPtr locateNodeCutomerNumber(OrdersPtr temp, string eCustomerNumber);

//finds a node witha  matching customernumber
OrdersPtr locateNodeCutomerNumber(OrdersPtr temp, string eCustomerNumber);
{
        while (temp != NULL)
        {
                if (temp->CustomerNumber== eCustomerNumber)
                {
                        return temp;
                }
                temp = temp->next;
        }
        return NULL;
}

void fnAddOrder(OrdersPtr &root3) //root 3 is the last item in the linked list
{
        string ePartCode, ePaymentType, eCCType, eCCNumber, eNameOnCard, eExpiryDate;
        long eCustomerNumber, eOrderNumber;
        bool eCompletionStatus;

        cin.ignore(500,'\n');
        cout << "Customer Number:\t\t\t";
        getline(cin, eCustomerNumber, '\n');

        cout << "PartCode:\t\t\t";
        getline(cin, ePartCode, '\n');

        cout << "Payment Type:\t\t\t";
        getline(cin,ePaymentType, '\n');

        cout << "Credit Card Type:\t\t\t";
        getline(cin,eCCType, '\n');

        cout << "Credit Card Number:\t\t\t";
        getline(cin, eCCNumber, '\n');

        cout << "Name on Credit Card:\t\t\t";
        getline(cin, eNameOnCard, '\n');

        cout << "Would you like to Complete This Order Now (1-yes, 0 no):\t\t\t";
        getline(cin, eCompletionStatus, '\n');

        cout << "Order Number:\t\t\t";
        getline(cin, eOrderNumber, '\n');

        root3 = new Orders(eCustomerNumber, ePartCode, ePaymentType, eCCType, eCCNumber, eNameOnCard, eExpiryDate, eCompletionStatus, eOrderNumber, root3);

        system("cls");
       
}

---

To insert a node in a singly linked list, just walk down the list until you find the point you want to add at and insert it, like this:

Code:

---

node *insert ( node *list, int val )
{
  node *new_node = new node ( val, 0 );

  // Empty list
  if ( list == NULL )
    return new_node;
  // Add at the front
  else if ( list->data > val ) {
    new_node->next = list;
    list = new_node;
  }
  // Everything else
  else {
    node *walk;

    for ( walk = list; walk->next != NULL; walk = walk->next ) {
      if ( walk->next->data > val )
        break;
    }

    new_node->next = walk->next;
    walk->next = new_node;
  }

  return list;
}

---

-Prelude