question about linklist

The question I found it from the text as following:
You are required to design, implement and test a function, sort_list(.), which will sort such a list according to the priority value computed by whatever function is passed as its second argument. The first argument is to be a pointer to the head of the list. Since the OS will have other structures with pointers to IORB's, the list must be sorted in place.

typedef struct iorb {

short base_pri;
struct iorb *link;
char filler[110];

} IORB;
void sort_list(IORB **list,int(*newpr)(short));
int newp(short base)
{
return base;
}
question
1) provide the coding for inserting a value
2) insert into a list

Thanks,
Frank

I'm sorry, but I can't find your question anywhere in that post. All I see is an exercise (from a book?). But I'll humor you and offer some suggestions:

>the list must be sorted in place.
If you mean by not using any extra memory then it's hard not to sort a list in place. If you mean by performing exchanges within the same list then you're going about it in an inefficient way. You'll find sorting a list easier if you build a new list from the old one by removing from the old list and adding the removed item in sorted position to the new list.

That would be how you perform insertion sort easily with linked lists, and mergesort. It's also possible (thought slightly more difficult and with annoying degenerate cases) to use binary search tree insertion and traversal routines to sort a linked list without using any extra memory:

Code:

---

#include <stdio.h>
#include <stdlib.h>

struct node {
  int data;
  struct node *prev, *next;
};

static struct node *treeinsert ( struct node *tree, struct node *item )
{
  if ( tree == NULL ) {
    tree = item;
  }
  else if ( item->data < tree->data ) {
    tree->prev = treeinsert ( tree->prev, item );
  }
  else {
    tree->next = treeinsert ( tree->next, item );
  }

  return tree;
}

static void traverse ( struct node *tree, struct node **list )
{
  struct node *save;

  if ( tree == NULL ) {
    return;
  }
  traverse ( tree->next, list );
  save = tree->prev;
  tree->prev = NULL;
  tree->next = *list;
  if ( *list != NULL ) {
    (*list)->prev = tree;
  }
  *list = tree;
  traverse ( save, list );
}

struct node *treesort ( struct node *list )
{
  struct node *tree = NULL;
  struct node *save;

  while ( list != NULL ) {
    save = list->next;
    list->prev = list->next = NULL;
    tree = treeinsert ( tree, list );
    list = save;
  }
  traverse ( tree, &list );

  return list;
}

int main ( void )
{
  struct node *list = NULL;
  struct node *n;
  int i;

  for ( i = 0; i < 10; i++ ) {
    n = malloc ( sizeof *n );
    if ( n == NULL ) {
      break;
    }
    n->data = rand() % 10;
    n->prev = NULL;
    n->next = list;
    if ( list != NULL ) {
      list->prev = n;
    }
    list = n;
  }
  printf ( "Unsorted\n" );
  for ( n = list; n->next != NULL; n = n->next ) {
    printf ( "%d->", n->data );
  }
  printf ( "%d\n", n->data );
  for ( ; n != NULL; n = n->prev ) {
    printf ( "%d%s", n->data, n->prev == NULL ? "\n" : "->" );
  }
  list = treesort ( list );
  printf ( "Sorted\n" );
  for ( n = list; n->next != NULL; n = n->next ) {
    printf ( "%d->", n->data );
  }
  printf ( "%d\n", n->data );
  for ( ; n != NULL; n = n->prev ) {
    printf ( "%d%s", n->data, n->prev == NULL ? "\n" : "->" );
  }

  return 0;
}

---

There are a few advantages to this approach:

1) You can easily sort a double linked list without jumping through hoops.
2) The code is easily accessable to anyone familiar with simple binary search trees.
3) For random data, it's every bit as efficient as sophisticated sorts (O(n log n))
4) It's easy to write. What I posted was the first try, and it compiled/ran correctly the on the first compile.

There is a big disadvantage too.

1) If the list is already sorted, the performance of the tree slows the sort down considerably.

I don't really recommend such a beast because mergesort is better, but this should get you started. :)