Linked lists can be thought of from a high-level perspective as being a series of nodes. Each node has at least a single pointer to the next node and in the last node’s case a null pointer representing that there are no more nodes in the linked list.
A linked list, in simple terms, is a linear collection of data elements. These data elements are called nodes. A node is a collection of two sub-elements or parts. A data part that stores the element and a next part that stores the link to the next node.
Linked lists always maintain head and tail pointers so that insertion at either the head or tail of the list is a constant time operation.
As we can see in the above image linked list in which every node contains two parts, an integer and a pointer to the next node. The left part of the node which contains data may include a simple data type, an array, or a structure. The right part of the node contains a pointer to the next node (or address of the next node in sequence). The last node will have no next node connected to it, so it will store a special value called NULL.
- Linked Lists can be used to implement Stacks, Queues.
- Linked Lists can also be used to implement Graphs. (Adjacency list representation of Graph).
- Linked lists are useful for dynamic memory allocation.
- The real-life application where the circular linked list is used is our Personal Computers, where multiple applications are running.
Declaring linked list
In C, we can implement a linked list using the following code:
struct node
{
int data;
struct node *next;
};The above definition is used to create every node in the list. The data field stores the element and the next is a pointer to store the address of the next node.
Note: Linked lists provide an efficient way of storing related data and perform basic operations such as insertion, deletion, and updating of information at the cost of extra space required for storing the address of the next node.
Algorithms for Linked List operations
Algorithm for traversing a linked list
Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Steps 3 and 4 while PTR != NULL
Step 3: Apply Process to PTR DATA
Step 4: SET PTR = PTR NEXT
[END OF LOOP]
Step 5: EXITAlgorithm for inserting a node at the beginning of linked list
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 7
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL NEXT
Step 4: SET DATA = VAL
Step 5: SET NEW_NODE NEXT = START
Step 6: SET START = NEW_NODE
Step 7: EXITIn the above algorithm, we first check whether memory is available for the new node. If the free memory has exhausted, then an OVERFLOW message is printed. Otherwise, if a free memory cell is available, then we allocate space for the new node. Set its DATA part with the given VAL and the next part is initialized with the address of the first node of the list, which is stored in START. Now, since the new node is added as the first node of the list, it will now be known as the START node, that is, the START pointer variable will now hold the address of the NEW_NODE
Algorithm for Inserting a Node at the End of a Linked List
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 1
[END OF IF]
Step 2: SET = AVAIL
Step 3: SET AVAIL = AVAIL NEXT
Step 4: SET DATA = VAL
Step 5: SET NEW_NODE = NULL
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR NEXT != NULL
Step 8: SET PTR = PTR NEXT
[END OF LOOP]
Step 9: SET PTR NEXT = NEW_NODE
Step 10: EXITSuppose we want to add a new node as the last node of the list, So we can consider above algorithm for it, the changes from last last algorithm in this is, in Step 6 we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. In the while loop, we traverse through the linked list to reach the last node. Once we reach the last node, in Step 9, we change the NEXT pointer of the last node to store the address of the new node. Remember that the NEXT field of the new node contains NULL, which signifies the end of the linked list.
Algorithm for deleting the first node from the Linked List
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 5
[END OF IF]
Step 2: SET PTR = START
Step 3: SET START = START NEXT
Step 4: FREE PTR
Step 5: EXITIn Step 1, we check if the linked list exists or not. If START = NULL, then it signifies that there are no nodes in the list and the control is transferred to the last statement of the algorithm. However, if there are nodes in the linked list, then we use a pointer variable PTR that is set to point to the first node of the list. For this, we initialize PTR with START that stores the address of the first node of the list. In Step 3, START is made to point to the next node in sequence and finally the memory occupied by the node pointed by PTR (initially the first node of the list) is freed and returned to the free pool.
Algorithm for deleting the last node from the linked list
Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 8
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR NEXT != NULL
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR NEXT
[END OF LOOP]
Step 6: SET PREPTR NEXT = NULL
Step 7: FREE PTR
Step 8: EXITAbove algorithm shows procedure to delete the last node from a linked list. First we check if there is any Node in linked list or if it's empty, then we move on to Step 2, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. In the while loop, we take another pointer variable PREPTR such that it always points to one node before the PTR. Once we reach the last node and the second last node, we set the NEXT pointer of the second last node to NULL, so that it now becomes the (new) last node of the linked list. The memory of the previous last node is freed and returned back to the free pool.
Linked list program in C to insert, delete, display it
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <malloc.h>
struct node {
int data;
struct node * next;
};
// decalre all functions
struct node * start = NULL;
struct node * create_ll(struct node * );
struct node * display(struct node * );
struct node * insert_beg(struct node * );
struct node * insert_end(struct node * );
struct node * delete_beg(struct node * );
struct node * delete_end(struct node * );
struct node * delete_list(struct node * );
void main() {
int option;
do {
printf("\n\n *****MAIN MENU *****");
printf("\n 1: Create a list");
printf("\n 2: Display the list");
printf("\n 3: Add a node at the beginning");
printf("\n 4: Add a node at the end");
printf("\n 5: Delete a node from the beginning");
printf("\n 6: Delete a node from the end");
printf("\n 7: Delete the entire list");
printf("\n 8: EXIT");
printf("\n\n Enter your option : ");
scanf("%d", &option);
switch (option) {
case 1:
start = create_ll(start);
printf("\n LINKED LIST CREATED");
break;
case 2:
start = display(start);
break;
case 3:
start = insert_beg(start);
break;
case 4:
start = insert_end(start);
break;
case 5:
start = delete_beg(start);
break;
case 6:
start = delete_end(start);
break;
case 7:
start = delete_list(start);
printf("\n LINKED LIST DELETED");
break;
}
} while (option != 8);
getch();
}
//Create linked list function
//it will keep asking for data until -1 is entered
struct node * create_ll(struct node * start) {
struct node * new_node, * ptr;
int num;
printf("\n Enter -1 to end");
printf("\n Enter the data: ");
scanf("%d", & num);
while (num != -1) {
new_node = (struct node * ) malloc(sizeof(struct node));
new_node -> data = num;
if (start == NULL) {
new_node -> next = NULL;
start = new_node;
} else {
ptr = start;
while (ptr -> next != NULL)
ptr = ptr -> next;
ptr -> next = new_node;
new_node -> next = NULL;
}
printf("\n Enter the data : ");
scanf("%d", & num);
}
return start;
}
//display linked list data
//after looping it from start until NULL
struct node * display(struct node * start) {
struct node * ptr;
ptr = start;
while (ptr != NULL) {
printf("\t %d", ptr -> data);
ptr = ptr -> next;
}
return start;
}
//insert a node at beginning
struct node * insert_beg(struct node * start) {
struct node * new_node;
int num;
printf("\n Enter the data: ");
scanf("%d", & num);
new_node = (struct node *) malloc(sizeof(struct node));
new_node -> data = num;
new_node -> next = start;
start = new_node;
return start;
}
//insert a node at the end of linked list
struct node * insert_end(struct node * start) {
struct node * ptr, * new_node;
int num;
printf("\n Enter the data: ");
scanf("%d", &num);
new_node = (struct node * ) malloc(sizeof(struct node));
new_node -> data = num;
new_node -> next = NULL;
ptr = start;
while (ptr -> next != NULL)
ptr = ptr -> next;
ptr -> next = new_node;
return start;
}
//delete the first node of Linked list
struct node * delete_beg(struct node * start) {
struct node * ptr;
ptr = start;
start = start -> next;
free(ptr);
return start;
}
//delete the last node of linked list
struct node * delete_end(struct node * start) {
struct node * ptr, * preptr;
ptr = start;
while (ptr -> next != NULL) {
preptr = ptr;
ptr = ptr -> next;
}
preptr -> next = NULL;
free(ptr);
return start;
}
//delete list completly
struct node * delete_list(struct node * start) {
struct node * ptr;
if (start != NULL) {
ptr = start;
while (ptr != NULL) {
printf("\n %d is to be deleted next", ptr -> data);
start = delete_beg(ptr);
ptr = start;
}
}
return start;
}
The above program has various functions like Create linked list, delete a node from the beginning of linked list, adding a node at beiginning etc, I have commented out function's detail and compiled it online here is the output of it.
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the beginning
4: Add a node at the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete the entire list
8: EXIT
Enter your option : 1
Enter -1 to end
Enter the data: 22
Enter the data : 11
Enter the data : 456
Enter the data : 33
Enter the data : 77
Enter the data : -1
LINKED LIST CREATED
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the beginning
4: Add a node at the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete the entire list
8: EXIT
Enter your option : 5
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the beginning
4: Add a node at the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete the entire list
8: EXIT
Enter your option : 4
Enter the data: 89
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the beginning
4: Add a node at the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete the entire list
8: EXIT
Enter your option : 2
11 456 33 77 89
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the beginning
4: Add a node at the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete the entire list
8: EXIT
Enter your option : 6
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the beginning
4: Add a node at the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete the entire list
8: EXIT
Enter your option : 2
11 456 33 77
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the beginning
4: Add a node at the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete the entire list
8: EXIT
Enter your option : 3
Enter the data: 5
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the beginning
4: Add a node at the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete the entire list
8: EXIT
Enter your option : 2
5 11 456 33 77
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the beginning
4: Add a node at the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete the entire list
8: EXIT
Enter your option : 7
5 is to be deleted next
11 is to be deleted next
456 is to be deleted next
33 is to be deleted next
77 is to be deleted next
LINKED LIST DELETED
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the beginning
4: Add a node at the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete the entire list
8: EXIT
Enter your option : 2
*****MAIN MENU *****
1: Create a list
2: Display the list
3: Add a node at the beginning
4: Add a node at the end
5: Delete a node from the beginning
6: Delete a node from the end
7: Delete the entire list
8: EXIT
Enter your option : 8
You may also like:
Program & algorithm for Quick sort in C
Program for Matrix multiplication in C (With & Without pointers)
I hope your concept for linked list is much more clear after reading the above article, if you have any question's feel free to ask it in the comment's section below.
Buy us a coffee
Become a Patron