By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,189 Members | 903 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,189 IT Pros & Developers. It's quick & easy.

Inserting in a list in Alphabetical order

P: 5 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
Share this Question
Share on Google+
2 Replies

P: 293
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

P: 23
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.