Thread: Doubly Linked List - Understanding...

  1. #1
    Registered User
    Join Date
    May 2009
    Posts
    2

    Doubly Linked List - Understanding...

    Hi, my first post.

    I canīt understand the insert (or enqueue) operation in this algorithm where we work with Doubly Linked List with sort (ordering) during insert operation.

    Could you help me please? I am putting comments in the lines where I have this difficulty to understand

    Here is the code:

    Code:
    typedef struct list
    {
         int info;
         struct list *next;
         struct list *prev;
    } list;
    
    list *LHead, *LTail;
    Code:
    int value_info()
    {
        int info;
     
        printf("\nValue = ");
        scanf("%d",&info);
        return info;    
    }
    Code:
    void insert()
    {
        list *p, *a, *q;
        int new;
        
        new = value_info();
        
        q = (list *)calloc(1,sizeof(list));
        q->info = new;
        p = LHead; //what does this mean???
        while (p->info < new) //what does this mean???
              p = p->next; //what does this mean???
        a = p->prev; //what does this mean???
        a->next = q; //what does this mean???
        p->prev = q; //what does this mean???
        q->next = p; //what does this mean???
        q->prev = a; //what does this mean???
        printf("Value %d inserted on list!",new);
    }

  2. #2
    Banned ಠ_ಠ's Avatar
    Join Date
    Mar 2009
    Posts
    687
    ╔╗╔══╦╗
    ║║║╔╗║║
    ║╚╣╚╝║╚╗
    ╚═╩══╩═╝

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    2
    Quote Originally Posted by ಠ_ಠ View Post
    Look, thanks but

    I see that this is a completely different way to add in order to the list, so I would need to change EVERYTHING in my code that works perfectly.

    I just need to understand those last lines of insert opertation

    Code:
        while (p->info < new)
              p = p->next; 
        a = p->prev; 
        a->next = q; 
        p->prev = q; 
        q->next = p; 
        q->prev = a;
    I just need to generally interpret these lines. I would be very grateful if someone could explain just this insert operation
    Last edited by hi-0ctane; 05-31-2009 at 05:27 PM.

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    In your example, q is the new node. The while loop then iterates through the list until it finds a node with a higher int info in it. Then it inserts q by rearranging the pointers in the previous and next node, and setting it's own prev and next pointers appropriately.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM