Why is a pointer to pointer treated differently than a pointer in spite of corresponding corrections-CodePudding

I'm trying to delete a Node from a Doubly Linked List. The function deleteNode() will receive the head of the linked list and the node to be deleted. However, depending on whether I pass the node to be deleted as a pointer or a pointer to pointer, the code behaves differently (in spite of making the corresponding corrections in syntax).

Here is my structure for Doubly Linked List node -

struct DNode {
int val;
struct DNode* next;
struct DNode* prev;
DNode(int val) { //constructor
    this->val = val;
    next = NULL;
    prev = NULL;
}
};

The following code works perfectly fine:

void deleteNode(struct DNode** head, struct DNode* deleteMe) {
//head is pointer to pointer, deleteMe is pointer

if(!(*head) || !deleteMe) {
    cout<<"\nDeletion not possible";
    return;
}

if(deleteMe->prev != NULL)
    deleteMe->prev->next = deleteMe->next;

if(deleteMe->next != NULL)
    deleteMe->next->prev = deleteMe->prev;

if(deleteMe == *head)
    *head = deleteMe->next;

delete deleteMe;
}

Correspoding Driver Code -

/*at this point, I have pushed elements into the Linked List to make it 4->3->2->1, where 4 is 
the head*/
deleteNode(&head, head);      
deleteNode(&head, head->next); 
deleteNode(&head, head->next);

However, when I send both parameters as pointer to pointer, I experience a crash at runtime:

void deleteNode(struct DNode** head, struct DNode** deleteMe) {

if(!(*head) || !(*deleteMe)) {
    cout<<"\nDeletion not possible";
    return;
}

if((*deleteMe)->prev != NULL)
    (*deleteMe)->prev->next = (*deleteMe)->next;

if((*deleteMe)->next != NULL)
    (*deleteMe)->next->prev = (*deleteMe)->prev;

if(*deleteMe == *head)
    *head = (*deleteMe)->next;

delete *deleteMe;
}

Corresponding driver code:

/*at this point, I have pushed elements into the Linked List to make it 4->3->2->1, where 4 is 
the head*/
deleteNode(&head, &head);      
deleteNode(&head, &head->next);
deleteNode(&head, &head->next);

PS - this is not entirely an issue with delete:

if you comment the line delete *deleteMe in the erroneous code, the code will run but the output will be different.

Output for working code: 3

Output for erroneous code after commenting the delete line: 3->1

CodePudding user response：

Here, when you pass &head and &head,

if(*deleteMe == *head)
    *head = (*deleteMe)->next;

*deleteMe and *head are the same object (the object whose address you passed in), and they are still the same object after the assignment.
(That is, it is equivalent to both *head = (*head)->next; and *deleteMe = (*deleteMe)->next.)

So this,

delete *deleteMe;

does the same as delete *head in this case, and then things go boom.

In the first case, *head and deleteMe are different objects, so assigning to *head does not affect deleteMe.

As an illustration, this is what happens ("main_head" is the variable in main).

When you enter the function, you have this situation:

  head
   |
   v           ---     --- 
main_head---->|  ---->| ----> ...
   ^           ---     --- 
   |                    ^
 deleteMe               |
                  (*deleteMe)->next

And after the assignment *head = (*deleteMe)->next:

  head     ------------- 
   |      |             |
   |      |             v
   v      |    ---     --- 
main_head-    |  ---->| ----> ...
   ^           ---     --- 
   |
 deleteMe

And you can see that head and deleteMe still point to main's head, and that is the object you assigned a value to.

With the working code, you start with this:

  head        
   |           
   v           ---     --- 
main_head---->|  ---->| ----> ...
               ---     --- 
                ^       ^
                |       |
            deleteMe   deleteMe->next

And end up with

  head     ------------- 
   |      |             |
   |      |             v
   v      |    ---     --- 
main_head-    |  ---->| ----> ...
               ---     --- 
                ^       ^
                |       |
            deleteMe   deleteMe->next