Operations on Single Linked List

Single Linked List :

Singly linked list is the most common linked list among the others. The singly linked list can be traversed only in one direction. It is a collection of ordered sets of elements. In singly linked list, Each node has a data and a pointer to the next node.

Algorithm

Construction of a single linked list :

For constructing a singly linked list in C we make use of the structure keyword(struct), for creating user-defined data types, which can store various different types of data in the nodes of the singly linked list.

Operations on a single linked list:

Node creation:

Following is how we create a node for a linked list using structure in C:

        struct node   
        {  
            int data;   
            struct node *next;  
        };  
        struct node *head, *ptr;   
        ptr = (struct node *)malloc(sizeof(struct node *));

Insertion:

The insertion into a singly linked list can be performed at different positions. Based on the position of the new node being inserted, the insertion is categorized into the following categories.

Insertion at beginning - It involves inserting any element at the front of the list. We just need to a few link adjustments to make the new node as the head of the list.
Insertion at end of the list - It involves insertion at the last of the linked list. The new node can be inserted as the only node in the list or it can be inserted as the last one. Different logics are implemented in each scenario.
Insertion after specified node - It involves insertion after the specified node of the linked list. We need to skip the desired number of nodes in order to reach the node after which the new node will be inserted.

Deletion and Traversal:

The Deletion of a node from a singly linked list can be performed at different positions. Based on the position of the node being deleted, the operation is categorized into the following categories.

Deletion at beginning - It involves deletion of a node from the beginning of the list. This is the simplest operation among all. It just need a few adjustments in the node pointers.
Deletion at the end of the list - It involves deleting the last node of the list. The list can either be empty or full. Different logic is implemented for the different scenarios.
Deletion after specified node - It involves deleting the node after the specified node in the list. we need to skip the desired number of nodes to reach the node after which the node will be deleted. This requires traversing through the list.
Traversing - In traversing, we simply visit each node of the list at least once in order to perform some specific operation on it, for example, printing data part of each node present in the list.
Searching - In searching, we match each element of the list with the given element. If the element is found on any of the location then location of that element is returned otherwise null is returned.

In the following example we are going to see the above operations on a single linked list using structure in C.

Program using C

//SINGLE LINKED LIST IMPLEMENTATION
#include<stdio.h>
#include<stdlib.h>
struct node
{
    int info;
    struct node*next;
};
struct node*start=NULL,*nw,*curn,*prev;
void insert();
void delet();
void display();
main()
    {
        int ch,item;
        while(1)
        {
            printf("\nMENU\n======\n1.INSERT\n2.DELETE\n3.DISPLAY\n4.EXIT\nEnter your choice: ");
            scanf("%d",&ch);
            switch(ch)
            {
                case 1:
                insert();
                break;
                
                case 2:delet();
                            break;
                
                case 3:display();
                break;
                
                case 4:exit(0);
                default: printf("\n Invalid choice: Please try again...\n");
            }
        }
    }
    void insert()
    {
        int pos,n,i;
        n=0;
        printf("Enter the position: ");
        scanf("%d",&pos);
        curn=start;
        while(curn!=NULL)
        {
            n++;
            curn=curn->next;
        }
        if(pos<1||pos>n+1)
        printf("Invalid position");
        else
        {
            nw=(struct node*)malloc(sizeof(struct node));
            printf("Enter info part: ");
            scanf("%d",&nw->info);
            nw->next=NULL;
            if(pos==1)
            {
                nw->next=start;
                start=nw;
            }
            else 	if(pos==n+1)
            {
                curn=start;
                while(curn->next!=NULL)
                curn=curn->next;
                curn->next=nw;
            }
            else
            {
                i=1;
                curn=start;
                while(i<pos)
                {
                    prev=curn;
                    curn=curn->next;
                    i++;
                }
                nw->next=curn;
                prev->next=nw;
            }
        }
        
    }
    void delet()
    {
        int pos,n=0,i;
        curn=start;
        printf("Enter the position: ");
        scanf("%d",&pos);
        if(curn==NULL)
        {
            printf("Underflow");
        }
        else
        {
            while(curn!=NULL)
            {
            n++;
            curn=curn->next;
            }
          if(pos<1 || pos>n)
              {
                printf("Invalid position");}
          else
          {
              if(pos==1)
              {
                  curn=start;
                  start=start->next;
                  free(curn);
              }
              else if(pos==n)
              {
                  curn=start;
                  while(curn->next!=NULL)
                  {
                      prev=curn;
                      curn=curn->next;
                  }
                  prev->next=NULL;
                  free(curn);
              }
           else
           {
                   i=1;
                curn=start;
                while(i<pos)
                {
                    prev=curn;
                    curn=curn->next;
                    i++;
                }
                prev->next=curn->next;
                free(curn);
           }
        }	
       }
    }
    void display()
    {
        curn=start;
        while(curn!=NULL)
        {
            printf("%d->",curn->info);
            curn=curn->next;
        }	
    }