Linked lists are a fundamental and commonly employed type of data structure. They are versatile and can serve as the foundation for a range of well-known abstract data types like lists, stacks, queues, associative arrays, and S-expressions. Nonetheless, it is not uncommon to integrate these data structures independently without relying on a linked list as the base or primary data structure.
The main benefit of a linked list compared to a conventional array lies in its ease of inserting or deleting elements without the need to restructure the entire data structure. This is because the elements in a linked list are not required to be stored consecutively in memory or on disk, unlike arrays where runtime restructuring can be a costly process. Linked lists facilitate adding and removing nodes at any position in the list with a consistent number of steps by maintaining the link preceding the node being added or removed in memory while traversing the list. Nonetheless, simple linked lists lack support for direct access to data or efficient indexing, leading to tasks like accessing the last node, finding a specific node, or determining the insertion point for a new node requiring traversal through most or all elements in the list. The advantages and disadvantages of utilizing linked lists are detailed below.
A dynamic array functions as a data structure that stores elements contiguously in memory and keeps a record of the current element count. When the array exceeds its allocated capacity, it undergoes reallocation and potentially copying, which can be a costly process. Linked lists offer various advantages over dynamic arrays. When inserting or deleting an element at a specific position in a list, it is a constant-time operation (unless a pointer to the node has been indexed beforehand, either before the insertion point or the one to be removed). Conversely, inserting elements at random locations in a dynamic array typically involves moving an average of half the elements and all elements in the worst-case scenario. While it is feasible to mark an element's slot as "vacant" for constant-time deletion in an array, this approach leads to fragmentation that hinders iteration performance.
The direction of the pointers in linked list nodes is determined by the type of pointer associated with each node.
Types of Linked list
There are different types of linked lists, and some of the major types of linked lists are:
- Singly Linked list
- Doubly Linked list
- Circular Linked list
- Doubly Circular Linked list
Singly Linked list
In a singly linked list, each node points to the memory location of the next node in the list. This forms a chain where each node contains the address of the following node. The last node's pointer points to NULL, indicating the end of the linked list.
Now, we will examine an example code for constructing a singly linked list, inserting elements into the list, and subsequently traversing the singly linked list in the C programming language.
/* A sample C code to perform the following functions on Singly Linked list Insert, Delete, Display and Count Operations */
/* All Operations Example Program Using Functions in C*/
// stdio library is included to use the input output functionalities in the program
#include <stdio.h>
// the malloc library is included to dynamically allocate memory to the nodes of the Singly Linked list
#include <malloc.h>
#include <stdlib.h>
// a struct named node is defined that will represent the node of the Singly Linked list
// the struct object has two variables in it named value and next
struct node {
// the value variable is of integer type and will be used to store the value associated with that particular node of the Singly Linked list
int value;
// the next variable is of struct node* type and will be used to store the address of the next node of the Singly Linked list
struct node *next;
};
void insert();
void display();
void delete();
int count();
// the struct object named node is typedef with DATA_NODE for easier interpretation
typedef struct node DATA_NODE;
// An object of the DATA_NODE (which is struct node) named head_node is created and initialized with 0 that acts as the head node of the Singly Linked list.
DATA_NODE *head_node = 0;
// An object of the DATA_NODE (struct node) named first_node is created and initialized with 0, which acts as the first node of the Singly Linked list.
DATA_NODE *first_node = 0;
// An object of the DATA_NODE (which is struct node) named temp_node is created and initialized with 0 that will be used to store the node of the Singly Linked list temporarily.
DATA_NODE *temp_node = 0;
// An object of the DATA_NODE (which is struct node) named next_node,prev_node is created that will be used to temproray store the node of Singly Linked list.
DATA_NODE *prev_node;
DATA_NODE next_node;
// a variable named data of integer type is created to store the value associated with that particular node of the Singly Linked list
int data;
// A function named insert is written to add a new node to the Singly Linked list
void insert() {
// Data to be associate with that particular node of the Singly Linked list is taken as input from the user
printf("\nEnter Element for Insert Linked list : \n");
// the data enetred by the user is stored in the data variable
scanf("%d", &data);
// a temporary node is created with the added new data by the user, and this new temporary node is allocated memory by using the malloc function
temp_node = (DATA_NODE *) malloc(sizeof (DATA_NODE));
// now the data added by the user is associated with this particular new temproray node
temp_node->value = data;
// while inserting a new node to the Singly linked list, it is checked whether the first_node is zero or not,
// if first_node is zero, that means there are no nodes present in the Singly Linked list at that time, so that
// new node is added at the start of the Singly Linked list, which will act as the head of the Linked list
// if the first_node is not zero, then the new node is added after that already existing node
// this if condition will check the value of first_node varible
if (first_node == 0) {
// if value of first_node varible is zero then it will become the head of the Singly Linked list
first_node = temp_node;
} else {
// if the value is not zero, then the address of this new node will be added to the pointer of the already last existing node in the Singly Linked list
head_node->next = temp_node;
}
// and the address that is stored in the newly added node is 0 representing it to be the last node of the Singly Linked list
temp_node->next = 0;
head_node = temp_node;
fflush(stdin);
}//end of the insert function
// A function named delete was written to delete a node from the Singly Linked list
void delete() {
int countvalue = 0;
int pos = 0;
int i = 0;
countvalue = count();
temp_node = first_node;
printf("\nDisplay Linked list : \n");
// The position of the node that we want to delete from the Singly Linked list is taken as input from the user
printf("\nEnter Position for Delete Element : \n");
// The position of the node that we want to delete from the Singly Linked list entered by the user is stored in the pos variable
scanf("%d", &pos);
// Now, for deleting a node from the Singly Linked list, first we need to traverse to that position and then delete that node from the Singly Linked list
// By deleting, we mean to add the pointer of the previous node to the next node of the node whose position is entered by the user.
if (pos > 0 && pos <= countvalue) {
// this is the case when the user wants to delete the head node of the Singly Linked list
if (pos == 1) {
temp_node = temp_node -> next;
first_node = temp_node;
// Once the node is deleted a message is displayed to the user
printf("\nDeleted Successfully \n\n");
} else {
while (temp_node != 0) {
if (i == (pos - 1)) {
prev_node->next = temp_node->next;
if(i == (countvalue - 1))
{
head_node = prev_node;
}
// Once the node is deleted a message is displayed to the user
printf("\nDeleted Successfully \n\n");
break;
} else {
i++;
prev_node = temp_node;
temp_node = temp_node -> next;
}
}
}
// if the position that is entered by the user is out of the range of the length of the Singly Linked list then an error message saying Invalid position is displayed
} else
printf("\nInvalid Position \n\n");
}// end of delete function
// A function named display is written to print the data in the nodes of the Singly Linked list
void display() {
//an integer variable named count is initialized with zero that will keep the total count of the number of nodes in the Singly Linked list
int count = 0;
// the temp_node variable is initialized with the first_node variable, which is the first node of the Singly Linked list
temp_node = first_node;
printf("\nDisplay Linked list : \n");
// The Singly Linked list is traversed untill the last element of the Singly Linked list is encountered
while (temp_node != 0) {
// while traversing the Singly Linked list the data present in the each node of the Singly Linked list is printed
printf("# %d # ", temp_node->value);
// the count variable is incremented after traversing each node of the Singly Linked list
count++;
temp_node = temp_node -> next;
}
// after traversing each node of the Singly Linked list, the total count of the number of nodes in the Singly Linked list is printed
printf("\nNo Of Items In Linked list : %d\n", count);
}// end of display function
// A function named count is written to count the total number of nodes in the Singly Linked list
int count() {
//an integer variable named count is initialized with zero that will keep the total count of the number of nodes in the Singly Linked list
int count = 0;
// the temp_node variable is initialized with the first_node variable, which is the first node of the Singly Linked list
temp_node = first_node;
// The Singly Linked list is traversed until the last element of the Singly Linked list is encountered
while (temp_node != 0) {
// the count varible is incremented after traversing each node of the Singly Linked list
count++;
temp_node = temp_node -> next;
}
// after traversing each node of the Singly Linked list, the total count of the number of nodes in the Singly Linked list is printed
printf("\nNo Of Items In Linked list : %d\n", count);
return count;
}// end of count function
// main function is written to call all the functionalities functions of the Singly Linked list written above
int main() {
char ch;
// Do-while loop
// Do part for performing actions
do
// Menu is displayed
// Users enter 'y' to continue 'n' if
// entered by user , the program terminates
{
// Menu
// Display messages
printf("Please Choose one of the Operations::\n");
printf("1. To Insert Data in the Singly Linked list.\n");
printf("2. To Delete Data from the Singly Linked list.\n");
printf("3. To Display Data present in the Singly Linked list.\n");
printf("4. To Display the count of nodes in the Singly Linked list.\n");
printf("\n");
int choice;
scanf("%d",&choice);
// Switch case
switch (choice) {
// Case 1
case 1:
insert();
// Display message
printf("Data Added Sucessfully.\n");
// Break statement to terminate a case
break;
// Case 2
case 2:
// Display message
delete();
// Break statement to terminate a case
break;
// Case 3
case 3:
// Display message
display();
// Break statement to terminate a case
break;
// Case 2
case 4 :
// Display message
count();
// Break statement to terminate a case
break;
default:
// Print statement
printf("Please enter a valid option from the menu to proceed further.\n \n");
// Break statement
break;
}
printf("\nType [N or n] to terminate the program.\nType [Y or y] to continue the program.\n");
scanf(" %c",&ch);
} while (!(ch == 'N' || ch == 'n'));
return 0;
}// end of main function
Output:
The above code gives the following output:
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
1
Enter Element for Insert Linked list:
2
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
1
Enter Element for Insert Linked list:
3
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
1
Enter Element for Insert Linked list:
6
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
1
Enter Element for Insert Linked list:
89
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
1
Enter Element for Insert Linked list:
56
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
1
Enter Element for Insert Linked list:
31
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
1
Enter Element for Insert Linked list:
78
Data Added Successfully.
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
3
Display Linked list:
# 2 # # 3 # # 6 # # 89 # # 56 # # 31 # # 78 #
No Of Items In Linked list: 7
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
2
No of Items In Linked list: 7
Display Linked list:
Enter Position for Delete Element:
4
Deleted Successfully
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
3
Display Linked list:
# 2 # # 3 # # 6 # # 56 # # 31 # # 78 #
No Of Items In Linked list: 6
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
y
Please Choose one of the Operations::
1. To Insert Data in the Singly Linked list.
2. To Delete Data from the Singly Linked list.
3. To Display Data present in the Singly Linked list.
4. To Display the count of nodes in the Singly Linked list.
4
No of Items in Linked list: 6
Type [N or n] to terminate the program.
Type [Y or y] to continue the program.
n
In the preceding code snippet, various functions were implemented to handle distinct operations within the linked list structure. These functions include adding a new node to the linked list, showcasing the data stored in all nodes of the list, removing a specific node at a defined position, and determining the total count of nodes within the linked list.
When adding a new node to a singly linked list, the initial node's value is checked to determine if it is zero or not. If the first node is zero, indicating an empty linked list, a new node is inserted at the beginning to serve as the head node. However, if the first node is not zero, the new node is appended after the existing last node.
To delete a node from the linked list, the user provides the index of the node to be removed. The process involves traversing the list to locate the specified node. Once found, the preceding node must be adjusted to point to the node following the one to be deleted.
For displaying the data stored in each node, the traversal starts from the head node and continues until the last node, presenting the data within each node along the way. The same method is applied when determining the total node count in the linked list.