1

The book I have been following for learning datastructure uses "single-pointer" as arguments in the functions which add new nodes in different positions in a linked list e.g. At the beginnning, at the end. Also in case of deletion "pointer-to-pointer" are used. In all these cases, the function prototype looks like:

void appendordelete (struct node **, int );

But in functions which count no of nodes, display the list and add after a certain position, the function prototype changes to:

void anyofthementionedfunctions (struct node *, int );

So I am confused when should I use single-pointer and when pointer-to-pointer in linkedlist operations. Please clarify. These functions work in a typical and ideal way, so I am not posting the coding for these lengthy functions.

Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
Mistu4u
  • 5,132
  • 15
  • 53
  • 91

1 Answers1

2

In this case, the pointer to pointer is used so that it is possible to change the pointer to the first node. You keep a pointer which points to the beginning of the list. If you add a new item, that pointer might need to change since the new item may be added at the beginning of the list.

void insertAtBeginning(struct node **first_ptr,int value)
{
    struct node *first = malloc(sizeof(struct node));
    first->value = value;
    first->next = *first_ptr;
    *first_ptr = first;
}

void test()
{
    struct node *first = 0;
    insertAtBeginning(&first,5);
    freeAll(first);
}

If you are doing something like searching through the list, there is no need to change the pointer to the first node, so there is no need to pass a pointer to pointer.

But note that there are other uses of pointers to pointers. For example, you might maintain a matrix as a pointer to an array of pointers to rows.

Vaughn Cato
  • 63,448
  • 5
  • 82
  • 132
  • One more question: when a pointer type variable is being passed to a function as a parameter, how is it possible to use them within the fucntion body without the pointer? For ex. `void display (struct node *q);` in the function body, all works are done on `q` instead of `*q`. Why is that? If my aim was to use only `q`, I could have sent `q` instead of `*q` as the parameter! – Mistu4u Sep 11 '13 at 04:43
  • 1
    @Mistu4u: If `q` is a pointer, then you can use `q->member` to access a member. This is equivalent to `(*q).member`. – Vaughn Cato Sep 11 '13 at 04:45
  • Yeah, I understood that. My point is in my book, in the `display` function I mentioned above, a loop is working to show the contents of the list, `{while( q!=NULL){printf("%d",q->data);q=q->link;}printf("\n");}`. My point is I have sent parameter `*q`, then why is the line `q!=NULL`, should it not be `while (*q!=NULL)`? – Mistu4u Sep 11 '13 at 04:49
  • 2
    @Mistu4u: If `q` is a pointer, then `*q` is what it points to. A `node` can't be null, but a pointer can be null, so it is the pointer that you are wanting to check, not the `node` that it points to. – Vaughn Cato Sep 11 '13 at 04:52
  • @Mistu4u Suppose you want someone to deliver a flyer to a house. Do you truck the house to them, or give them its address? Suppose the mailbox at each house contains a slip of paper with the address of the next house to deliver a flyer to, with the last one saying "no house". Should you truck the first house to them, or provide its address? If you send the delivery person a house, and they put a flyer in its mailbox, take out the address of the next house, and replace the current house with the next house, what do they replace it with when they encounter the slip saying "no house"? – Jim Balter Sep 11 '13 at 05:36
  • *My point is I have sent parameter `*q`* -- No, you haven't. You have passed an address (a pointer), which becomes the value of the parameter `q`. the `*` is part of the type declaration of `q` -- it's a variable of type `struct node*`. This is why I and many other experience C programmers put the `*` next to the type, not next to the variable. The only problem with that is things like `struct node* a, b;` which declares `a` as a `struct node*` but declares `b` as a `struct node`. The solution is to always use separate declarations when declaring pointers. (Or to use more modern languages.) – Jim Balter Sep 11 '13 at 05:43