Purpose of Using a double pointer in Linked Lists

Question

I have a few questions about this function which intends to delete all occurrence of a given integer in the list :

void deleteAllOcc (node**headRef,int d)
{   
    node*temp;
    if (*headRef==NULL)
        return;
       
    while (*headRef)
    {
        if ((*headRef)->data==d)
        {
            temp=*headRef;
            *headRef=(*headRef)->next;
            free(temp);        
        }
        else
        {  
            headRef=&((*headRef)->next);
        }
    }
}

First why did we use **headRef instead of *head ?

Secondly, considering this :

if ((*headRef)->data==d)
{
    temp=*headRef;
    *headRef=(*headRef)->next;
    free(temp);               
}

Don't we need to update the links ?

And third, considering this :

else
{
    headRef=&((*headRef)->next);
}

Why we didnt do *headRef=(*headRef)->next); here?

Thanks in advance

Answer 1

For starters the function can be written simpler

void deleteAllOcc( node **headRef, int d )
{   
    while ( *headRef != NULL )
    {
        if ( ( *headRef )->data == d )
        { 
            node *temp = *headRef;
            *headRef = ( *headRef )->next;
            free( temp );
        }                    
        else
        {  
            headRef = &( *headRef )->next;
        }
    }
}

That is the first check for the equality of the passed by reference the pointer to the head node is redundant.

First why did we use **headRef instead of *head?

It depends on how the function is defined. In the case of the function definition provided in your question the pointer to the head node is passed by reference that is through a pointer to the pointer head. In this case changing the pointed pointer head within the function you are changing the original pointer.

For example imagine that the list contains only one node and its data member data is equal to the specified value of the argument d.

in main

node *head = malloc( sizeof( mode ) );
head->data = 1;
head->next = NULL;

deleteAllOcc( &head, 1 );

//...

and within the function deleteAllOcc you have

if((*headRef)->data==d)
{
    temp=*headRef;
    *headRef=(*headRef)->next;
    free(temp);
    
}

As *headRef yields the original pointer head in main then this statement

*headRef=(*headRef)->next;

changes the original pointer head in main bot a copy of the value of the pointer.

You could define the function in other way when the pointer to the head node is not passed by reference but passed by value. But in this case you need to return the possible new value for the pointer to the head node in main.

For example

node * deleteAllOcc( node *head, int d )
{
    while ( head != NULL && head->data == d )
    {
        node *temp = head;
        head = head->next;
        free( temp );
    }

    if ( head != NULL )
    {
        for ( node *current = head; current->next != NULL; )
        {
            if ( current->next->data == d )
            {
                node *temp = current->next;
                current->next = current->next->next;
                free( temp );
            }
            else
            {
                current = current->next;
            }
        }
    }

    return head;
}
  

and in main the function should be called for example like

node *head = NULL;

//filling the list

head = deleteAllOcc( head, 1 );

As you can see the function definition when the pointer to the head node is passed by reference looks more simpler.

how are we updating the links between the nodes after deleting a node

You have a pointer to the data member next of the current node. The pointed node by the data member next of the current node contains the value equal to the value of the parameter d. So the next node must be deleted. It ,means that the data member next of the current node shall point to the node after the deleted node. That is you need to write

*headRef = ( *headRef )->next;

where headRef at the current moment points to the data member next of the current node.

|node1| next |  -> |node2| next | -> |node3| next |
         |            |
       headRef      node that must be deleted

So in the data member next pointed to by headRef you have to write the value of the data member next of the deleted node node2.

why we didnt do *headRef=(*headRef)->next); here?

In this code snippet

else
{
   headRef=&((*headRef)->next);
}

you are reallocating the pointer headRef to point to the data member next of the next node. If you will write

*headRef = ( *headRef )->next;

then you will lose the node currently pointed to by the value stored in the expression *headRef that is in the currently pointed data member next will be changed rewriting the stored pointer.