Thread: doubly linked list

  1. #1
    Musicman - Canora
    Join Date
    Aug 2005
    Location
    Melbourne
    Posts
    252

    doubly linked list

    Hey guys just wondering if somebody could explain a simple example of doubly linked lists. I know that each node contains a prev next pointer but how does it look when its all coded. I checked on various websites i cant really find much that makes sense. Even if its a simple traversing doubly linked list ?

    thanks

  2. #2
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    http://en.wikipedia.org/wiki/Double_...ly-linked_list

    What isn't there to understand ? I mean, traversing is the exact same thing as traversing a single linked list, you just read the next pointer until you reach NULL. The only difference is that you can traverse it in two directions, using not only the next but also the previous pointer. This allows you to read the element just before another element in O(1) instead of O(x-1) where x is the position of the element in the list.

  3. #3
    Musicman - Canora
    Join Date
    Aug 2005
    Location
    Melbourne
    Posts
    252
    What does the o stand for sorry

  4. #4
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    It's a notation for the algorithmic complexity, also called Big O or Asymptotic Notation.

    What I wanted to say is that if you're at element X in a single linked list and you want to access the element X-1, you need to start at the head and iterate all the way through the list until you are at element X-1. In a double linked list, you simply follow the "previous" pointer, so you only need one operation.

  5. #5
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,732
    I digged up my first year folder, and i got this example

    Code:
    #include <stdio.h>
    
    struct node
    {
           struct node *prev;
           int data;
           struct node *next;
    };
    
    void insertNode( struct node **, int );
    void DisplayNodes( struct node *, int );
    struct node * CreateNode( );
    
    int main()
    {
        struct node *head = NULL;
        int i;
        int Toggle = 1;
        
        insertNode( &head, 1 );
        insertNode( &head, 2 );
        insertNode( &head, 3 );
    
        for( i=0;i<10;i++ )
            DisplayNodes( head, (Toggle ^= 3) );
        
        getchar();
        return 0;
    }
    
    struct node * createnode()
    {
           return malloc(sizeof(struct node));
    }
    
    void insertNode( struct node **head, int data)
    {
         struct node *tempnode, *tempnode1;
         
         if( *head == NULL )
         {
            *head = createnode();
            (*head)->next = NULL;
            (*head)->prev = NULL;
            (*head)->data = data;
         }
         else
         {
             tempnode = *head;
             
             while( empnode->next != NULL )
                tempnode = tempnode->next;
             
             tempnode1 = createnode();
             tempnode1->prev = tempnode;
             tempnode1->next = NULL;
             tempnode1->data = data;
             
             tempnode->next = tempnode1;
         }
    }
    
    void DisplayNodes( struct node *head, int direction )
    {
         if( direction == 1 )
         {
            while( head != NULL )
            {
                printf("&#37;d ",head->data);
                head = head->next;
            }
         }
         else
         {
             while( head->next != NULL )
                 head = head->next;
             
             while( head != NULL )
             {
                printf("%d ",head->data);
                head = head->prev;
             }
         }
         printf("\n");
    }
    
    /* my output
    3 2 1
    1 2 3
    3 2 1
    1 2 3
    3 2 1
    1 2 3
    3 2 1
    1 2 3
    3 2 1
    1 2 3
    */
    This code is just a demo of how the struct is defined for doublely LL and how to call them, build then and display then in alternative direction.

    ssharish2005

  6. #6
    Musicman - Canora
    Join Date
    Aug 2005
    Location
    Melbourne
    Posts
    252
    thanks guys for that ill build upon that

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  2. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  3. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  4. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM