sorting a doubly linked (linux-style) list

Hello everybody!
This is a quite good exercise for training with pointers: so good that I'm getting crazy!:)

In linux, a doubly-linked list is implemented by means of a list_head structure defined as follows:

Code:

---

struct list_head{
        struct list_head *next;
        struct list_head *prev;
};

---

The head of the list is a struct list_head head which is initialized as follows:

Code:

---

head.next=&head;
 head.prev=&head

---

We can use this data structure to define lists of every type, simple as

Code:

---

struct node{
struct list_head lh;
int value;
}

---

or more complex like:

Code:

---

struct node{
struct list_head lh;
int age;
char firstname[25];
char lastname[25];
};

---

My problem is understanding how a sort algorithm could be implemented in a "general" way. For example, I had to sort the 1st kind of nodes according to their values and I did this in a "dirty" way, by swapping the values (I omit some obvious typedefs) :

Code:

---

void swap (int *a, int *b)
{
        int tmp = *a;
        *a=*b;
        *b=tmp;
}

void sort (ListHeadPtr head)
{
        ListHeadPtr aPtr,bPtr;
        for (aPtr=head->next; aPtr!=head; aPtr=aPtr->next)
        {
                for (bPtr=head->next;bPtr!=head;bPtr=bPtr->next)
                {
                        if ( (aPtr!=bPtr)&&( ((NodePtr)aPtr)->value < ((NodePtr)bPtr)->value) )
                        {
                                swap (&(((NodePtr)aPtr)->value),&(((NodePtr)bPtr)->value));
                        }
                }
        }
}

---

But I don't like this solution.. I'd like to swap the whole node...
I tried swapping the lh fields but didn't work and I surrended since my brain got really messed-up.. :) How could I solve this?
Thanks a lot!
Bye

You shouldn't ever copy things when you sort linked ilsts, just trade pointers. That is, instead of
A <-> B <-> C <-> D you can just trade pointers on B and C so that A <-> C <-> B <-> D. (Of course, you'll also have to change a pointer on A and D as well.)

Quote:

---

Originally Posted by tabstop

You shouldn't ever copy things when you sort linked ilsts, just trade pointers. That is, instead of
A <-> B <-> C <-> D you can just trade pointers on B and C so that A <-> C <-> B <-> D. (Of course, you'll also have to change a pointer on A and D as well.)

---

with a normal list i'd do this in a couple of minutes, but with this list_head struct I have some problems.. every node has 2 pointers, the last has to point to head which in turn has to know who is the 1st and who is the last... a bit messy.. :(

It must be that paper shortage again.

Let's be more general: Suppose I want to swap A and B in the following list:
C <-> A <-> D <-> ... <-> E <-> B <-> F
We can find C, D, E, and F by following pointers on A and B.
We have eight pointers to change (two into A, two out of A, two into B, two out of B). Now it's pretty much just eight assignment statements, with the caveat of checking to make sure C, D, E, and F exist before trying to set their links (that is, don't set F->prev = A if F=NULL).

In other words, it's quite nasty to perform swaps in a doubly-linked list, much like how it's more painful to insert items in the middle of an array. Each data structure makes different things easier or harder.
What I would recommend is to try a different sorting algorithm. BubbleSort or similiar algorithms are extremely painful to get right with a doubly-linked list. Trust me I've been there, and you really really don't want to go there! Even QuickSort is far easier to implement for a doubly-linked list, IMHO.
I would thoroughly recommend switching to InsertionSort instead. You can make it out of some much easier to implement concepts. You need:

• A second doubly-linked list, initially empty
• The ability to pop an item from the unsorted list.
• The ability to search a sorted list for the position of insertion of a new item
• The ability to insert an item at that found location.
• The ability to swap the newly sorted list with the original one.

Repeat the middle 3 steps until the unsorted list is empty and then you have Insertion Sort.
Note that it works best if you remove an item from the opposite end of the unsorted list than the end you append to on the sorted list. That way it's fastest when already sorted. Give that a go instead and I'm sure you'll manage.