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 pointers1).
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 |
+---+ +---+ +---+
^^^^^ ^^^^^