Different ways of iterating over linked list

Question

The first thing I think of when iterating over a linked list is to do this:

Node* node = head;

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

But sometimes I see people do this complicated thing:

Node** node = &head;

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

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

Answer 1

You obviously understand the first method.

The fundamental difference between the first and second is where the pointer's used to enumerate the list reside. In the first, the pointer values are used via a local variable, each time updating it to the value of the current node's next pointer. In the second, a pointer-to-pointer is used to hold the address of the "current" pointer. The pointer it addresses is an actual pointer "in the list", not just it's value. Initially it addresses the head pointer. With each step it addresses the current node's next pointer. When the algorithm finishes it will be holding the address of the last next member in the linked list, the value of which better be NULL.

The second has distinct advantages, though none for simple enumeration. This method is more commonly utilized in maintenance scenarios, such as positional list insertions and removals.

Example: Given only a head pointer to a linked list with the following node-form, write a function that appends a new node to the end of the list:

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

Using the first method to enumerate requires maintaining a previous pointer and a special-consideration to detect an initial NULL head pointer. The following function does that, 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 utilizing a pointer-to-pointer approach to walk the actual pointer members (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 could be further enhanced by requiring the caller pass the address of the head pointer in the first place. This adds he advantage of allowing you to utilize the return value of the function for something other than the list head pointer. For example:

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;
}

Invoked as:

    int res = ll_insertTail(&head, data);

Both of the latter cases are possible because of utilizing pointers by-address rather than simply by-value. For simple enumeration it makes little sense to exercise a pointer-to-pointer approach. But if you need to search for a specific node or position of a node within a list and retain a mechanism for using the pointer that got you there (could be head, could be some next member), pointers-to-pointers make for elegant solutions.

Best of luck.

Answer 2

In the first code sample, the variable node is a pointer to a Node struct. It contains the address of the memory location where the Node struct is stored.

In the second code sample, the variable node is a pointer to a pointer to a Node struct. It contains the address of a memory location containing the address of a memory location where the Node struct is stored.

This sounds confusing in large part because the variable name is the same in both code samples and it is almost the same as Node. Let's rewrite the code samples so that the meaning of the pointer is clearer.

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 variable head is a pointer to a Node struct. That's why 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 memory location of head:

node_pointer_pointer = &head;

What is a Node? It is a struct containing (probably along with other things) a field next which is a pointer to a Node. That is why the value of next can be assigned directly to node_pointer in the first code sample but it has to be referenced with the & operator in the second code sample.

Why is the second approach useful? In this example, it's not. If you only want to iterate over the elements of the linked list, all you need is a pointer to a Node struct.

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

In the first case above, node_pointer is of no help because its value is NULL. You can't do anything more with it.

In the second case, while the value of *node_pointer_pointer is NULL, the value of node_pointer_pointer is not. It is the address of the next field of the last node in the list. Therefore, we can assign the address of a new Node struct to that next:

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

Note the asterisk, or dereferencing operator, in *node_pointer_pointer. By deferencing node_pointer_pointer, we get the next pointer, and we can assign to it the address of a new Node struct.

Also note that this assignment works if node_pointer_pointer points to the head of an empty list. Dereferencing it gets us head, and we can assign to it the address of a new Node struct.