A linked list is an example of a linear data structure. It is stored the data dynamically using the structure and pointers. Linked-list enables the user to store the desired data to create a new location in the program at run time.
In simple word, we can say that linked list is a sequence of data structures or sequence of links. These data structures are connected together through the links.
There are two data types attached with linked list one is the node and second one is the node pointer. Each node is contained two things one is the data field and the second one is the node pointer.
Note: Here in the node, the data field is used to store the desired data and node pointer is used to point the address of the next node in linked list.
Representation of Node in linked list:
Generally, in c language, we use a structure to create a node of a linked list. These structures contain at least a data field and self-referential pointer. Here we can use the data field to store the data and the self-referential pointer (node pointer) to point the next node.
In the linked list each node has assigned the memory in the heap to calling a library function malloc(). So that is the reason each node is alive until not explicitly deallocated the memory of each node by the calling of free().
Representation of linked list:
A linked list is the sequence of the nodes. The first node of the linked list is pointed by a pointer which is called start or head pointer. If there is no node in the linked list then this type of linked list is called empty linked list and head should be pointed to NULL.
In the above Image, I am creating a linked list of the four nodes. The beginning of the list is stored in the head pointer (node pointer) which point to the first node.
The first node contains the “3” and the address of the second node. Similar to the first node second node contain the “10” and the address of the third node. This process is same till the last node. The last node contains the “1” and the NULL pointer. The NULL pointer is the mark of the end of the list. So in every linked list, the last node must contain the NULL pointer.
Why use Linked List
Linked list is a serial data structure like an array, the main reason to use the linked list in the program that in linked list elements can easily be inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk.
In the case of the array the size of the array is fixed, so we need to know the size of the array before inserting the new element, beside it a linked list provide the flexibility to the user to add and remove the node any time and any situation.
Let’s take an example for the better understanding. Suppose here is a sorted integer array “aiSallary” which contains the salary of five employees.
int aiSallary [10] = { 400, 1200 , 2000 , 4500 , 5000 };
If suppose a new person is joined to the company and his salary is 1800. So to place the salary of a new employee in “aiSallary” is very hard because you have to first shift all salary which greater than 1800. We can perform this task very easily with the help of the linked list.
Advantages of the linked list
- A Linked list is a dynamic data structure, we can increase or decrease the number of the node from the linked list at the run time of the program.
- Insertion and deletion operations are very easy in a linked list.
- As like the array, we don’t need to give the size of the linked list.
- We can easily add or remove the node from the middle of a list.
- We can implement the stacks and queues using the linked list.
Disadvantages of the linked list
- In linked list, every node contains an extra node pointer to point the next node, so it uses more memory as compare to the array.
- In linked list we cannot access the data randomly, every time we need to start the data tracing from the beginning because it does not contains the data in contiguous format.
- The nodes do not store in contiguous format, so more time is required to access the individual elements from the list.
- In linked list reverse traversing is difficult as compare to the array but in the case of doubly linked list reverse traversing is easy but it takes two extra pointers one for next node and second for the previous node.
Sample program to describe the Linked list
In the below program, I am creating a list of 4 nodes. Each node contains the integer data and node pointer to point the next node.
// A simple C program to introduce a linked list
#include<stdio.h>
#include<stdlib.h>
// Creating Node
struct Node
{
int iData;
struct Node *pNextNode;
};
// Define the new type Node type and Node pointer
typedef struct Node NodeType, * NodePointer;
// This function use to prints the data of the list from the begning
//to the given list.
void PrintTheList(struct Node *pNode)
{
int iCountOfNode = 0;
while (pNode != NULL)
{
printf("\nValue of %d Node = %d\n", ++iCountOfNode , pNode->iData);
pNode = pNode->pNextNode;
}
}
// Program to create linked-list of 4 node
int main(void)
{
// Head or Start pointer
NodePointer pHead = NULL;
//first Node
NodePointer pFirstNode = NULL;
//Second Node
NodePointer pSecondNode = NULL;
//Third Node
NodePointer pThirdNode = NULL;
//Fourth Node
NodePointer pFourthNode = NULL;
// allocate 4 nodes in the heap
pFirstNode = malloc(sizeof(NodeType));
pSecondNode = malloc(sizeof(NodeType));
pThirdNode = malloc(sizeof(NodeType));
pFourthNode = malloc(sizeof(NodeType));
/* Four blocks have been allocated dynamically using the malloc and
these allocated block are pointed by the node pointters pFirstNode, pSecondNode , pThirdNode
and pFourthNode.
pFirstNode pSecondNode
| |
| |
+-----+-------+ +-----+---------+
|Data | Address| | Data | Address|
+-----+-------+ +------+--------+
pThirdNode pFourthNode
| |
| |
+-----+-------+ +-----+---------+
|Data | Address| | Data | Address|
+-----+-------+ +------+--------+
*/
pFirstNode->iData = 3; //assign 3 in iData of first node
pFirstNode->pNextNode = pSecondNode; // Assign Address of Second Node
pHead = pFirstNode; // Assign Address of first node to head pointer
/*
pFirstNode pSecondNode
| |
| |
+-----+-------+ +-----+---------+
pHead---------->| 3 | |----->| Data | Address|
+-----+-------+ +------+--------+
*/
pSecondNode->iData = 10; //assign 10 in iData of second node
pSecondNode->pNextNode = pThirdNode; //Assign Address of third Node
/*
pFirstNode pSecondNode pThirdNode
| | |
| | |
+-----+-------+ +------+------+ +-----+---------+
pHead---------->|3 | |----->| 10 | |------>| Data | Address|
+-----+-------+ +------+------+ +------+--------+
*/
pThirdNode->iData = 2; //assign 2 in iData of third node
pThirdNode->pNextNode = pFourthNode; //Assign Address of fourth Node
/*
pFirstNode pSecondNode pThirdNode pSecondNode
| | | |
| | | |
+-----+-------+ +------+--------+ +-----+------+ +-----+---------+
pHead---------->|3 | |----->| 10 | |------>| 2 | |----->| Data | Address|
+-----+-------+ +------+--------+ +------+-----+ +------+--------+
*/
pFourthNode->iData = 1; //assign 1 in iData of fourth node
pFourthNode->pNextNode = NULL; //Assign NULL to indicate that linked list is terminated here.
/*
pFirstNode pSecondNode pThirdNode pSecondNode
| | | |
| | | |
+-----+-------+ +------+--------+ +-----+------+ +-----+--------+
pHead---------->|3 | |----->| 10 | |------>| 2 | |----->| 1 | NULL|
+-----+-------+ +------+--------+ +------+-----+ +------+-------+
*/
//Print The Linked list
PrintTheList(pHead);
// After the use of linked-list explicitly delete the all nodes
free(pFirstNode);
pFirstNode = NULL;
free(pSecondNode);
pSecondNode = NULL;
free(pThirdNode);
pThirdNode = NULL;
free(pFourthNode);
pFourthNode = NULL;
pHead = NULL;
return 0;
}
OutPut:
