CODEWITHSUNDEEP
cpointerslinked-listdouble-pointer
Jatin
Jatin

Reputation: 14269

Using single versus double pointers in Linked lists implemented in C

I was writing this code for adding element at the end of linked list:

struct node{
    int info;
    struct node* link;
};

void append ( struct node **q, int num )  
{

struct node *temp, *r ;

if ( *q == NULL )       // if the list is empty, create first node
{
    temp = (struct node*) malloc ( sizeof ( struct node ) ) ;
    temp -> info = num ;
    temp -> link = NULL ;
    *q = temp ;        
}
else{
    temp = *q ;         

    /* go to last node */
    while ( temp -> link != NULL )
        temp = temp -> link ;

    /* add node at the end */
    r = (struct node *)malloc ( sizeof ( struct node ) ) ;
    r -> info = num ;
    r -> link = NULL ;
    temp -> link = r ;
}
}

and I call append function like this: append(&list, 10); where list is the pointer to the linked list

This code works, but if I use single pointer in append function(using *q instead of **q) and make changes accordingly (as done below and also when I call it), it doesn't work. What is wrong with the code below?:

void append ( struct node *q, int num )  
{

struct node *temp, *r ;

if ( q == NULL )       // if the list is empty, create first node
{
    temp = (struct node*) malloc ( sizeof ( struct node ) ) ;
    temp -> info = num ;
    temp -> link = NULL ;
    q = temp ;        
}
else{
    temp = q ;         

    /* go to last node */
    while ( temp -> link != NULL )
        temp = temp -> link ;

    /* add node at the end */
    r = (struct node *)malloc ( sizeof ( struct node ) ) ;
    r -> info = num ;
    r -> link = NULL ;
    temp -> link = r ;
}
}

Upvotes: 3

Views: 5331

Answers (2)

wildplasser
wildplasser

Reputation: 44250

In your first snippet (which is correct), you are doing too much.

void append ( struct node **q, int num )  
{

struct node *new ;

    /* go to last node */
    for ( ; *q; q = &(*q)->link ) {;}

    /* add node at the end */
    new = malloc ( sizeof *new );
    if (!new) { barf_now(); return; }

    new->info = num ;
    new->link = NULL ;
    *q = new; ;
    }
}

The basic idea is: you want to append to the tail of the list; you need to:

  • find the first NULL pointer
  • set it's value to the value of the new pointer

The "empty list" case is not special, it just means that you can find the NULL pointer in zero steps. Coding it this way there is no special case, and no need for an if (...) ... else ... construct.

Upvotes: 1

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272657

Because in the second example, q is a copy of the pointer passed in by the caller. The caller's original pointer never gets modified.

Upvotes: 3

Related Questions