Inserting in a sorted linked list(sorted alphabetically)

Expand Post »

[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;

}

}

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

Similar Threads

Removing an item from head of linked list in C
Quicksorting linked list - simple algorithm in C
Sorted linked list help in C++
sort linked list help please in C
help with linked lists in C++

crestaldin

Reputation Points: 10

Solved Threads: 0

Light Poster

Offline

30 posts
since Mar 2005

Permalink

Mar 12th, 2006

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:

C++ Syntax (Toggle Plain Text)
Node **array = new Node*[size];
Node *temp = head_ptr;
 
while(temp)
{
   Node[i] = temp;
   temp = temp->next;
}
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:

C++ Syntax (Toggle Plain Text)
#include<algorithm>
 
//This function sorts to ascending order
sort(Node[0]->name[0], Node[size]->name[0]);
#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:

C++ Syntax (Toggle Plain Text)
head_ptr = Nodes[0];
 
for(int i=0; i<size-1; i++)
 
   Nodes[i]->next = Nodes[i+1];
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.

Clinton Portis

Reputation Points: 237

Solved Threads: 117

Practically a Posting Shark

Offline

822 posts
since Oct 2005

Permalink

Mar 12th, 2006

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

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

C++ Syntax (Toggle Plain Text)
...
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;
  }
}
...
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;
  }
}

Nedals

Reputation Points: 11

Solved Threads: 0

Light Poster

Offline

43 posts
since Dec 2005

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: Parse integers from string?

Next Thread in C++ Forum Timeline: Form won't close

DaniWeb Message

Cancel Changes

User Name
Password