Data structures are essential concepts in programming languages. They help developers store data easily and organize it efficiently in computer memory. There are many data structures, including arrays, linked lists, stacks, queues, trees, and graphs. In this post, we will learn about the Singly Linked List data structure.
What is a Singly Linked List?
A singly linked list is a linear data structure in which all data is stored as a node, and the next node is connected by the memory address of the next node. Unline arrays, which have contiguous memory locations, linked lists use dynamic memory allocation. It allows efficient insertion and deletion operations.
Linked List Components:
- Head: It points to the first node of the list.
- Nodes: Each node contains two parts: the data part, which stores the actual value, and the pointer part, which points to the next node in the linked list.
POSTGRADUATE PROGRAM IN
Multi Cloud Architecture & DevOps
Master cloud architecture, DevOps practices, and automation to build scalable, resilient systems.
Syntax of Singly Linked List
struct node{
int data;
struct node* next;
};
Why Do We Need a Linked List?
A linked list has several advantages over other data structures, which is why we need one.
- A linked list is a linear data structure that stores the data dynamically. It means a link can increase its size when more data is entered into the linked list.
- Linked list data segments are represented by nodes, which are connected by links or pointers.
- The final node has null in its second field to avoid pointing to any node.
Operations on Singly Linked List
Singly Linked List supports various operations such as insertion, deletion, traversal, and searching. Let’s explore each operation in detail.
Insertion
Insertion can be performed in various ways in Linked List. There are the following ways.
- Insertion at the start: This operation adds the node at the beginning of the linked list. Let’s see how we can do this.
- Create a new node with the given data.
- Set the new node’s pointer to the current head of the list.
- Update the head pointer to point to the new node.
Program
void insert_at_the_first()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc(sizeof(struct node *));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value\n");
scanf("%d",&item);
ptr->data = item;
ptr->next = head;
head = ptr;
printf("\nNode inserted");
}
}
- Insertion at the specific Point: This operation inserts the node at the specific node of the linked list. Let’s see how we can do this.
- Traverse the list until the desired position does not come.
- Create a node with the given data.
- Adjust the pointer to enter the new node at the specified position.
Program
void insert_at_the_sepecific_point()
{
int i,loc,item;
struct node *ptr, *temp;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter element value");
scanf("%d",&item);
ptr->data = item;
printf("\nEnter the location after which you want to insert ");
scanf("\n%d",&loc);
temp=head;
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\ncan't insert\n");
return;
}
}
ptr ->next = temp ->next;
temp ->next = ptr;
printf("\nNode inserted");
}
}
- Insert at the End: This operation adds the node at the end of the linked list. Let’s see how we can do this
- Traverse the list until you reach the endpoint of the list
- Insert the node link to the last node’s next point.
Program
void insert_At_End()
{
struct node *ptr,*temp;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
ptr -> next = NULL;
head = ptr;
printf("\nNode inserted");
}
else
{
temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
printf("\nNode inserted");
}
}
}
Deletion
Singly linked list deletion is the same as insertion. There are the following ways.
- Deletion at the start: The first node of a single list is very you have to point to the next node in the linked list.
- The Head Node must point to the second node in the list.
Program
void delete_at_start() {
struct node *ptr;
if(head == NULL)
{
printf("\nList is empty\n");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\nNode deleted from the beginning...\n");
}
}
- Deletion at the specific Point: The following operations delete the node at the specific point. Let’s see “how we can do this”.
- Reach the desired node that you want to delete.
- Make the current node point to the next or next node.
Program
void delete_at_specific_node()
{
struct node *ptr,*ptr1;
int loc,i;
printf("\n Enter the location of the node which you want to delete\n");
scanf("%d",&loc);
ptr=head;
for(i=0;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;
if(ptr == NULL)
{
printf("\nCan't delete");
return;
}
}
ptr1 ->next = ptr ->next;
free(ptr);
printf("\nDeleted node %d ",loc+1);
}
Deletion at the End: The deletion of the last node is performed like this.
- Iterate the list until you reach the second last node of the singly linked list.
- Make the second last node null.
Program
void last_node()
{
struct node *ptr,*ptr1;
if(head == NULL)
{
printf("\nlist is empty");
}
else if(head -> next == NULL)
{
head = NULL;
free(head);
printf("\nOnly node of the list deleted ...\n");
}
else
{
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\nDeleted Node from the last ...\n");
}
}
Display
Displaying a list is the most important operation in a linked list. In arrays, we can access the arrays directly However, we cannot do this in Linked. We have to visit every node to get the desired result. The following program demonstrates the traversing of the linked list.
Program
void display()
{
struct node *ptr;
ptr = head;
if(ptr == NULL)
{
printf("Nothing to print");
}
else
{
printf("\nprinting values . . . . .\n");
while (ptr!=NULL)
{
printf("\n%d",ptr->data);
ptr = ptr -> next;
}
}
Search
We can also search the element in the singly linked list by performing the search operations. We need to traverse the linked list. At each node, we have to perform a lookup to determine if the target has been found. If the target has been found, then print the target otherwise, print the item that is not found.
Program
void search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("Item not found\n");
}
}
82.9%
of professionals don't believe their degree can help them get ahead at work.
Applications of Linked List
There are many use cases of Linked List data structure. Here, I am discussing some common use cases of Linked Lists.
- Implementation of stacks and queues by using the Linked list data structure.
- Dynamic memory allocation using the Linked list.
- Manipulation of polynomials in Maths by storing the constants in the node of the linked list.
- Working with sparse matrices
- In the browser, for the next page and previous page use the linked list.
Linked List vs Arrays
The following table differentiates the Arrays and Linked List:
| Features | Linkedin Lists | Arrays |
| Memory Allocations | Dynamic Memory allocated | Contiguous memory allocations |
| Size Flexibility | Flexible, can grow or shrink dynamically | Fixed-size, allocated once |
| Memory overhead | Additional memory for pointers | Fixed memory allocations |
| Implementation | Linked list implementation using nodes | Implemented as a continuous block of memory |
| Insertion and Deletion | Efficient, especially at the beginning/ end | It can be expensive, especially in the middle of the array |
Advantages of Linked List
- Dynamic Data Structure: A linked list is a dynamic data structure. This means it can grow and shrink at runtime by allocating or deallocating memory. So, we don’t need to give the size of the linked list while writing a program.
- No memory wastage: In the Linked list, no memory of wastage because It can increase and decrease the size. So, there is no need to define and pre-allocate the memory.
-
- Insertion and Deletion operations: In the linked list, insertion and deletion operations are very easy. Because we don’t need to shift the elements after the insertion or deletion.
- Scalability: In the linked list, add or remove elements at any position.
Disadvantages of Linked List
-
- Random Access: Linked lists do not provide random access to elements like arrays. In the linked list, we have to traverse the whole link to delete or access the specific elements in the linked list.
- Extra Memory Usage: The linked list requires extra memory compared to arrays. Each element in the linked list must reference another linked list element node, which takes up additional memory space.
- Complexity: Implementing a linked list is more complex than arrays. It requires a pointer or reference link for the node. This complexity can lead to more bugs and errors in linked list programs.
Conclusion
In the above tutorial, we learned about the singly linked list and saw its implementation in the C programming language. A singly linked list provides dynamic memory allocation while running the program. Because of this data structure’s simplicity and ability to handle dynamic data, it is a versatile choice for various applications. Overall, the singly list remains a powerful data structure in computer science.
Can a linked list contain duplicate elements?
Can I implement a linked list using an array?
Is a linked list better than an array data structure?
What are the rules for singly linked lists?
Updated on July 23, 2024