Bi-Directional Linked Lists

This is a discussion on Bi-Directional Linked Lists within the C Programming forums, part of the General Programming Boards category; Not sure if thats the proper name for it but I was thinking, wouldn't having a pointer the the next ...

  1. #1
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681

    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.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    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
    My best code is written with the delete key.

  3. #3
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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 */
    My best code is written with the delete key.

  5. #5
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    How would you declare sorted then?

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >How would you declare sorted then?
    Code:
    struct node **sorted;
    Since this is a dynamic array of pointers, you need a double pointer.
    My best code is written with the delete key.

  7. #7
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Thanks Prelude, I understand and have it working now.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Singly Linked Lists: Clarification Needed
    By jedispy in forum C++ Programming
    Replies: 4
    Last Post: 12-14-2006, 04:30 PM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. Map file formats and linked lists
    By Spitball in forum Game Programming
    Replies: 2
    Last Post: 03-04-2004, 10:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21