Thread: Bi-Directional Linked Lists

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

>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?

Code:

struct node **sorted;

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