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.
Get curriculum highlights, career paths, industry insights and accelerate your technology journey.
Download brochure
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.
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 emptyn");
}
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 deleten");
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.
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 Listn");
}
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 foundn");
}
}
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.
FAQs
Can a linked list contain duplicate elements?
Yes, the Linked list data structure contains duplicate elements like any other data structure.
Can I implement a linked list using an array?
Yes, we can implement a linked list using an array data structure. Each element of an array contains the data and the link to the next node's reference link.
Is a linked list better than an array data structure?
A linked list data structure can be more efficient than arrays because it uses dynamic memory allocations. But sometimes, arrays are better than links when you want to access the elements quickly.
What are the rules for singly linked lists?
A singly linked list is composed of the link part and the data part of the node. The link part references another node in the linked list. The last nod contains the Null for termination of the linked list.
Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.
