Pointer (computer Programming) - Multiple Indirection

Multiple Indirection

In some languages, a pointer can reference another pointer, requiring multiple dereference operations to get to the original value. While each level of indirection may add a performance cost, it is sometimes necessary in order to provide correct behavior for complex data structures. For example, in C it is typical to define a linked list in terms of an element that contains a pointer to the next element of the list:

struct element { struct element * next; int value; }; struct element * head = NULL;

This implementation uses a pointer to the first element in the list as a surrogate for the entire list. If a new value is added to the beginning of the list, head has to be changed to point to the new element. Since C arguments are always passed by value, using double indirection allows the insertion to be implemented correctly, and has the desirable side-effect of eliminating special case code to deal with insertions at the front of the list:

// Given a sorted list at *head, insert the element item at the first // location where all earlier elements have lesser or equal value. void insert(struct element **head, struct element *item) { struct element ** p; // p points to a pointer to an element for (p = head; *p != NULL; p = &(*p)->next) { if (item->value <= (*p)->value) break; } item->next = *p; *p = item; } // Caller does this: insert(&head, item);

In this case, if the value of item is less than that of head, the caller's head is properly updated to the address of the new item.