Question about argument in a function as a pointer to a pointer

Question

I am reading the book "C Programming: A Modern Approach" by KN King, where in chapter 17.5 on page 432 they define a function for deleting a node from a singly linked list:

The following function, delete_from_list, uses the strategy that we've just outlined. When given a list and an integer n, the function deletes the first node containing n. If no node contains n, delete_from_list does nothing. In either case, the function returns a pointer to the list.

struct node *delete_from_list(struct node *list, int n)
{
  struct node *cur, *prev;

  for (cur = list, prev = NULL;
       cur != NULL && cur->value != n;
       prev = cur, cur = cur->next)
     ;
  if (cur == NULL)
    return list;               /* n was not found */
  if (prev == NULL)
    list = list->next;         /* n is in the first node */
  else
    prev->next = cur->next;    /* n is in some other node */
  free(cur);
  return list;
}

The book refers to this function in an exercise on page 454:

Exercises

6. Modify the delete_from_list function so that is uses only one pointer variable instead of two (cur and prev).

My question is about the following solution I found on Github:

struct node *delete_from_list(struct node **list, int n) {
    struct node *item = *list;
    while (item) {
        if (item->value == n) {
            *list = item->next;
            free(item);
            break;
        }
        list = &item->next;
        item = item->next;
    }
    return *list;
}

I understand what a pointer to a pointer is. But I don't understand what happens after the line struct node **list. I would very much appreciate it if anybody could explain this solution line by line with visualization.

Answer 1

I would very much appreciate it if anybody could explain this solution line by line with visualization.

Let's take an example linked list with values 1, 2, and 3, where head points to its first node, and we have a value n that equals 2. We can picture the state of the list in the main program as follows:

      ┌───────┐   ┌─────────────┐  ┌─────────────┐  ┌──────────────┐
      │ head ────►│ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
      └───────┘   │ │ value 1 │ │  │ │ value 2 │ │  │ │ value 3  │ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
                  │ │ next────────►│ │ next────────►│ │ next NULL│ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │             │  │             │  │              │
                  └─────────────┘  └─────────────┘  └──────────────┘

With this solution code, the caller must pass a pointer to a pointer to a node, and so if the head variable in the main program is a pointer to the first node, we need to pass its address, like so:

delete_from_list(&head, n);

Let's now picture how the function sees its own list variable:

      ┌───────┐
      │ list  │
      └───│───┘
          ▼
      ┌───────┐   ┌─────────────┐  ┌─────────────┐  ┌──────────────┐
      │ head ────►│ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
      └───────┘   │ │ value 1 │ │  │ │ value 2 │ │  │ │ value 3  │ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
                  │ │ next────────►│ │ next────────►│ │ next NULL│ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │             │  │             │  │              │
                  └─────────────┘  └─────────────┘  └──────────────┘

The first statement is:

struct node *item = *list;

So we get:

      ┌───────┐   ┌───────┐
      │ list  │   │ item  │
      └───│───┘   └───│───┘
          ▼           ▼
      ┌───────┐   ┌─────────────┐  ┌─────────────┐  ┌──────────────┐
      │ head ────►│ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
      └───────┘   │ │ value 1 │ │  │ │ value 2 │ │  │ │ value 3  │ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
                  │ │ next────────►│ │ next────────►│ │ next NULL│ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │             │  │             │  │              │
                  └─────────────┘  └─────────────┘  └──────────────┘

Execution enters the loop, but the if condition is false, so the next executed statement is:

list = &item->next;

Now the local list variable will point to the address of the next member of the node that item points to:

                  ┌───────┐
                  │ item  │
                  └───│───┘
                      ▼
      ┌───────┐   ┌─────────────┐  ┌─────────────┐  ┌──────────────┐
      │ head ────►│ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
      └───────┘   │ │ value 1 │ │  │ │ value 2 │ │  │ │ value 3  │ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
                  │ │ next────────►│ │ next────────►│ │ next NULL│ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │   ▲         │  │             │  │              │
                  └───│─────────┘  └─────────────┘  └──────────────┘
                      │
                  ┌───│───┐
                  │ list  │
                  └───────┘

The last statement in the loop's body is:

item = item->next;

So we get:

                                   ┌───────┐
                                   │ item  │
                                   └───│───┘
                                       ▼
      ┌───────┐   ┌─────────────┐  ┌─────────────┐  ┌──────────────┐
      │ head ────►│ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
      └───────┘   │ │ value 1 │ │  │ │ value 2 │ │  │ │ value 3  │ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
                  │ │ next────────►│ │ next────────►│ │ next NULL│ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │   ▲         │  │             │  │              │
                  └───│─────────┘  └─────────────┘  └──────────────┘
                      │
                  ┌───│───┐
                  │ list  │
                  └───────┘

In the next iteration the if condition is true, so then we execute this:

*list = item->next;

Which mutates the list as follows:

                                   ┌───────┐
                                   │ item  │
                                   └───│───┘
                                       ▼
      ┌───────┐   ┌─────────────┐  ┌─────────────┐  ┌──────────────┐
      │ head ────►│ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
      └───────┘   │ │ value 1 │ │  │ │ value 2 │ │  │ │ value 3  │ │
                  │ └─────────┘ │  │ └─────────┘ │  │ └──────────┘ │
                  │ ┌─────────┐ │  │ ┌─────────┐ │  │ ┌──────────┐ │
                  │ │ next────────┐│ │ next────────►│ │ next NULL│ │
                  │ └─────────┘ │ ││ └─────────┘ │  │ └──────────┘ │
                  │   ▲         │ ││             │┌►│              │
                  └───│─────────┘ │└─────────────┘│ └──────────────┘
                      │           └───────────────┘
                  ┌───│───┐
                  │ list  │
                  └───────┘

Now the found node can be freed with free(item):

                                   ┌───────┐
                                   │ item  │
                                   └───│───┘
                                       ▼
      ┌───────┐   ┌─────────────┐                   ┌──────────────┐
      │ head ────►│ ┌─────────┐ │                   │ ┌──────────┐ │
      └───────┘   │ │ value 1 │ │                   │ │ value 3  │ │
                  │ └─────────┘ │                   │ └──────────┘ │
                  │ ┌─────────┐ │                   │ ┌──────────┐ │
                  │ │ next─────────────────────────►│ │ next NULL│ │
                  │ └─────────┘ │                   │ └──────────┘ │
                  │   ▲         │                   │              │
                  └───│─────────┘                   └──────────────┘
                      │
                  ┌───│───┐
                  │ list  │
                  └───────┘

Finally the function returns *list, but that is of little use: the caller should not use that return value for assignment to its own head variable, or things would go bad. The caller should just rely on the function to adapt its head if necessary (not the case in this example).

This is what the caller ends up with:

      ┌───────┐   ┌─────────────┐                   ┌──────────────┐
      │ head ────►│ ┌─────────┐ │                   │ ┌──────────┐ │
      └───────┘   │ │ value 1 │ │                   │ │ value 3  │ │
                  │ └─────────┘ │                   │ └──────────┘ │
                  │ ┌─────────┐ │                   │ ┌──────────┐ │
                  │ │ next─────────────────────────►│ │ next NULL│ │
                  │ └─────────┘ │                   │ └──────────┘ │
                  │             │                   │              │
                  └─────────────┘                   └──────────────┘

Remarks

In my opinion this is not really a "fair" solution, as it changes the signature of the function:

• The caller must pass a double pointer instead of single pointer, and
• The caller should not use the returned pointer to assign it back to their own list pointer. Instead, the function returns a pointer to the successor node, which in most cases is not interesting information, so the caller could just ignore the return value.

The original function would have to be called like this:

head = delete_from_list(head, n);

...while this function should be called like this:

delete_from_list(&head, n);

For the above reasons, I am not sure this was the intended solution for the exercise. For other ideas to solve this, see this Q&A.