Observation and Finding,* why...
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 = (struct LinkedList*)malloc(sizeof(struct LinkedList));
temp->data=item;
temp->next=NULL;
struct LinkedList *p = root;
while(p->next!=NULL){
p=p->next;
}
p->next=temp;
return 0;
}
int main(){
int m;
struct LinkedList *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;
}
It’s simple to explain (basic). We have a pointer in our main function which points to the first node (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 = (struct LinkedList*)malloc(sizeof(struct LinkedList));
temp->data=item;
temp->next=NULL;
struct LinkedList *p=root;
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=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 you 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 (the 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 = (struct LinkedList *)malloc(sizeof(struct LinkedList));
cout<<"enter the element to be inserted\n";
cin>>m;
insert(A,m);
return 0;
}
But we don’t 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.
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.
Now here is the complete program and later 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.
