Linked List issue insert from middle C++

Question

I am new to linked lists, and now I face a problem on how to add the node into the middle of a list. Example like if I got a name list show below and when I add data one by one just like below sequence:

1.andrew
2.eric
3.madness
4.gerik

I want my data "gerik" in "madness" place when it show out. I am able to sort the data infront of "eric" but after "eric" i am not idea. I want my output just like below:

1.andrew
2.eric
3.gerik
4.madness

Below will be my example code, please help me by giving me advise or code sample:

#include <iostream>
#include <string>
#include <cstdlib>
#include <cstring>

using namespace std;

struct node
{
    char f_name[20];
    char l_name[20];
    char u_id[10];
    node *next;
};

node *head;
node *curr;

//prototype
void display();
void add();
void search_name();
void insert_data(node *tempnode);
void insert_before_head(node *tempnode);
void menu(char choice);
char pause;

//function start...
void search_name()
{
    char name[20];
    curr = head;
    cin.ignore(30,'\n');
    cout<<"Key In Last Name :"<<endl;
    cin.get(name, 20);
    cin.ignore(30,'\n');

    while((curr->next != NULL) && (strcmp(curr->l_name, name) != 0))
    {
        curr = curr->next;
    }
    if(curr != NULL)
    {
        cout<<"Record Found !"<<endl;
        cout<<"First Name"<<setw(16)<<"Last Name"<<setw(16)<<"User ID"<<endl;
        cout<<"--------------------------------------------------------------"<<endl;
        cout<<curr->f_name<<setw(20)<<curr->l_name<<setw(16)<<curr->u_id<<endl<<endl;

    }
    else
    {
        cout<<"No Match !"<<endl;
        cout<<"Press 'Enter' To Continue"<<endl;
        cin.get(pause = getch());
        system("cls");
    }
};
void display()
{
    curr = head;
    if(head != NULL)
    {
        cout<<"First Name"<<setw(16)<<"Last Name"<<setw(16)<<"User ID"<<endl;
        cout<<"--------------------------------------------------------------"<<endl;
        while(curr != NULL)
        {
            cout<<curr->f_name<<setw(20)<<curr->l_name<<setw(16)<<curr->u_id<<endl;
            curr = curr->next;
        }
    }
    else
    {
        cout<<"No Data. File storage Empty!"<<endl;
    }
};
void add()
{
    node *temp;
    temp = new node;
    cin.ignore(30, '\n');
    cout<<"Key In First Name:"<<endl;
    cin.get(temp->f_name, 20);
    cin.ignore(30, '\n');
    cout<<"Key In Last Name:"<<endl;
    cin.get(temp->l_name, 20);
    cin.ignore(30, '\n');
    cout<<"Key In Your ID:"<<endl;
    cin.get(temp->u_id, 10);
    insert_data(temp);
};

void insert_data(node *tempnode)
{
    node *temp;

    if(head == NULL)
    {
        node *temp;
        temp = new node;
        temp = head;
        tempnode->next = NULL;
        head = tempnode;
    }
    else if(strcmp(tempnode->l_name, head->l_name) < 0)
    {
            insert_before_head(tempnode);
    }
    else
    {
        temp = new node;
        curr = head;

        while(curr->next != NULL)
        {
            curr = curr->next;
        }
            temp = tempnode;
            curr->next = tempnode;
            tempnode->next = NULL;
    }

};
void insert_before_head(node *tempnode)
{
    node *temp;

    if(head != NULL)
    {
       temp = new node;
       temp = tempnode;
       tempnode->next = head;
       head = tempnode;
    }
};

void menu(int choice)
{
    switch (choice)
    {
    case 1 :
        add();
        break;
    case 2:
        display();
        break;
    case 3:
        search_name();
        break;
    case 4:
        cout<<"Exit Program !"<<endl;
        break;
    default :
        cout<<"Error! Program Terminate !"<<endl;
    }
};

int main()
{
    int choice;
    node *temp;
    head = NULL;
    curr = NULL;

    cout << "Data Stack Head And Any Position !" << endl;
    system("cls");
    do{
            cout<<"1. Add Data."<<endl;
            cout<<"2. Show Data. "<<endl;
            cout<<"3. Search Last Name "<<endl;
            cout<<"4. Exit. "<<endl;
            cin >>choice;
            menu(choice);

       }while(choice != 4);

 return 0;
}

Answer 1

To sort linked lists you need to use the divide and conquer strategy with merge sort.

In order to insert in the middle you need to create 2 nodes Node slow and Node fast. At first Node slow is head.next, Node fast is head.next.next and you keep moving those 2 by doing slow = slow.next and fast = fast.next.next, until you hit the end with Node fast. If you think about it, fast will be moving twice as fast as Node slow, so in the end Node slow will be in the middle. Then insert after that node.

Answer 2

We want to insert in our list newNode.
Let node X be the node, after which newNode should be inserted to preserve sorting order.

You can rewite your insert_data(...) function like in my example.
I took the code, sugested by WhozCraug and rewrote it to be more evident.

void insert_data(node *newNode)
{
    node **pointerToTheNextPtr = &head;
    // find position to insert new node
    while (*pointerToTheNextPtr && strcmp((*pointerToTheNextPtr)->l_name, newNode->l_name) < 0)
        pointerToTheNextPtr = &((*pointerToTheNextPtr)->next);

    // here pointerToTheNextPtr stores the pointer to the X->next field

    // insert new node between X and *(X->next)
    newNode->next = *pointerToTheNextPtr; // set newNode->next = X->next
    *pointerToTheNextPtr = newNode; // set X->next = newNode 
}