Request a callback

or Chat with us on

# Introduction to Single Linked List in Data Structure

Internship Assurance
DevOps & Cloud Engineering

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.

• 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.

## 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 valuen");             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 insertn");                   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 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.

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 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");           }       } ```
Internship Assurance
DevOps & Cloud Engineering

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.

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

• 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.

• 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
Yes, the Linked list data structure contains duplicate elements like any other data structure.
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.
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.
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.

Book a free counselling session

Get tailored program recommendations

Explore industry trends and job opportunities

Popular

Data Science

Technology

Finance

Management

Future Tech

Upskill with expert articles
View all
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.

Blogs
Reviews
Events
In the News