Hi iamnamja,

Sorting a doubly-linked list is a piece of cake.  You can move up and down the list at will, just like you can with an array.

Sorting a singly-linked list is a bit more complicated.  The links move forward through the list, but you often need to move backwards through the list.  There are several practical ways to do this:  recursion, rescanning the list, and breaking/rebuilding the list.  Because this sounds like classwork, the third option is probably not going to be acceptable (though it the most efficient for very large lists).

Consider a list that consists of the even numbers from 2 to 20.  For illustration purposes, this list is ascending.

2 -> 4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 16 -> 18 -> 20

Now add a node at the end that contains 17

2 -> 4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 16 -> 18 -> 20 -> 19

As we scan down the list comparing adjacent nodes, we see things in order until we get to the last node

2 < 4
4 < 6
6 < 8
...
18 < 20
20 !< 19  <<--  need to move this node!

To swap two nodes, we actually need the address of three nodes.  In this case, to swap nodes 19 and 20 we also need the address of 18.  Node 18 points to 20 as the next link in the chain and it will need to point to 19.  Node 19 will need to point to node 20, and node 20 will need to point to NULL to mark the end of the list.

Keeping track of three nodes isn't so bad, but look what happens if the last node is 17.  The node needs to be moved back two places, so we need the address of the last 4 nodes.

If the last node contains a 1, we need to have the address of every node to bubble it back up the list.

There are two ways around this.  You can march through the list recursively, with each successive call advancing one position in the list.  When a node is swapped, the function returns FALSE and the calling node checks to see if the change affects the two nodes that it is comparing.  When the function hits the end of list it returns TRUE, which is returned all the way back to the base node.  A recursive solution is fairly efficient on a small list.  But it's not practical with a large list because stack sizes are ususally quite small.

The non-recursive variant will work on very large lists, but is not particularly efficient.  Every time you swap two nodes you simply restart the sort.  A slighltly better version is to work the entire list each pass.  In this case you would restart the sort if any swaps were performed.


Better than any of the sorts mentioned here is to sort the list by deleting and adding.

1) Walk through the list one time comparing adjacent nodes.  (A and B in this example.)
2) If the two nodes are in the correct order advance one location and retest.
3) If the nodes are out of order, delete node B by linking around it.  (Make sure that you saved a pointer to node B!)
4) Now call your ADD() function to add node B back into the list in it's correct location.  (By definition, node B will be inserted into the list in the already-sorted region that you've already tested.)
5) Resume comparing nodes from where you left off.



Good Luck,
Kent