Append to end of doubly linked list

This is a discussion on Append to end of doubly linked list within the C Programming forums, part of the General Programming Boards category; How would I change this function so that it appends new nodes to the end of the list instead of ...

  1. #1
    Registered User
    Join Date
    Oct 2001
    Posts
    2

    Question Append to end of doubly linked list

    How would I change this function so that it appends new nodes to the end of the list instead of at the beginning?


    struct node *append(struct node *list, int data)
    {
    struct node *new;
    new = malloc(sizeof(struct node));
    if(new == NULL) {
    printf("malloc failed to allocate storage - exit\n");
    exit(0);
    }

    new->value = data;
    new->nextPTR = list;
    /* headPTR is a global pointer of type struct node */
    new->prevPTR = headPTR;
    return new;
    }

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Append to the end of 'tailPtr'.

    tailPtr->next = thisNode;
    thisNode->prev = tailPtr;
    tailPtr = thisNode;

    Quzah.
    Hope is the first step on the road to disappointment.

  3. #3
    kdt
    kdt is offline
    Registered User
    Join Date
    Mar 2002
    Posts
    9
    I hope that's what you needed

    struct node *append(struct node *list, int data)
    {
    struct node *new;
    new =(struct node*) malloc(sizeof(struct node));
    if(new == NULL)
    {
    printf("malloc failed to allocate storage - exit\n");
    exit(0);
    }

    /*a loop to get the last node*/
    for( ; list->nextPTR != NULL ; list = list->nextPTR)
    /*you can also use a global pointer of type struct node not to find the last node every time
    and it makes your code faster
    last_node=new;*/

    new->prevPTR=list;
    new->value = data;
    new->nextPTR = NULL;
    return new;
    }

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    /*a loop to get the last node*/
    for( ; list->nextPTR != NULL ; list = list->nextPTR)
    /*you can also use a global pointer of type struct node not to find the last node every time
    and it makes your code faster
    last_node=new;*/

    new->prevPTR=list;
    new->value = data;
    new->nextPTR = NULL;
    return new;
    }
    If you already have a 'last node' pointer, then the fastest way to do it as I've shown. If the pointer exists, simply make it's next point to the new node, and the new node's prev point back to it. Then change it so 'last node' now points to the new one. There is no faster way.

    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    kdt
    kdt is offline
    Registered User
    Join Date
    Mar 2002
    Posts
    9
    yes,i know there is no faster way
    and it's the basic way
    but we have a 'list' parameter and we don't know what is shown by it.

  6. #6
    Registered User PutoAmo's Avatar
    Join Date
    Mar 2002
    Posts
    72
    kdt, maybe your code is just lacking one more statement, namely:

    Code:
    list->nextPTR = new;

  7. #7
    kdt
    kdt is offline
    Registered User
    Join Date
    Mar 2002
    Posts
    9
    puto amo, why do you think so?

  8. #8
    Registered User PutoAmo's Avatar
    Join Date
    Mar 2002
    Posts
    72
    After loop,
    Code:
    for( ; list->nextPTR != NULL ; list = list->nextPTR)
    list->nextPTR == NULL

    And that means that list is now pointing to last node.

    After you add the new node (*new), you want the former last node (*list) to point to *new.

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    yes,i know there is no faster way
    and it's the basic way
    but we have a 'list' parameter and we don't know what is shown by it.
    But the original question was: How do I change this function to append to (the end of) a list.

    As such, all you have to do is:

    1) use a global tail and head pointer.
    2) use this function:
    Code:
    void append( Node *n )
    {
        if( n )
        {
            if( listTail )
            {
                listTail->next = n;
                n->prev = listTail;
            }
            listTail = n;
        }
    }
    After all, if we're changing the function, why bother with that prototype? Actually, you could also do:
    Code:
    void append( int data )
    {
        Node *n = malloc( sizeof( Node ) );
        n->data = data;
        if( listTail )
        {
                listTail->next = n;
                n->prev = listTail;
        }
        listTail = n;
    }
    Quzah.
    Last edited by quzah; 03-19-2002 at 04:45 PM.
    Hope is the first step on the road to disappointment.

  10. #10
    Registered User PutoAmo's Avatar
    Join Date
    Mar 2002
    Posts
    72
    Why checking for listTail to be true?
    Code:
    if ( listTail )
    maybe empty list?

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    > Why checking for listTail to be true?


    Because if it is null, and I do this:

    listTail->next = n;

    Bad Things(TM) happen.

    Quzah.
    Hope is the first step on the road to disappointment.

  12. #12
    Registered User PutoAmo's Avatar
    Join Date
    Mar 2002
    Posts
    72

    Thumbs up

    Ahaa. Sounds reasonable.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pleas take a look & give a critique
    By sh3rpa in forum C++ Programming
    Replies: 14
    Last Post: 10-19-2007, 10:01 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 06:47 PM
  3. Replies: 3
    Last Post: 03-04-2005, 01:46 PM
  4. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 05:40 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

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