Different ways to iterate over a linked list

Question

The first thing I think about when I need to iterate over a linked list is to do:

Node* node = head; while (node) { // do something to node node = node->next; } 

But sometimes I see people doing this complicated thing:

 Node** node = &head; while (*node) { // do something to node node = &(*node)->next; } 

What is the difference and what is the second used for?

Answer 1

Obviously, you understand the first method.

The main difference between the first and second is where the pointer used to enumerate the list is located. In the first, pointer values ​​are used through a local variable, each time updating it to the value of the current pointer node next . In the second, a pointer to a pointer is used to store the address of the "current" pointer. The pointer that it addresses is the actual pointer in the list, not just the value. It initially accesses the head pointer. At each step, it accesses the current node next pointer. When the algorithm completes, it will hold the address of the last member of next in a linked list whose value would be better NULL.

The second has certain advantages, although there is not one for a simple listing. This method is more commonly used in maintenance scenarios, such as inserting and deleting position lists.

Example. Pointing only to a list of linked list with the following node form, write a function that adds a new node to the end of the list:

 struct Node { int data; struct Node *next; }; 

Using the first method for enumeration requires saving the previous pointer and special consideration to find the initial pointer of the head NULL. The following function does this and always returns the head of the linked list:

 struct Node * ll_insertTail(struct Node *head, int data) { struct Node *prev = NULL, *cur = head; while (cur) { prev = cur; cur = cur->next; } cur = malloc(sizeof(*head)); cur->data = data; cur->next = NULL; if (prev == NULL) return cur; prev->next = cur; return head; } 

The same operation, but using the pointer approach to the pointer to move the actual members of the pointer (and not just their values) would be something like this:

 struct Node* ll_insertTail(struct Node *head, Type data) { struct Node **pp = &head; while (*pp) pp = &(*pp)->next; *pp = malloc(sizeof(**pp)); (*pp)->data = data; (*pp)->next = NULL; return head; } 

This can be further improved by the fact that the caller transmits the address of the head pointer first. This adds an advantage to it, allowing you to use the return value of a function for something other than a list chapter pointer. For instance:

 int ll_insertTail(struct Node **pp, int data) { while (*pp) pp = &(*pp)->next; if ((*pp = malloc(sizeof(**pp))) == NULL) { perror("Failed to allocate linked list node"); return EXIT_FAILURE; } (*pp)->data = data; (*pp)->next = NULL; return EXIT_SUCCESS; } 

Called as:

  int res = ll_insertTail(&head, data); 

Both last cases are possible due to the use of pointers by address, and not just by value. For a simple listing, it makes little sense to use a pointer-to-pointer approach. But if you need to find a specific node or node position in the list and save the mechanism for using the pointer that got you there (maybe head , maybe some next member), pointers to pointers make for elegant decisions.

Good luck.

Answer 2

In the first code example, the node variable is a pointer to a node structure. It contains the address of the memory cell in which the node structure is stored.

In the second code example, the variable node is a pointer to a pointer to a node structure. It contains the address of the memory cell containing the address of the memory cell in which the node structure is stored.

This sounds confusing to a large extent, because the variable name is the same in both code samples, and it almost matches the node . Let me rewrite the code samples so that the meaning of the pointer is clearer.

The first case:

 Node* node_pointer = head; while (node_pointer != NULL) { // node_pointer points to a Node // do something to that Node, then advance to the next element in the list // ... something ... node_pointer = node_pointer->next; // advance } 

Second case:

 Node** node_pointer_pointer = &head; while (*node_pointer_pointer != NULL) { // node_pointer_pointer points to a pointer which points to a Node // do something to that Node, then advance to the next element in the list // ... something ... node_pointer_pointer = &((*node_pointer_pointer)->next); // advance } 

In both cases, the head variable is a pointer to a node structure. Therefore, its value is assigned directly to node_pointer in the first case:

 node_pointer = head; 

And in the second case, the & operator is used to get the head memory cell:

 node_pointer_pointer = &head; 

What is node ? This is a struct containing (possibly along with other things) the next field, which is a pointer to a node . Therefore, the next value can be assigned directly to node_pointer in the first code example, but in the second stage of the code it needs to refer to the & operator.

Why is the second approach useful? This is not the case in this example. If you only want to iterate over the elements of a linked list, all you need is a pointer to the node structure.

However, it is useful to have a pointer to a pointer when you want to manipulate a subordinate pointer. For example, suppose you have finished moving the list, and now you want to add a new tail to the node.

In the first case above, node_pointer does not help, since its value is NULL . You can't do anything about it.

In the second case, when the *node_pointer_pointer value is NULL , the node_pointer_pointer value node_pointer_pointer not. This is the address of the next field of the last node in the list. Therefore, we can assign the address of the new node structure to this next :

 *node_pointer_pointer = make_new_node(); // make_new_node() returns a pointer 

Note the asterisk or dereference operator in *node_pointer_pointer . By delaying node_pointer_pointer , we get the next pointer, and we can assign it the address of the new node structure.

Also note that this assignment works if node_pointer_pointer points to the head of an empty list. By dereferencing this, we get head , and we can assign it the address of the new node structure.