sorting a doubly linked (linux-style) list

This is a discussion on sorting a doubly linked (linux-style) list within the C Programming forums, part of the General Programming Boards category; Hello everybody! This is a quite good exercise for training with pointers: so good that I'm getting crazy! In linux, ...

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    100

    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
    /* NO COMMENT */

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.)

  3. #3
    Registered User
    Join Date
    Oct 2007
    Posts
    100
    Quote Originally Posted by tabstop View Post
    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..
    /* NO COMMENT */

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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).

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    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.
    Last edited by iMalc; 10-01-2008 at 01:06 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 03:09 AM
  3. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  4. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  5. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21