Insertion sort question

Hey all,

I'm doing an assignment, in which I'm reading the contents of a binary file, into a linked-list, which I then need to sort by customer code. At first, I was going to use a bubble-sort on the linked list, but after searching this board, it seemed that an insertion sort would be more appropriate.

However, I think I'm right in saying that I'd need a doubly-linked list to do this? I've only ever used a singly-linked list in the form of a stack, so I'm a little in the dark still. I think this is the correct theory though.

Just wondered if that was right or not and if I need to go and learn how to use a *prev pointer.

Thanks,

John.

>However, I think I'm right in saying that I'd need a doubly-linked list to do this?
Insertion sort doesn't require a doubly linked list, but you will find that building a new list as you break down the old one is the easiest solution:

Code:

struct node *sort_list ( struct node *in )
{
  struct node out = {0,0};
  struct node *i, *step, *next;

  for ( step = in; step != 0; step = next ) {
    next = step->next;

    for ( i = &out; i->next != 0; i = i->next ) {
      if ( i->next->data > step->data )
        break;
    }

    step->next = i->next;
    i->next = step;
  }

  return out.next;
}

-Prelude

Thanks Prelude.

John.