Please I need help on how to insert elements into a sorted linked list.I actually have a list that contains names and scores for students and I want the elements to be inserted into the right postion such that the names of individual students are arranged alphabetically.

This is my code but something seems to be wrong.

#include "iostream"
using namespace std;

struct Node
{
 char *name;
 int score;
 Node *next;
};
Node  *head=NULL;

void InsertItem(Node * &head);


void main()
{
    InsertItem(head);
}



void InsertItem(Node * &head)
{
    Node *temp, *previous,*current; /*previous stores the node before the insertion point*/

       temp=new Node();

        cout<<"Enter name";
        cin>>temp->name;
        cout<<"Enter score";
        cin>>temp->score;


       if (head == NULL)  /* first node in the list */
    {

           head = temp;
        }
        else if (strcmp(head->name,temp->name)>=0)/* insert at the head */
    {

            temp->next = head;
            head = temp;
        }
        else 
    {
            previous = head;     /* trailing pointer */
            current = head->next; 

        while ((current != NULL) && strcmp(current->name,temp->name)<0) 
        {
                previous = current;
                current = current->next;
            }
            temp->next=previous->next;
        previous->next=temp;

        }


}

Edited 3 Years Ago by pyTony: Fiexed formatting

Here is one method you could use to sort your linked list alphabetically:
(I haven't tested this specific code but the idea is sound)

First, push each node into an array of nodes:

Node **array = new Node*[size];
Node *temp = head_ptr;

while(temp)
{
   Node[i] = temp;
   temp = temp->next;
}

Now sort your array of Nodes based on the first letter of each name:

#include<algorithm>

//This function sorts to ascending order
sort(Node[0]->name[0], Node[size]->name[0]);

Now.. all you have to do is include a provision on what to do if the first 2 letters of a person's name are the same.


Once you are done with all your sorting operations, turn the array of nodes back into a linked list. Make each node of the newly sorted list point to the next node in line by resetting all the *next pointers:

head_ptr = Nodes[0];

for(int i=0; i<size-1; i++)

   Nodes[i]->next = Nodes[i+1];

That's it. You now have a head_ptr that points to beginning of a sorted linked list.

This assumes that, if the list already exist, it is in 'name' order

...
temp->next = NULL; // add this to temp just after cin

curr = head;
if (curr == NULL) // empty list
{
  head = temp;
}
else
{
  while (curr != NULL)
  {
    if (curr->next == NULL) // end of list
    {
      curr->next = temp;
      break;
    }
    else if (temp->name < curr->name) // insert temp
    {
      temp->next = curr->next;
      curr->next = temp;
      break;
    }
    curr = curr->next;
  }
}
This article has been dead for over six months. Start a new discussion instead.