468,512 Members | 1,530 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,512 developers. It's quick & easy.

Inserting in a list in Alphabetical order

..how can I insert entry in a linked list and arrange my entries according to the name in alphabetical order? I need to make a student record which contains the name, yr level and course of the student.
Is bubble sort applicable in this problem?if yes, can anyone help me how to implement it..tnx..
Sep 30 '06 #1
2 5838
293 100+
Bubble sort, while easiest to implement, has the worst best case performance ever. What you want is insertion sort. Each time you put in an entry, put it in in the correct place, and the list will be sorted when you are done inserting.

For example, insertion sort 1 1 9 8 4 3 2 1
Expand|Select|Wrap|Line Numbers
  1. data->NULL // list data points to a null entry
  2. data->1->NULL
  3. data->1->1->NULL
  4. data->1->1->9->NULL
  5. data->1->1->8->9->NULL
  6. data->1->1->4->8->9->NULL
  7. data->1->1->3->4->8->9->NULL
  8. data->1->1->2->3->4->8->9->NULL
  9. data->1->1->1->2->3->4->8->9->NULL
Sep 30 '06 #2
What you do, since it's a linked list, is you find the last item in the linked list (LL) that would come before the new entry. Now, in a LL, each item should have a pointer (or some other method of reference) to the next item in the LL (call this pointer NEXT). Also, for explanation's sake, let's call your three items A, B and N (for new).

A and B are already in the LL, and A points to B as the next item in the LL. Create N (the new item to insert), and make its NEXT pointer point to whatever A's points to. Then make A's next pointer point to N (the new item). Now the sequence of pointers goes from A -> N -> B.

Following this algorithm, there is never any need to sort anything, because right from the get-go you insert everything in the proper order to begin with, as hinted at in the first response above.

That help?
Sep 30 '06 #3

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

5 posts views Thread by Darryl B | last post: by
33 posts views Thread by Jim Cobban | last post: by
1 post views Thread by Richy Rich | last post: by
17 posts views Thread by John Salerno | last post: by
9 posts views Thread by Sheldon | last post: by
1 post views Thread by inboxforsumit | last post: by
1 post views Thread by fmendoza | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.