Inserting in a sorted linked list(sorted alphabetically)
 

[COLOR=Navy]Pls 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;

}


}

***********************************************

Re: Inserting in a sorted linked list(sorted alphabetically)
 

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.

Re: Inserting in a sorted linked list(sorted alphabetically)
 

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;

  }

}