Just as an array is used to store elements in the memory linked list is also used to store something but both arrays and linked lists have their own advantages and disadvantages.
A lined list is make up of nodes and a node is divided into two parts the link part and the info part as shown in the fig.
The info part of the linked list contains the actual data, the data can be in form of an int value, float, char etc..
and the link part of the list contains the address of the next node in the list.
In the image above, there is a linked list made up of thee nodes. 1001, 1006 and 1009 are the addresses of each node respectively. You may see first node contains the address of the second node ie; 1006, second node contains the address of the third node ie; 1009 and because the third node is the last node in the list it has no next node so it has NULL in its link field. NULL has a predefined meaning in c language, it means empty or nothing.
If there is only one node in the linked list then that node is the first node as well as the last node and its link field will be NULL.
Each node stores the address of its next node but who stores the address of the first node ?
For this we have a start pointer, start is a pointer variable which stores the address of the first node in the list.
The general form of a node of a linked list
struct node {
          int info;                       /*** data type <name>***/
          struct node * link;        Â
         };
Structures will be used in linked list programs as used in the above example a short tutorial on structures if you are not familiar with it. https://youtu.be/JSSTnytdJUI
info is just a variable info part of the node which stores the data in form of an integer value and link is a pointer variable of type struct node which stores the address of the next node.
Empty condition
When the value of start is equal to null then the linked list is empty.
In the program initially we initialize the value of start to be equal to NULL and later when new nodes are added or deleted then the value of start changes accordingly.
struct node *start = NULL;
Traversing a linked list:Traversing means visiting nodes of a linked list in sequence starting from the first node one after the other.
Remember that linked list does not allow random access it only allows sequential access. So if there are 5 nodes in a linked list and we want to access the 4th node then starting from the first node we have to go through nodes 1, 2 and 3 to reach and access the 4th node, direct access to the nodes cannot take place in a linked list therefore traversal is important.
Lets take an example, in the above fig. there is a linked liked with three nodes. Lets say the user wants to visit the 3rd node in the list. This is how traversal is done.
Start pointer variable has the address of the first node, first node is the entry point into the linked list.
We declare another pointer variable and assign it the value of start which is the address of the first node.
struct node *p;
p = start;
while(p != NULL)
{
p = p->link;
}
The above while loop means as long as p is not equal to null keep on executing p = p-> link.
-> called the arrow operator and it is used to access the members of the structure using pointer variable. Shot tutorial on arrow operator https://youtu.be/J2iHTv5VVgg
Refer to the image above first time the while loop runs the value of p is 1001 which means the first node and p -> link means link part of that node and the link of that node is 1005.
p -> link evaluates to 1005 address of the second node.
So in the statement p = p -> link pointer variable p is assigned 1005.
Second time the while loop runs
Value of p will be 1005, p means second node and the link part of the second node p->link is 1008 ie; the address of the third node.
p will be assigned the address of the next node p = p -> link;
Third time the while loop runs
Value of p will be 1008
p = p -> link
p will be assigned p -> link which is the link part of that node and this time the link part is NULL so now p is equal to NULL.
Now all the nodes of the list have been visited, we don’t need any more traversing.
Fourth time the while loop runs
P is equal to NULL while loop becomes false and terminates.
Now that we know traversal we can easily create display function for our program on linked list by adding a simple printf function.
void display(struct node *start)
{
struct node *p;
if(start==NULL)
{
printf("nList is emptyn");
return;
}
p=start;
printf("List is : n");
while(p != NULL)
{
printf("%d ", p->info);
p=p->link;
}
}
p->info will will access whatever value is stored in the info variable of the structure or you can say info part of the node and printf function will print it each time the while loop runs while p is not equal to null.
p = p->link will move p to the next node each time the loop runs.
Adding a new node (insertion):
Adding a node at the beginning of the list or to an empty list. Initially a linked list is always empty.
The same code is enough to add nodes at the beginning of the list as well as into an empty list.
struct node *addatbeg(struct node *start, int num)
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->info=num;
temp->link = start;
start = temp;
return start;
}
In the above code first we declare a pointer variable temp.
The malloc() function is used for dynamic memory allocation. In simple words here it allocates memory for the new node and returns the address of that memory location, the address is then assigned to pointer variable temp. Tutorial on malloc() function https://youtu.be/B4NRsJhM9WA
So temp has the address of the new node.
temp->info=num
temp->info means the info part of the new node which is assigned the value of num, the value is entered by user using scanf function in the main() and passed as an argument in the addatbeg() function
Now placing the new node into the list.
       temp->link = start;
Start has the address of the first node or if the list is empty then start is equal to NULL.
The new node temp which is added into the list will become the first node in the list.
If the list was previously empty then NULL will be assigned to the link part of the new node with the help of the statement temp->link = start;
Or if the list was previously not empty then the address of the next node will be assigned to the link part of the new node with the help of the same statement temp->link = start;
start = temp;
start should always hold the address of the first node and since the new node temp is the first node in the list so start is assigned its address.
return start;
The value of start has changed so it needs to be updated. The returned value of start goes into the main function and updates the value of start so that the next time if addatbeg function is called from the main() then the correct updated value of start is passed.
Adding a node at the end of a linked list
void addatend(struct node *start, int num)
{
struct node *temp, *p;
temp=(struct node *)malloc(sizeof(struct node));
temp->info=num;
p=start;
while(p->link!=NULL)
{
p = p->link;
}
p->link = temp;
temp->link = NULL;
}
The first three lines in the code is the same that was used in the previous case.
The while loop and p=p->link statement is used for traversal because first we need to reach the last node in the list then only we can insert a node at the end.
When p will be at the last node of the list then p->link will be equal to null which will make the while condition false, terminate the while loop and the following two statements will get executed.
          p->link = temp;
temp is the newly created node and its address will be assigned to the link part of node p which will now become the second last node in the list and temp will become the last node in the list and the link part of the last node should always be null and the following statement will ensure that.
          temp->link = NULL;
Here we don’t need to return start because as opposed to the previous case here adding a node at the end of the list does not change the value of start.
Deletion
In deletion the node to be deleted is passed by the user through scanf function in the main(). The node to be deleted is recognized by the data it contains. So if there is a node that contains integer value 25 in its info part and the user enters 25 to be deleted then that node would get deleted.
struct node *del(struct node *start,int num)
{
struct node *tmp,*p;
if(start==NULL)
{
printf("List is emptyn");
return start;
}
if(start->info==num) /*deletion from first or only node*/
{
tmp=start;
start=start->link;
free(tmp);
return start;
}
p=start;
while(p->link!=NULL)
{
if(p->link->info==num)
{
tmp = p->link;
p->link = tmp->link;
free(tmp);
return start;
}
p=p->link;
}
printf("%d not presentn",num);
return start;
}
if(start->info==num)Â Â Â Â Â Â Â Â /*deletion from first or only node*/
{
tmp=start;
start=start->link;
free(tmp);
return start;
}
This part of the delete function handles the situation where the node to be deleted is the first node in the list.
This if condition if(start->info==num) will become true if the number entered by the user is equal to the info part of the first node because start holds the address of the first node.
start=start->link;
start->link means the link part of the first node which contains the address of the next node or the second node. It is assigned to start so the second node becomes the first node.
free(tmp);
Since memory is dynamically allocated in case of a linked list and dynamically allocated memory is not freed automatically so we have to free the memory by using free() function.
return start;
When the first node is changed the value of start also changes so we need to return the value so that it gets updated in the main() function.
The return statement here also help us to get out of del() function after deletion is performed.
If the node to be deleted is not the first node then traversing will take place each node with be checked.
if(p->link->info==num)
p->link->info means the info part of the next node. If info part of the next node is equal to the number entered by the user (num) then the condition becomes true and node is deleted from anywhere in the list except the first node. It can also delete the last node in the list.
The following code will get executed if the above if condition becomes true.
tmp = p->link;
p->link = tmp->link;
free(tmp);
return start;
If the number is present p will stop right before the node to be deleted.
tmp = p->link  Assign tmp the address of node which is going to be deleted in the above image it is p->link ie 1008
p->link = tmp->link;Â tmp is 1008 ie; last node and its link part is NULL so null will be assigned to the second last node thus making it the last node in the list. Imagine if tmp was not the last node then also this code would have done its job the address of the next node would have been assigned to p->link instead of null, removing node tmp.
return start;
Value of start doesn’t get changed but still we need to return some value because the del() function is not of type void and return statement helps the program control to get out of delete fucking after the job is completed.
If the while condition becomes false it would mean that the number or node to be deleted is not present in the list and printf(“%d not presentn”,num); number not present will be displayed to the user.
