Why use double pointer when adding node to Linked List? This question struck my mind when i first read about Linked Lists in my Second Semester. At that time i didnt gave it much thought. But from past 1 week i wanted the answer of this question. I googled it, but forums were full of nasty definitions of pointers and their usage, asked my seniours but they told me the bookish reasons which didnt made me satisfied, so i decided to do some experiments and make some conclusion......
OBSERVATION 1- If the linked list is not empty then we can add the nodes in it (obviously at the end) by using a single pointer only.
int insert(struct LinkedList *root, int item)
{
struct LinkedList *temp;
temp= (struct LinkedList *)malloc(sizeof(struct LinkedList));
temp->data=item;
temp->next=NULL;
struct LinkedList *p;
p=root;
while(p->next!=NULL)
{
p=p->next;
}
p->next=temp;
return 0;
}
int main()
{
int m;
A=(struct LinkedList *)malloc(sizeof(struct LinkedList));
//now we want to add one element to the list so that the list becomes non-empty
A->data=5;
A->next=NULL;
cout<<"enter the element to be inserted\n";
cin>>m;
insert(A,m);
return 0;
}
Its simple to explain. We have a pointer in our main function which points to the first node (or root) of the list. In the insert() function we pass the address of the root node and using this address we reach the end of the list and add a node to it. So we can conclude that if we have address of a variable in a function (not the main function) we can make permanent changes in the value of that variable from that function which would reflect in the main function.
OBSERVATION 2- The above method of adding node failed when the list was empty.
int insert(struct LinkedList *root, int item)
{
struct LinkedList *temp;
temp= (struct LinkedList *)malloc(sizeof(struct LinkedList));
temp->data=item;
temp->next=NULL;
struct LinkedList *p;
p=root;
//check if list is empty
if(p==NULL)
{
p=temp;
}
else
{
while(p->next!=NULL)
{
p=p->next;
}
p->next=temp;
}
return 0;
}
int main()
{
int m;
A=NULL;//initialise the list to be empty
cout<<"enter the element to be inserted\n";
cin>>m;
insert(A,m);
return 0;
}
If you keep on adding elements and finally display the list then u would find that the list has undergone no changes and still it is empty.
The question which struck my mind was in this case also we are passing the address of the root node then why modifications are not happening as permanent modifications and list in the main function undergoes no changes. WHY? WHY? WHY?
Then i observed one thing, when i write A=NULL the address of A becomes 0. This means now A is not pointing to any location in memory. So i removed the line
int insert(struct LinkedList *root, int item)
{
root= (struct LinkedList *)malloc(sizeof(struct LinkedList));
root->data=item;
root->next=NULL;
return 0;
}
int main()
{
int m;
cin>>m;
insert(A,m);
return 0;
}
the above method also fails because in the insert() function root stores same address as A in the main() function but after the line root= (struct LinkedList *)malloc(sizeof(struct LinkedList)); the address stored in root changes. Thus ,now , root (in insert() function) and A (in main() function) store different addresses.
SO THE CORRECT FINAL PROGRAM WOULD BE...
int insert(struct LinkedList *root, int item)
{
root->data=item;
root->next=NULL;
return 0;
}
int main()
{
int m;
OBSERVATION 1- If the linked list is not empty then we can add the nodes in it (obviously at the end) by using a single pointer only.
int insert(struct LinkedList *root, int item)
{
struct LinkedList *temp;
temp= (struct LinkedList *)malloc(sizeof(struct LinkedList));
temp->data=item;
temp->next=NULL;
struct LinkedList *p;
p=root;
while(p->next!=NULL)
{
p=p->next;
}
p->next=temp;
return 0;
}
int main()
{
int m;
struct LinkedList *A;
A=(struct LinkedList *)malloc(sizeof(struct LinkedList));
//now we want to add one element to the list so that the list becomes non-empty
A->data=5;
A->next=NULL;
cout<<"enter the element to be inserted\n";
cin>>m;
insert(A,m);
return 0;
}
Its simple to explain. We have a pointer in our main function which points to the first node (or root) of the list. In the insert() function we pass the address of the root node and using this address we reach the end of the list and add a node to it. So we can conclude that if we have address of a variable in a function (not the main function) we can make permanent changes in the value of that variable from that function which would reflect in the main function.
OBSERVATION 2- The above method of adding node failed when the list was empty.
int insert(struct LinkedList *root, int item)
{
struct LinkedList *temp;
temp= (struct LinkedList *)malloc(sizeof(struct LinkedList));
temp->data=item;
temp->next=NULL;
struct LinkedList *p;
p=root;
//check if list is empty
if(p==NULL)
{
p=temp;
}
else
{
while(p->next!=NULL)
{
p=p->next;
}
p->next=temp;
}
return 0;
}
int main()
{
int m;
struct LinkedList *A;
A=NULL;//initialise the list to be empty
cout<<"enter the element to be inserted\n";
cin>>m;
insert(A,m);
return 0;
}
If you keep on adding elements and finally display the list then u would find that the list has undergone no changes and still it is empty.
The question which struck my mind was in this case also we are passing the address of the root node then why modifications are not happening as permanent modifications and list in the main function undergoes no changes. WHY? WHY? WHY?
Then i observed one thing, when i write A=NULL the address of A becomes 0. This means now A is not pointing to any location in memory. So i removed the line
A=NULL; and made some modification in the insert function...
some modifications......(below insert() function can add only one element to an empty list,, just wrote this function for testing purpose)
int insert(struct LinkedList *root, int item)
{
root= (struct LinkedList *)malloc(sizeof(struct LinkedList));
root->data=item;
root->next=NULL;
return 0;
}
int main()
{
int m;
struct LinkedList *A;
cout<<"enter the element to be inserted\n";cin>>m;
insert(A,m);
return 0;
}
the above method also fails because in the insert() function root stores same address as A in the main() function but after the line root= (struct LinkedList *)malloc(sizeof(struct LinkedList)); the address stored in root changes. Thus ,now , root (in insert() function) and A (in main() function) store different addresses.
SO THE CORRECT FINAL PROGRAM WOULD BE...
int insert(struct LinkedList *root, int item)
{
root->data=item;
root->next=NULL;
return 0;
}
int main()
{
int m;
struct LinkedList *A;
A= (struct LinkedList *)malloc(sizeof(struct LinkedList));
cout<<"enter the element to be inserted\n";
cin>>m;
insert(A,m);
return 0;
}
But we dont want two different functions for insertion , one when list is empty and other when list is not empty. Now comes double pointer which makes things easy.
now pls give ur full attention,
lets see what double pointer can do,
ONE THING I NOTICED WHICH IS IMPORTANT IS THAT POINTERS STORE ADDRESS AND WHEN USED WITH '*' THEY GIVE VALUE AT THAT ADDRESS BUT POINTERS THEMSELVES HAVE THEIR OWN ADDRESS.
for example-
if we write int *a,p; a=&p; then *a would give value of p, a would give address of p, and &a would give address of pointer a.
now i would first give the complete program and then explain the concepts.....
int insert(struct LinkedList **root,int item)
{
if(*root==NULL)
{
(*root)=(struct LinkedList *)malloc(sizeof(struct LinkedList));
(*root)->data=item;
(*root)->next=NULL;
}
else
{
struct LinkedList *temp=(struct LinkedList *)malloc(sizeof(struct LinkedList));
temp->data=item;
temp->next=NULL;
struct LinkedList *p;
p=*root;
while(p->next!=NULL)
{
p=p->next;
}
p->next=temp;
}
return 0;
}
int main()
{
int n,m;
struct LinkedList *A=NULL;
cout<<"enter the no of elements to be inserted\n";
cin>>n;
while(n--)
{
cin>>m;
insert(&A,m);
}
display(A);
return 0;
}
following are the observations->
1. root stores the address of pointer A (&A) , *root stores the address stored by pointer A and **root stores the value at address stored by A. In simple language root=&A, *root= A and **root= *A.
2. if we write *root= 1528 then it means that value at address stored in root becomes 1528 and since address stored in root is the address of pointer A (&A) thus now A=1528 (i.e. address stored in A is 1528) and this change is permanent.
whenever we are changing value of *root we are indeed changing value at address stored in root and since root=&A ( address of pointer A) we are indirectly changing value of A or address stored in A.
so now if A=NULL (list is empty) *root=NULL , thus we create the first node and store its address at *root i.e. indirectly we storing the address of first node at A. If list is not empty , everything is same as done in previous functions using single pointer except we have changed root to *root since what was stored in root is now stored in *root.
cout<<"enter the element to be inserted\n";
cin>>m;
insert(A,m);
return 0;
}
But we dont want two different functions for insertion , one when list is empty and other when list is not empty. Now comes double pointer which makes things easy.
now pls give ur full attention,
lets see what double pointer can do,
ONE THING I NOTICED WHICH IS IMPORTANT IS THAT POINTERS STORE ADDRESS AND WHEN USED WITH '*' THEY GIVE VALUE AT THAT ADDRESS BUT POINTERS THEMSELVES HAVE THEIR OWN ADDRESS.
for example-
if we write int *a,p; a=&p; then *a would give value of p, a would give address of p, and &a would give address of pointer a.
now i would first give the complete program and then explain the concepts.....
int insert(struct LinkedList **root,int item)
{
if(*root==NULL)
{
(*root)=(struct LinkedList *)malloc(sizeof(struct LinkedList));
(*root)->data=item;
(*root)->next=NULL;
}
else
{
struct LinkedList *temp=(struct LinkedList *)malloc(sizeof(struct LinkedList));
temp->data=item;
temp->next=NULL;
struct LinkedList *p;
p=*root;
while(p->next!=NULL)
{
p=p->next;
}
p->next=temp;
}
return 0;
}
int main()
{
int n,m;
struct LinkedList *A=NULL;
cout<<"enter the no of elements to be inserted\n";
cin>>n;
while(n--)
{
cin>>m;
insert(&A,m);
}
display(A);
return 0;
}
following are the observations->
1. root stores the address of pointer A (&A) , *root stores the address stored by pointer A and **root stores the value at address stored by A. In simple language root=&A, *root= A and **root= *A.
2. if we write *root= 1528 then it means that value at address stored in root becomes 1528 and since address stored in root is the address of pointer A (&A) thus now A=1528 (i.e. address stored in A is 1528) and this change is permanent.
whenever we are changing value of *root we are indeed changing value at address stored in root and since root=&A ( address of pointer A) we are indirectly changing value of A or address stored in A.
so now if A=NULL (list is empty) *root=NULL , thus we create the first node and store its address at *root i.e. indirectly we storing the address of first node at A. If list is not empty , everything is same as done in previous functions using single pointer except we have changed root to *root since what was stored in root is now stored in *root.
