Using Pointers to Pointers In C

Lets try to understand the importance of pointers to pointers by the help of an example.Suppose we're trying to write some code to delete a given integer from a list. The straightforward solution looks like this:

 /* delete node containing i from list pointed to by lp */

 struct list *lp, *prevlp;
 for(lp = list; lp != NULL; lp = lp->next)
  {
  if(lp->item == i)
   {
   if(lp == list)
    list = lp->next;
   else prevlp->next = lp->next;
   break;
   }
  prevlp = lp;
  }
 }

This code works, but it has two blemishes. One is that it has to use an extra variable to keep track of the node one behind the one it's looking at, and the other is that it has to use an extra test to special-case the situation in which the node being deleted is at the head of the list. Both of these problems arise because the deletion of a node from the list involves modifying the previous pointer to point to the next node (that is, the node before the deleted node to point to the one following). But, depending on whether the node being deleted is the first node in the list or not, the pointer that needs modifying is either the pointer that points to the head of the list, or the next pointer in the previous node.

To illustrate this, suppose that we have the list (1, 2, 3) and we're trying to delete the element 1. After we've found the element 1, lp points to its node, which just happens to be the same node that the main list pointer points to, as illustrated in (a) below: 

To remove element 1 from the list, then, we must adjust the main list pointer so that it points to 2's node, the new head of the list (as shown in (b)). If we were trying to delete node 2, on the other hand (as illustrated in (c) above), we'd have to adjust node 1's next pointer to point to 3. The prevlp pointer keeps track of the previous node we were looking at, since (at other than the first node in the list) that's the node whose next pointer will need adjusting. (Notice that if we were to delete node 3, we would copy its next pointer over to 2, but since 3's next pointer is the null pointer, copying it to node 2 would make node 2 the end of the list, as desired.)

We can write another version of the list-deletion code, which is (in some ways, at least) much cleaner, by using a pointer to a pointer to a struct list. This pointer will point at the pointer which points at the node we're looking at; it will either point at the head pointer or at the next pointer of the node we looked at last time. Since this pointer points at the pointer that points at the node we're looking at (got that?), it points at the pointer which we need to modify if the node we're looking at is the node we're deleting. Let's see how the code looks:

 struct list **lpp;
 for(lpp = &list; *lpp != NULL; lpp = &(*lpp)->next)
  {
  if((*lpp)->item == i)
   {
   *lpp = (*lpp)->next;
   break;
   }
  }
 }

That single line

 *lpp = (*lpp)->next;

updates the correct pointer, to splice the node it refers to out of the list, regardless of whether the pointer being updated is the head pointer or one of the next pointers. (Of course, the payoff is not absolute, because the use of a pointer to a pointer to a struct list leads to an algorithm which might not be nearly as obvious at first glance.)

To illustrate the use of the pointer-to-pointer lpp graphically, here are two more figures illustrating the situation just before deleting node 1 (on the left) or node 2 (on the right). 

In both cases, lpp points at a struct node pointer which points at the node to be deleted. In both cases, the pointer pointed to by lpp (that is, the pointer *lpp) is the pointer that needs to be updated. In both cases, the new pointer (the pointer that *lpp is to be updated to) is the next pointer of the node being deleted, which is always (*lpp)->next.

One other aspect of the code deserves mention. The expression

 (*lpp)->next

describes the next pointer of the struct node which is pointed to by *lpp, that is, which is pointed to by the pointer which is pointed to by lpp. The expression

 lpp = &(*lpp)->next

sets lpp to point to the next field of the struct list pointed to by *lpp. In both cases, the parentheses around *lpp are needed because the precedence of * is lower than ->.