Bi-Directional Linked Lists

Not sure if thats the proper name for it but I was thinking, wouldn't having a pointer the the next node and to the previous node provide a lot more functionality then a standard linked list?

I've coded up a few test programs and its really not that much more overhead. While I haven't had the chance to try this in a "real" program I would like to hear your thoughts.

Methinks you've stumbled upon the concept of double linked lists. You're right on all counts, except the overhead of an extra pointer per node is a bit more signifigant than you might think. The algorithms are also more complicated because you have to fix four links per node instead of just two. Of course, for the benefits you get, the added complexity is most certainly worth it.

While single linked lists are still useful, they aren't nearly as useful when more powerful processing is required. I'll typically use a single linked list for situations where I need to build an arbitrarily long list of records and then traverse that list from first to last. Insertions and deletions usually warrant a double linked list.

>While I haven't had the chance to try this in a "real" program I would like to hear your thoughts.
Most of the linked lists in my "real" programs have been double. Consider the slightly extra effort in writing the following compared to what you've done with single linked lists and imagine the signifigantly greater return:

Code:

---

#include <stdlib.h>

struct node {
  void        *object;
  struct node *prev;
  struct node *next;
};

struct list {
  struct node head;
  struct node tail;
  size_t      size;
};

struct node *front ( struct list *list )
{
  return list->head.next;
}

struct node *back ( struct list *list )
{
  return list->tail.prev;
}

int push_front ( struct list *list, void *new_item )
{
  if ( list == NULL || new_item == NULL )
    return 0;
  if ( list->size == 0 ) {
    list->head.next = malloc ( sizeof *list->head.next );
    if ( list->head.next == NULL )
      return 0;
    list->head.next->object = new_item;
    list->head.next->prev = &list->head;
    list->head.next->next = &list->tail;
    list->head.prev = NULL;
    list->tail.next = NULL;
    list->tail.prev = list->head.next;
  }
  else {
    struct node *new_node;

    new_node = malloc ( sizeof *new_node );
    if ( new_node == NULL )
      return 0;
    new_node->object = new_item;
    new_node->next = list->head.next;
    new_node->prev = &list->head;
    list->head.next->prev = new_node;
    list->head.next = new_node;
  }
  list->size++;

  return 1;
}

int push_back ( struct list *list, void *new_item )
{
  if ( list == NULL || new_item == NULL )
    return 0;
  if ( list->size == 0 ) {
    list->head.next = malloc ( sizeof *list->head.next );
    if ( list->head.next == NULL )
      return 0;
    list->head.next->object = new_item;
    list->head.next->prev = &list->head;
    list->head.next->next = &list->tail;
    list->head.prev = NULL;
    list->tail.next = NULL;
    list->tail.prev = list->head.next;
  }
  else {
    struct node *new_node;

    new_node = malloc ( sizeof *new_node );
    if ( new_node == NULL )
      return 0;
    new_node->object = new_item;
    new_node->next = &list->tail;
    new_node->prev = list->tail.prev;
    list->tail.prev->next = new_node;
    list->tail.prev = new_node;
  }
  list->size++;

  return 1;
}

int insert_this ( struct list *list, struct node *it, void *new_item )
{
  struct node *new_node;

  if ( list == NULL || it == NULL )
    return 0;
  if ( list->size == 0 ) {
    if ( push_front ( list, new_item ) == 0 )
      return 0;
  }
  else {
    new_node = malloc ( sizeof *new_node );
    if ( new_node == NULL )
      return 0;
    new_node->object = new_item;
    new_node->next = it;
    new_node->prev = it->prev;
    it->prev->next = new_node;
    it->next->prev = new_node;
  }
  list->size++;

  return 1;
}

int erase_item ( struct list *list, void *old_item
                ,int (*compare) ( const void *a, const void *b )
                ,void (*release) ( struct node * ) )
{
  struct node *walk;

  if ( list == NULL || old_item == NULL || list->size == 0 )
    return 0;
  for ( walk = list->head.next; walk != &list->tail; walk = walk->next) {
    if ( (*compare) ( walk->object, old_item ) == 0 ) {
      walk->next->prev = walk->prev;
      walk->prev->next = walk->next;
      (*release) ( walk );
      list->size--;
      return 1;
    }
  }

  return 0;
}

int erase_this ( struct list *list, struct node *it
                ,void (*release) ( struct node * ) )
{
  if ( it == NULL || list->size == 0 )
    return 0;
  it->next->prev = it->prev;
  it->prev->next = it->next;
  (*release) ( it );
  list->size--;

  return 1;
}

int traverse ( struct list *list, void (*action) ( struct node * ) )
{
  struct node *save;
  struct node *walk;

  if ( list == NULL )
    return 0;
  for ( walk = list->head.next; walk != &list->tail; walk = save ) {
    save = walk->next;
    (*action) ( walk );
  }

  return 1;
}

int rtraverse ( struct list *list, void (*action) ( struct node * ) )
{
  struct node *save;
  struct node *walk;

  if ( list == NULL )
    return 0;
  for ( walk = list->tail.prev; walk != &list->head; walk = save ) {
    save = walk->prev;
    (*action) ( walk );
  }

  return 1;
}

#ifdef TEST_DRIVER
#include <stdio.h>

struct integer {
  int i;
};

struct integer *make_integer ( int init )
{
  struct integer *rv;

  rv = malloc ( sizeof *rv );
  if ( rv == NULL )
    return NULL;
  rv->i = init;

  return rv;
}

void print_integer ( struct node *x )
{
  printf ( "%d\n", ( (struct integer *)x->object )->i );
}

void free_integer ( struct node *x )
{
  free ( x->object );
  free ( x );
}

int compare ( const void *a, const void *b )
{
  return ( (const struct integer *)a )->i - ( (const struct integer *)b )->i;
}

int main ( void )
{
  struct integer kill;
  struct list    ilist = {0};
  int            i;

  for ( i = 0; i < 10; i++ )
    push_back ( &ilist, make_integer ( i ) );
  traverse ( &ilist, print_integer );
  kill.i = 4;
  printf ( "\n%d\n\n", erase_item ( &ilist, &kill, compare, free_integer ) );
  traverse ( &ilist, print_integer );
  kill.i = 9;
  printf ( "\n%d\n\n", erase_item ( &ilist, &kill, compare, free_integer ) );
  traverse ( &ilist, print_integer );
  kill.i = 0;
  printf ( "\n%d\n\n", erase_item ( &ilist, &kill, compare, free_integer ) );
  traverse ( &ilist, print_integer );
  kill.i = 14;
  printf ( "\n%d\n\n", erase_item ( &ilist, &kill, compare, free_integer ) );
  traverse ( &ilist, print_integer );
  printf ( "\n%d\n\n", erase_this ( &ilist, front ( &ilist )->next, free_integer ) );
  traverse ( &ilist, print_integer );
  printf ( "\n%d\n\n", erase_this ( &ilist, back ( &ilist )->prev, free_integer ) );
  traverse ( &ilist, print_integer );
  printf ( "\n%d\n\n", insert_this ( &ilist, front ( &ilist ), make_integer ( 14 ) ) );
  traverse ( &ilist, print_integer );
  printf ( "\n%d\n\n", insert_this ( &ilist, back ( &ilist ), make_integer ( 15 ) ) );
  traverse ( &ilist, print_integer );
  traverse ( &ilist, free_integer );

  return 0;
}
#endif

---

Thanks again Prelude. The code you supplied is still a little too much for me at this stage. Though I will keep it at hand for future consumtion.

Talking to one of the programming structures he said a common practice was to create a dynamically allocated array of pointers that could be used to sort the link list without modifying the lists structure. I'm currently banging my head against the wall trying to figure out how to do this. Know of any good tutorials that covers this?

Thanks

>Know of any good tutorials that covers this?
Well, using the above library you would do something like this:

Code:

---

for ( i = 0; i < 10; i++ )
  push_back ( &ilist, make_integer ( rand() % 100 ) );
sorted = malloc ( ilist.size * sizeof *sorted );
if ( sorted == NULL ) {
  fprintf ( stderr, "Error allocating memory\n" );
  return EXIT_FAILURE;
}
i = 0;
for ( it = front ( &ilist ); it != &ilist.tail; it = it->next )
  sorted[i++] = it;
/* Insert your favorite sorting method here */

---

How would you declare sorted then?

>How would you declare sorted then?

Code:

---

struct node **sorted;

---

Since this is a dynamic array of pointers, you need a double pointer.

Thanks Prelude, I understand and have it working now.