471,850 Members | 996 Online

# 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 6267
D_C
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
m013690
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