delete an entry from a singly-linked list

Question

So today I was watching The mind behind Linux | Linus Torvalds, Linus posted two pieces of code in the video, both of them are used for removing a certain element in a singly-linked list.

The first one (which is the normal one):

void remove_list_entry(linked_list* entry) {
    linked_list* prev = NULL;
    linked_list* walk = head;
    while (walk != entry) {
        prev = walk;
        walk = walk->next;
    }
    if (!prev) {
        head = entry->next;
    } else {
        prev->next = entry->next;
    }
}

And the better one:

void remove_list_entry(linked_list* entry) {
    // The "indirect" pointer points to the
    // *address* of the thing we'll update
    linked_list** indirect = &head;

    // Walk the list, looking for the thing that
    // points to the entry we want to remove
    while ((*indirect) != entry)
        indirect = &(*indirect)->next;

    // .. and just remove it
    *indirect = entry->next;
}

So I cannot understand the second piece of code, what happens when *indirect = entry->next; evaluates? I cannot see why it leads to the remove of the certain entry. Someone explains it please, thanks!

Answer 1

what happens when *indirect = entry->next; evaluates? I cannot see why it leads to the remove of the certain entry.

I hope you have clear understanding of double pointers¹⁾.

Assume following:
Node structure is

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

and linked list is having 5 nodes and the entry pointer pointing to second node in the list. The in-memory view would be something like this:

                          entry -+
   head                          |
      +---+     +-------+     +-------+     +-------+     +-------+     +--------+
      |   |---->| 1 |   |---->| 2 |   |---->| 3 |   |---->| 4 |   |---->| 5 |NULL|
      +---+     +-------+     +-------+     +-------+     +-------+     +--------+

This statement:

linked_list** indirect = &head;

will make indirect pointer pointing to head.

                         entry -+
  head                          |
     +---+     +-------+     +-------+     +-------+     +-------+     +--------+
     |   |---->| 1 |   |---->| 2 |   |---->| 3 |   |---->| 4 |   |---->| 5 |NULL|
     +---+     +-------+     +-------+     +-------+     +-------+     +--------+
       ^
       |
     +---+
     |   |
     +---+
   indirect

The while loop

    while ((*indirect) != entry)

*indirect will give the address of first node because head is pointing to first node and since entry is pointing to second node the loop condition evaluates to true and following code will execute:

indirect = &(*indirect)->next;

this will make the indirect pointer pointing to the next pointer of first node. The in-memory view:

                          entry -+
   head                          |
      +---+     +-------+     +-------+     +-------+     +-------+     +--------+
      |   |---->| 1 |   |---->| 2 |   |---->| 3 |   |---->| 4 |   |---->| 5 |NULL|
      +---+     +-------+     +-------+     +-------+     +-------+     +--------+
                      ^
                      |
                    +---+
                    |   |
                    +---+
                  indirect

now the while loop condition will be evaluated. Because the indirect pointer is now pointing to next of first node, the *indirect will give the address of second node and since entry is pointing to second node the loop condition evaluates to false and the loop exits.
The following code will execute now:

*indirect = entry->next;

The *indirect dereference to next of first node and it is now assigned the next of node which entry pointer is pointing to. The in-memory view:

                          entry -+
   head                          |
      +---+     +-------+     +-------+     +-------+     +-------+     +--------+
      |   |---->| 1 |   |--   | 2 |   |---->| 3 |   |---->| 4 |   |---->| 5 |NULL|
      +---+     +-------+  \  +-------+     +-------+     +-------+     +--------+
                  *indirect \              /
                             +------------+

Now the next of first node is pointing to third node in the list and that way the second node is removed from the list.

Hope this clear all of your doubts.

---

EDIT:

David has suggested, in comment, to add some details around - why are the (..) parenthesis required in &(*indirect)->next?

The type of indirect is linked_list **, which means it can hold the address of pointer of type linked_list *. The *indirect will give the pointer of type linked_list * and ->next will give its next pointer.
But we cannot write *indirect->next because the precedence of operator -> is higher than unary * operator. So, *indirect->next will be interpreted as *(indirect->next) which is syntactically wrong because indirect is a pointer to pointer. Hence we need () around *indirect.

Also, &(*indirect)->next will be interpreted as &((*indirect)->next), which is the address of the next pointer.

---

1) If you don't know how double pointer works, check below:

Lets take an example:

#include <stdio.h>

int main() {
        int a=1, b=2;
        int *p = &a;
        int **pp = &p;

        printf ("1. p : %p\n", (void*)p);
        printf ("1. pp : %p\n", (void*)pp);
        printf ("1. *p : %d\n", *p);
        printf ("1. *pp : %d\n", **pp);

        *pp = &b;  // this will change the address to which pointer p pointing to
        printf ("2. p : %p\n", (void*)p);
        printf ("2. pp : %p\n", (void*)pp);
        printf ("2. *p : %d\n", *p);
        printf ("2. *pp : %d\n", **pp);

        return 0;
}

In the above code, in this statement - *pp = &b;, you can see that without accessing pointer p directly we can change the address it is pointing to using a double pointer pp, which is pointing to pointer p, because dereferencing the double pointer pp will give pointer p.

Its output:

1. p : 0x7ffeedf75a38
1. pp : 0x7ffeedf75a28
1. *p : 1
1. *pp : 1
2. p : 0x7ffeedf75a34   <=========== changed 
2. pp : 0x7ffeedf75a28
2. *p : 2
2. *pp : 2

In-memory view would be something like this:

//Below in the picture
//100 represents 0x7ffeedf75a38 address
//200 represents 0x7ffeedf75a34 address
//300 represents 0x7ffeedf75a28 address

int *p = &a
      p         a
      +---+     +---+
      |100|---->| 1 |
      +---+     +---+

        int **pp = &p;

      pp        p         a
      +---+     +---+     +---+
      |300|---->|100|---->| 1 |
      +---+     +---+     +---+


*pp = &b;

      pp        p         b
      +---+     +---+     +---+
      |300|---->|200|---->| 2 |
      +---+     +---+     +---+
                ^^^^^     ^^^^^

Answer 2

The entry isn't really "deleted", it's just no longer in the list. If this is your chain:

A --> B --> C --> D --> E --> ■

And you want to delete C, you're really just linking over it. It's still there in memory, but no longer accessible from your data structure.

            C 
A --> B --------> D --> E --> ■

That last line sets the next pointer of B to D instead of C.