Double pointers!

[Ankit Khare]

I have written a code of deleting a node from a link list using double pointers,i am not sure if i'll be able to explain what i want to ask..
so the code goes like this:

node **ptr=NULL;
node **delete(int value)
{
    int flag=0;
    node **temp=&root;
    while(*temp!=NULL)
    {
        if((*temp)->value==value)
        {
            flag =1;
            break;
        }
        else
            {
              temp=&(*temp)->next;
              printf("In else: temp=%p  *temp=%p\n",temp,*temp);
            }
    }
    if(flag==1)
        {
            printf("\nIn **delete()value found.Returning &temp=%p value=%d\n",&temp,(*temp)->value);
 
            return temp;
        }
    else
        printf("\nNot found\n");
}
 
void main()
{
int loop=0;
node *temp;
addNodes(1);
addNodes(2);
addNodes(3);
addNodes(4);
addNodes(5);
 
display();
ptr=delete(3);
*ptr=(*ptr)->next;
display();
 
}
This code works as reqd,deletes node with value 3.
 Here's the Output:
 
*ptr:0x900f008 and value:1 Pointing to:0x900f018
*ptr:0x900f018 and value:2 Pointing to:0x900f028
*ptr:0x900f028 and value:3 Pointing to:0x900f038
*ptr:0x900f038 and value:4 Pointing to:0x900f048
*ptr:0x900f048 and value:5 Pointing to:(nil)
 
In else: temp=0x900f00c  *temp=0x900f018
In else: temp=0x900f01c  *temp=0x900f028
 
In **delete()value found.Returning &temp=0xbff9a948 value=3
 
*ptr:0x900f008 and value:1 Pointing to:0x900f018
*ptr:0x900f018 and value:2 Pointing to:0x900f038
*ptr:0x900f038 and value:4 Pointing to:0x900f048
*ptr:0x900f048 and value:5 Pointing to:(nil)
 

The step *ptr=(*ptr)->next; is causing confusion.
value 2 is pointing to add 0x..28
value 3 is pointing to add 0x..38
value 4 is pointing to add 0x..48
3 was to be deleted which was at location 0x..28,whatever operation i did was at the location 0x..28(*ptr=(*ptr)->next),i didnt updated add 0x..18 to point to 0x..38 instead of 0x..28,then how it happened?

Basically i am getting confused what is happening via double pointer.If at 0x..28 location i am just copying next locations contents etc,then location 28 should have been retained.If i am loosing the track of 0x..28 then how 18 knew to point correctly to the next location?


I hope i am somewhat clear.

[weaknessforcats]

ptr is a pointer to a pointer to a node:

node **ptr;

Therefore, *ptr is a pointer to a node.

Therefore, (*ptr)-> next is the value of the member next in the node.

Therefore, *ptr = (*ptr)->next assigns the address in the next member of the node whose address is pointed at by ptr. This is a way to move down the list when you have the address of a node pointer.

[Ankit Khare]

I agree, what's happening in that line is similar to:

node *current
current=current->next

means exactly whats happening at *ptr=(*ptr)->next;
But using single pointer to the node,if you would have done
current=current->next,it wont effect the link list at all,it will remain as it is,but using double pointer this line
*ptr=(*ptr)->next is actually deleting the node.

How it is traversing is clear,but problem is,what i am returning from the delete function is the address of (the address of (the node to be deleted)) and then i am performing the above operation,so what is happening at the address of the to be deleted is the problem..

[weaknessforcats]

node **temp=&root; 
    while(*temp!=NULL) 
    { 
        if((*temp)->value==value) 
        { 
            flag =1; 
            break; 
        } 
        else 
            { 
              temp=&(*temp)->next; 
              printf("In else: temp=%p  *temp=%p\n",temp,*temp); 

From your code, temp has the address of the root. The root contains the address of a node.

It looks like you have one too many layers of indirection. I think you could code:

node* temp = root;

instead of:

node** temp = & root.

Then when you code:

temp=&(*temp)->next; 

you cold change that to:

temp = temp->next;

In any case, you are not deleting a node. All you are doing is returning when you find the node to delete but you are not actually deleting it.

If your list is A B C then when you delete B you must change A->next to C. That means whe you get to B in your delete function you still need to know the address of the node before B. Then you set the next of that node to the next of B.

[Ankit Khare]

I am retunrning temp back to main(),where i am holding this returned value in another node **ptr.,and then i am doing *ptr=(*ptr)->next;
Ok,i'll change the code a little bit,i am not returning temp any more.Now my delete function's protoype will be :

void delete(int value)
{
..
..same as before..
 if(flag==1)
         {
            *temp=(*temp)->next;
         }
}

this will also delete the required node.
As i have said earlier,i fully agree with you that if we'll take single layer pointer,it can be done via temp=temp->next; But using double pointer i am able to delete that node somehow using the above line

[Ankit Khare]

I am attaching the whole code,please somebody run it yourself and tell me about this issue.
In function delete,*ptr=(*ptr)->nextis deleting the node successfully,confusing part is not the traversing or what i am doing,but what is happening at the address of the node to be deleted

#include<stdio.h>
#include<stdlib.h>
 
typedef struct node{
int value;
struct node *next;
}node;
 
 
node *root=NULL;
node **ptr=&root;
 
node * getNode(int val)
{
    node *temp=malloc(sizeof(node));
 
    temp->value=val;
    temp->next=NULL;
    return temp;
 
}
 
 
 
void swap(node **ptr)
{
    node *temp;
    temp=((*ptr)->next)->next;
    ((*ptr)->next)->next=*ptr;
    *ptr=(*ptr)->next;
    ((*ptr)->next)->next=temp;
 
 
}
 
void sort()
{
    ptr=&root;
    int value1,value2;
    while(((*ptr)->next)!=NULL)
    {
        value1=(*ptr)->value;
        value2=(((*ptr)->next)->value);
        if(value1>value2)
        {
            swap(&(*ptr));
            ptr=&root;
        }
        else
            ptr=&(*ptr)->next;
    }
 
}
 
 
 
node addNodes(int value)
{
 
 
    if(root==NULL)
        root=getNode(value);
    else
    {
        (*ptr)->next=getNode(value);
        ptr=&(*ptr)->next;
 
    }
 
 
}
 
void display()
{
 
printf("\n");        
    ptr=&root;
    while(*ptr!=NULL)
    {
        printf("*ptr:%p and value:%d Pointing to:%p\n",*ptr,(*ptr)->value,(*ptr)->next);
        ptr=&(*ptr)->next;
    }
printf("\n");        
}
 
 
 
 
node **delete(int value)
{
    int flag=0;
    node **temp=&root;
    while(*temp!=NULL)
    {
        if((*temp)->value==value)
        {
 
 
            flag =1;
            break;
        }
        else
            {
            temp=&(*temp)->next;
            printf("In else: temp=%p  *temp=%p\n",temp,*temp);
            }
    }
    if(flag==1)
        {
 
            printf("\nIn **delete()value found.Returning &temp=%p value=%d\n",&temp,(*temp)->value);
 
            return temp;
        }
    else
        printf("\nNot found\n");
}
 
 
node *delete2(int value)
{
    int flag=0;
    node *temp=root;
    while(temp!=NULL)
    {
        if((temp)->value==value)
        {
            flag =1;
            break;
        }
        else
            temp=temp->next;
    }
    if(flag==1)
        {
            printf("In Delete:value Found &temp:%p\n",&temp);
            return temp;
        }
    else
        printf("\nNot found\n");
}
void main()
{
int loop=0;
 
node *temp;
addNodes(1);
addNodes(2);
addNodes(3);
addNodes(4);
addNodes(5);
 
display();
 
 ptr=delete(3);
 *ptr=(*ptr)->next;
 
display();
 
}
 
 

[weaknessforcats]

How does

*ptr=(*ptr)->next; 

delete a node? I mean the node was allocated with malloc but nowhere do I see a free() of that allocation.

The delete should occur inside the delete function. That is, if temp is the node to delete, then:

savetemp->next = temp->next;
free(temp);

where savetemp is the address of the node before temp (which you saved in the "if" statement inside the traverse loop).