Linked list example with a pointer to pointer

Hi,

I have a piece of code that is demonstrating a linked list. What I don't understand is what's happening in the add function.

There is a pointer to a pointer '**q'. Further down a pointer variable is assigned 'temp = *q'
Why do I have to use '**q' as a parameter in the add function?

My code is:

Code:

---

# include<stdio.h>
# include<malloc.h>

/* define the node */
struct node {
int        data;
struct node *next;
};

/* Add a node to the linked list */
void add(struct node **q, int num) {
  struct node *temp;
  temp = *q;

  /* first time there is no node therefore allocate */
  if(*q==NULL) {
    *q=malloc(sizeof(struct node));
    temp = *q;
  }

  /* add node after the last one */
  else {
    /* move on until the last node then create a new node*/
    while((temp->next)!=NULL) {
      temp = temp->next;
    }
    temp->next = malloc(sizeof(struct node));
    temp = temp->next;
  }

  // set data and pointer for the node, the last one always point at NULL
  temp->data = num;
  temp->next = NULL;
}

/* Display the linked list */
void display(struct node *pt) {

  // traverse through all nodes until the last one
  while(pt!=NULL) {
    printf(" Data : %d\n",pt->data);
    printf(" next : %p\n",pt->next);
    pt = pt->next;
  }
}

/* ******* MAIN ******* */
int main() {

  int          continue_add; // used if you want to continue adding elements
  int          your_choice;  // user choice of what to do
  int          num;          // user data
  struct node *ptr;          // always pointing at the first node after first have been added

  /* init values */
  ptr          = NULL;
  continue_add = 1;

  while (continue_add == 1) {
    printf(" Main Menu\n");
    printf("  1. Add element\n");
    printf("  Enter your choice ");
    scanf("%d",&your_choice);

    switch(your_choice) {
      case 1:
        printf(" Enter data to your node -> ");
        scanf("%d",&num);
        add(&ptr,num);
        display(ptr);
        break;

      default:
        printf(" Illegal choice! ");
    }// switch(your_choice)

    printf(" Do you want to continue (press 1 for yes) ");
    scanf("%d",&continue_add);
    printf("\n");
  }// while (continue_add==1)
}// main()

---

Quote:

---

Originally Posted by hzcodec

There is a pointer to a pointer '**q'. Further down a pointer variable is assigned 'temp = *q'
Why do I have to use '**q' as a parameter in the add function?

---

Because C passes parameters by value and you have this:

Code:

---

  /* first time there is no node therefore allocate */
  if(*q==NULL) {
    *q=malloc(sizeof(struct node));

---

If you just passed "ptr" then you'd have *q as an argument, which is just a pointer. If you then did

Code:

---

    q=malloc(sizeof(struct node));

---

You'd just write over the local parameter q. When you returned to main, ptr would still be NULL. Using a pointer to a pointer allows you to change the value of the actual pointer. It's just like passing a pointer to something else.

All the rest of add() could function with just *q, it's just that initial write.

Code:

---

void foo ( int a ) {
  a = 10;
}
void bar ( int *a ) {
  *a = 10;
}
int main ( ) {
  int fred = 0;
  foo( fred );  // does this change fred?
  bar( &fred );  // what about this one?
}

---

If you've got a variable of type T in a function, and you want it to be modified by a called function, then you need to pass a pointer to it.
That means the called function needs a T* parameter.

So if your variable is already a pointer, this naturally leads to a pointer to a pointer.

Look at line 17 in your code.