Using single and double pointers in linked lists implemented in C
I wrote this code to add an item to the end of a 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 the append function like this: append(&list, 10);
where list
is a pointer to the linked list
This code works, but if I use a single pointer in the add function (using * q instead of ** q) and make the appropriate changes (as below and also when I call it) it doesn't work. What's 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 ;
}
}
source to share
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; ;
}
}
Basic idea: you want to add to the tail of the list; You need:
- find the first NULL pointer
- set value to the value of the new pointer
The "empty list" case is not special, it just means that you can find a NULL pointer in zero steps. By coding it this way there is no special case and no construction is needed if (...) ... else ...
.
source to share