Singly Linked List in C

From: Joe Wright (joewwright_at_earthlink.net)
Date: 10/28/03 

Date: Tue, 28 Oct 2003 14:58:52 GMT

Given a singly linked list with a dummy head node, how would you go
about sorting the list based on the node's value? Consider:

typedef struct node {
  int value;
  struct node *next;
} node;

node dummy; /* value is 0 and next is NULL */
node *head = &dummy; /* the value of head will not change */
node *prev, *this; /* various pointers to keep track */

I have routines to add() to the list, fnd() a value in the list and
del() a node from the list. No problem. But how to sort it on value?

Because we go 'forward' scanning the list, for a given 'this' node we
have only one 'prev' adjacent node. I can do a bubble sort with this
information but not insertion because I can't go 'backward' up the list.

Am I missing something simple? 

-- 
Joe Wright                                 http://www.jw-wright.com
"Everything should be made as simple as possible, but not simpler."
                    --- Albert Einstein ---

Relevant Pages

  • Re: Naming typedefs
    ... typedef struct node { ... some IDEs. ... If you do something like asking the editor to show you ...
    (comp.unix.programmer)
  • Re: Naming typedefs
    ... a considerable camp of people who feel the typedef adds nothing ... and just write `struct node_s' or `struct node' as needed. ... I've retained the habit past ...
    (comp.unix.programmer)
  • Re: A problem about use List
    ... typedef struct Node Node; ... MakeEmpty(List L) ... boolean and pointer to list. ...
    (comp.lang.c)
  • Re: the struct havent define when i use typedef
    ... typedef struct node *NODEPTR; ... At the time of your typedef, all the compiler really needs to know is how ...
    (comp.lang.c)
  • Re: A problem about use List
    ... typedef struct Node Node; ... MakeEmpty(List L) ... I think you need to spend more time reading some basic texts before ...
    (comp.lang.c)