CODEWITHSUNDEEP
cpointerslinked-list
Jackson Lenhart
Jackson Lenhart

Reputation: 650

Confused by double pointer traversal of linked list

So I was watching this Ted Talk w/ Linus Torvalds wherein he outlines this example: https://www.youtube.com/watch?v=o8NPllzkFhE&t=14m26s

I was intrigued by it, so I wanted to code it up for myself:

void remove_node(node* entry) {
  node** indirect = &head;

  while (*indirect != entry) {
    indirect = &(*indirect)->next;
  }

  *indirect = entry->next;

  free(entry);
}

I understand almost all of it, but I am deeply confused by this line:

indirect = &(*indirect)->next;

The &(*indirect) seems to take the address of dereferencing indirect, which I would think would cancel each other out and we just end up with plain indirect again. Although that is obviously incorrect, I do not exactly understand why.

If that is not correct (which it isn't), maybe I am just not understanding the grouping/order of operations properly when -> is involved. However, no matter how I try to separate it out, it does not work the same:

node* blegh;
while (*indirect != entry) {
  // Doesn't work.
  blegh = (*indirect)->next;
  indirect = &blegh;
}

If someone could help me wrap my feeble brain around this it would be greatly appreciated.

Upvotes: 1

Views: 175

Answers (2)

4386427
4386427

Reputation: 44329

In order to understand the line:

indirect = &(*indirect)->next;

you need to understand the precedence of the operators, i.e. understand in which order the individual operators are executed. For instance: Is & executed before or after -> ?

You can get the answer here: https://en.cppreference.com/w/c/language/operator_precedence

It will tell you that your line is the same as:

indirect = &((*indirect)->next);

So what the code does is to get the address of the next pointer in the current node. Consequently *indirect will be the value of the next pointer (aka a pointer to the next node).

Your attempt to rewrite the code is wrong because blegh is not part of the list so the address of blegh is not part of anything in the list. However, you can do:

node* blegh;
while (*indirect != entry) {
  blegh = *indirect;         // Pointer to current node
  indirect = &blegh->next;   // Get address of next-pointer in current node 
}

Upvotes: 2

MayurK
MayurK

Reputation: 1957

indirect = &(*indirect)->next;

is equavlent to 

indirect = &((*indirect)->next);

So the address of the "next" element is assigned to "indirect" here.

The following doesn't work.

  blegh = *indirect->next;
  indirect = &blegh;

Because indirect = &blegh; is storing address of local variable "blegh" to "indirect".

Try doing the following.

  node* indirect = head; //Use single pointer "indirect" 

  while (indirect != entry) {
    indirect = &indirect->next; //Assign "next" pointer to "indirect"
  }

Upvotes: 2

Related Questions