pointer of a pointer in linked list append

Question

I normally program in python. To increase performance of my simulations, I am learning C. I have a problem to understand the use of a pointer of a pointer when implementing the append function to a linked list. This is an excerpt of the code from my book (Understanding Pointers in C by Kanetkar).

#include <stdlib.h>
#include <stdio.h>

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

int main(){
    struct node *p; //pointer to node structure
    p = NULL;   //linked list is empty

    append( &p,1);
    return 0;
}

append( struct node **q, int num){
    struct node *temp, *r;  //two pointers to struct node
    temp = *q;

    if(*q == NULL){
        temp = malloc(sizeof(struct node));
        temp -> data = num;
        temp -> link = NULL;
        *q = temp;
    }
    else{
        temp = *q;
        while( temp -> link != NULL)
            temp = temp -> link;
        r = malloc(sizeof(struct node));
        r -> data = num;
        r -> link = NULL;
        temp -> link = r;
    }
}

In this code, I pass the double pointer **q to the append function. I get that this is the adress of the address, i.e. the adress of NULL in this case.

I just don't get why one does it like this. Would it not be valid to remove one * operator from everything in the append() function and simply pass the adress of NULL (i.e. p instead of &p) to the append() function?

I have googled this question. The answers are either too hard to understand (since I'm just a C beginner) or too plain. I'm thankful for any hints, comments or links where I can read up about this.

Answer 1

When you pass things to functions in C, whether its variables or pointers, it's a copy of the original.

Quick example:

#include <stdio.h>
void change(char *in)
{
    // in here is just a copy of the original pointer.
    // In other words: It's a pointer pointing to "A" in our main case 
    in = "B";
    // We made our local copy point to something else, but did _not_ change what the original pointer points to.
}
void really_change(char **in)
{
    // We get a pointer-to-a-pointer copy. This one can give us the address to the original pointer.
    // We now know where the original pointer is, we can make _that one_ point to something else.
    *in = "B";
}
int main(int argc, char *argv[])
{
    char *a = "A";
    change(a);
    printf("%s\n", a); /* Will print A */
    really_change(&a);
    printf("%s\n", a); /* Will print B */
    return 0;
}

So the first function call to change() gets passed a copy of a pointer to an address. When we do in = "B" we only change the copy of the pointer we got passed.

In the second function call, the really_change(), we get passed a copy of a pointer-to-a-pointer. This pointer contains the address to our original pointer and voila, we can now reference the original pointer and change what the original pointer should point to.

Hopefully it explains it somewhat more :)

Answer 2

First Its not "the address of the address." Its the address of a pointer variable. Ex: if you pass the address of an int variable n that contains zero, you're not passing the address of zero; you're passing the address of a variable (in this case an int variable, in your case a pointer-variable). Variables have addresses in memory. The parameter in this case is the address of a variable that happens to be a pointer-variable, the head of your list.

Regarding why one does this? Simple. All variables in C (arrays via pointer-decay not withstanding) are passed by value. If you want to modify something by reference (address), then the "value" you need to pass must be an address and the formal parameter that receives it must be a pointer-type. In short, you make the "value" being passed a memory address rather than just a basic scaler value. The function then uses this (via a formal pointer parameter) to store data accordingly. Think of it as saying "put that thing I wanted at "this" memory address."

As a short example, suppose you wanted to run through a file, appending every character within into a forward linked list of nodes. You would not use an append-method like the one you have (see The Painter's Algorithm for why). See if you can follow this code, which uses a pointer-to-pointer, but no function call.

typedef struct node
{
    char ch;
    struct node *next;
} node;


node *loadFile(const char *fname)
{
    node *head = NULL, **next = &head;
    FILE *fp = fopen(fname, "r");
    if (fp)
    {
        int ch;
        while ((ch = fgetc(fp)) != EOF)
        {
            node *p = malloc(sizeof(*p));
            p->ch = ch;
            *next = p;
            next = &p->next;
        }
        *next = NULL;
        fclose(fp);
    }
    return head;
}

Stare at that awhile and see if you can understand how the pointer-to-pointer next is used to always populate the next linked node to be added to the list, starting with the head-node.