Why use a pointer to a pointer in this "handmade list"?

Question

We have a project in school, which, despite the fact that it concerns the project, involves the use of linked lists with this specific structure:

typedef struct _node { int contents; _node *next_node; } *node; 

Before the project, we were assigned a bunch of functions to learn how to work with the list (click node on the front or back list, count the number of nodes, find a specific node, etc.).

It was not so difficult, but when the teacher sent the basic project (so that each of us began to work in one place), all the functions included passing *node by reference . For instance:

 resultType functionName(node *list, ...) { ... } 

I performed all the functions of the list before the project with void , because, as I understand it, we work with pointers, so until you lose the memory address of the list header, you will not lose the contents (and the rest of the list).

So ... what is the point of passing a pointer to a pointer in this case? Is there something I'm missing? I asked my teacher, and he did not know how to explain (either this or he is as lost as I am). I mean, the structure is already a pointer, so why pass the address of the list address?

Answer 1

It depends on what is done in the functionName functionName . If you want to select the node* pointer or want to change its value outside the functionName , you should be able to modify it, and the pointer to the pointer should be passed to the function.

To illustrate this with an example, compare the two functions below. First, allocate1 is capable of allocating heaps on pointer a because it received a pointer to a pointer. The second, allocate2 gets a pointer by value, is able to allocate an array, but after its return, the allocated space is lost. This can be seen by comparing the pointer values ​​in the print statement. A.

 #include <iostream> void allocate1(double** a, const int n) { *a = new double[n]; std::cout << "allocate1: " << *a << std::endl; } void allocate2(double* a, const int n) { a = new double[n]; std::cout << "allocate2: " << a << std::endl; } int main() { double* test1 = nullptr; double* test2 = nullptr; int n = 10; allocate1(&test1, 10); std::cout << "after allocate1: " << test1 << std::endl; test1[3] = 16; // OK! allocate2(test2, 10); std::cout << "after allocate2: " << test2 << std::endl; test2[3] = 16; // NOT OK! return 0; } 

Output on my machine:

 allocate1: 0x7fcdd2403160 after allocate1: 0x7fcdd2403160 allocate2: 0x7fcdd24031b0 after allocate2: 0x0 Segmentation fault: 11 

Answer 2

Answer: Because it is convenient. It allows a function to manipulate a pointer, regardless of where it is stored.

The fact is that with a linked list you want to save the pointer to the first node somewhere. This pointer is not part of struct _node . But you can pass your address to the function in the same way as the address of any next_node pointer in any node that is in the list. That is, you do not need to specifically handle the case with an empty list.

As an example:

 void pushFront(node* list, int value) { node newNode = malloc(sizeof(*newNode)); newNode->contents = value; newNode->next_node = *list; *list = newNode; } 

I can call this function as follows:

 int main() { node myList = NULL; pushFront(&myList, 42); printf("The answer is %d!\n", myList->contents); } 

Note that this code works even when myList initialized to NULL ! Similar elegant code arises when going through a list, inserting or deleting nodes along a path.

---

Also: I think this is a bad habit of typedef pointer types: it hides the fact that a thing is a pointer. I would very much prefer the following definitions:

 typedef struct node node; //avoid having to write `struct` everywhere struct node { int contents; node *next_node; }; void pushFront(node** list, int value); 

This implies a change in the implementations of the functions to the following (only three stars):

 void pushFront(node** list, int value) { node* newNode = malloc(sizeof(*newNode)); newNode->contents = value; newNode->next_node = *list; *list = newNode; } int main() { node* myList = NULL; pushFront(&myList, 42); printf("The answer is %d!\n", myList->contents); } 

You see, when I see a line like

 node newNode = malloc(sizeof(*newNode)); 

I immediately have a WTF moment: "Why is newNode considered as a pointer when it is just ... oh wait, this is really a type of pointer! Someone must really clear this code!" On the other hand, when I see

 node* newNode = malloc(sizeof(*newNode)); 

everything is clear right away: newNode is a pointer that malloc() stands out in a standard way.

The fact is that I do not expect a pointer if I do not see the type * in the type. Typed pointer types violate this assumption, which leads to poor readability of the code. Especially C programmers, like their code, are clearly in places like this.

Of course, you should adhere to the recommendations that your teacher gives, but be sure to change the pointer-typedef-habit as soon as you can.

Answer 3

The thing passed to such a function is usually the "head", a pointer to the first element of the list.

This pointer to the head often needs to be changed: when you insert the first node into an empty list (the main pointer changes from NULL to the pointer to the actual node) or when you remove the first element from (the main pointer must be changed to point to the next element of the list).

This is why we need to pass a pointer to the head, not the head.

A better solution would be to have a List struct

 typedef struct _List { Node head; } List; 

Then you pass a pointer to a List , which makes sense: in C, you pass a pointer to what you need to change.