Deletion in Singly Linked List

 

Introduction

In the previous article we saw how to insert a new node in the linked list at various positions . 
In this article we are going to deeply dive into the topic - delete the node in the linked list.

Deletion

There are three cases of deletion of a  node from singly linked list.
These are
Delete node at : 
 i.  Start of the SLL
 ii.  A given Position  of SLL
 iii . End of the SLL 

  

i.  Delete node at Start of the SLL

To delete the node at the beginning of the linked list , steps are as :

Steps :
 1. Check if the linked list is empty. If empty print the error message. 
 2. If linked list is not empty, create a pointer of type node temp to store the head pointer. temp = head.
 3. Make the next node of head as head by  head = head->head  .
Delete node at the begining in singly linked list
 3. Delete the first node  by delete(temp).

Function for deleting node at beginning :


int deleteStart()
{
    if(head==NULL)
    {
        cout<<"Nothing to delete ! Linked list is Empty";
    }
    else
    {
        node *temp = head;
        int x = temp->data;
        head = head->next;        // Next node of head is made as head
        cout<<"The deleted node is : "<<temp->data<<endl;
        delete(temp);   
    }
}

 

 ii.  Delete node at a given Position  of SLL

To delete the node at a position in a singly linked list , steps include :

 Steps :
 1. Take the position as input from user.

 2. Create a pointer variable of type node named  prev and temp. 
We use prev to store the address of the previous node.
temp is used to store the address of the node which is to be deleted. 

 3. Traverse the list till the position . Now we have two pointers one pointing to the node to be deleted (temp) and another pointing to the previous of it(prev).

4. Make prev->next = temp->next . This creates the link between previous node and a node after deleted node.(Concept will be more clear with diagram below).
Delete node at a position in singly linked list

  Function for deleting node at a position :

int deletePosition(int position)
{
    node *temp=head,*prev=NULL;
    int i=1;
  
        while(temp!=NULL)
        {
            if(position==i)
            {
                break;
            }
            else
            {
                prev=temp;
                temp=temp->next;
                i++;
            }
        }
        prev->next = temp->next;
    cout<<"The  deleted node is : "<<temp->data<<endl;
    delete(temp);
   
}
 

 iii . Delete node at the End of the SLL 

Deleting the node at the end of singly linked list is very simple.
 Steps : 
 1. Traverse upto the last node in linked  list .Store the address of last node in variable temp.
 2. Then just delete the temp . And make the address part of previous node NULL.
Delete node at end of the singly linked list

  Function for deleting node at end :
int deleteEnd()
{
    if(head==NULL)
    {
        cout<<"Nothing to delete ! Linked list is Empty";
    }
    else
    {
        node *temp = head,*prev = NULL;

        while(temp->next!=NULL)              // Traverse up to the last node
        {
            prev = temp;
            temp = temp->next;
        }
        cout<<"The deleted node is : "<<temp->data<<endl;

        prev->next=NULL; 
        delete(temp);
    }

}

  # Code for Deletion of node in linked list
#include<iostream>

using namespace std;


struct node
{
    int data;
    node *next;
};

node *head;

node *createNode(int value);

void insertEnd(int value);

void display();

int deleteStart();

int deleteEnd();

int deletePosition(int position);


    int main()
{
    head =NULL;

    int choise;

    int n,key;

    int location;

    cout<<"\n\t\t Operations on linked list \n";

    do
    {
        cout<<"\n\t\t\t____Menu____\n";

        cout<<"\n\t\t  1. Create a Linked List \n";

        cout<<"\t\t  2. Delete node at Beginning   \n";

        cout<<"\t\t  3. Delete node at End \n";

        cout<<"\t\t  4. Delete node at Position \n";

        cout<<"\t\t  5. Display Linked List \n";

        cout<<"\t\t  6. Exit  \n";

        cout<<"\t  Yours choise :  ";
        cin>>choise;

        switch(choise)
        {
            case 1:
                    cout<<"How many nodes do you want to add ?  ";
                    cin>>n;

                    for(int i=0;i<n;i++)
                    {
                        cout<<"Enter the data :";
                        cin>>key;

                        insertEnd(key);

                    }
            break;
            case 2:

                    deleteStart();

            break;
            case 3:

                    deleteEnd();

            break;
            case 4:

                    if(head==NULL)
                    {
                        cout<<"Nothing to delete ! Linked list is empty ! \n";
                    }
                    else
                    {
                        cout<<"Enter the position : ";
                        cin>>location;

                        deletePosition(location);

                    }
            break;    

            case 5:
                    display();              
            break;

        }
    }while(choise<6);
}

node *createNode(int value)
{
    node *n = new node;

    n->data = value;

    n->next = NULL;

    return n;
}

void insertEnd(int value)
{
    node *newNode = createNode(value);

    node *temp = head;

    if(head==NULL)
    {
        head = newNode;
    }
    else
    {
      
        while(temp->next!=NULL)
        {
            temp = temp->next;
        }
        temp->next= newNode;
    }
  
    cout<<"Node inserted succesfully at End \n"<<endl;

}


int deleteStart()
{
    if (head==NULL)
    {
        cout<<"Nothing to delete ! Linked list is Empty";
    }
    else
    {
        node *temp = head;

        int x = temp->data;

        head = head->next;
 
        cout<<"The deleted node is : "<<temp->data<<endl;

        delete(temp);

    }
}


int deleteEnd()
{
    if (head==NULL)
    {
        cout<<"Nothing to delete ! Linked list is Empty";
    }
    else
    {
        node *temp = head,*prev = NULL;

        while(temp->next!=NULL)
        {
            prev = temp;

            temp = temp->next;
        }
        cout<<"The deleted node is : "<<temp->data<<endl;

        prev->next=NULL;

        delete(temp);
    }

}


int deletePosition(int position)
{
    node *temp=head,*prev=NULL;

    int i=1;
  
    if (position==1)

        deleteStart();
      
    else
      
    {
        while(temp!=NULL)
        {
            if (position==i)
            {
                break;
            }
            else
            {
                prev=temp;

                temp=temp->next;

                i++;
            }
        }
        prev->next = temp->next;

    cout<<"The  deleted node is : "<<temp->data<<endl;

    delete(temp);
    }
}


void display()
{
    int count =0;

    node *temp = head;

    cout<<"Displaying the elements of linked list :\n";

    while(temp!=NULL)
    {
        cout<<"\t"<<temp->data<<"\n";

        temp=temp->next;

        count++;
    }

    cout<<"Node count : "<<count<<endl;

}
Note :  This code is successfully compiled and run under Linux distribution Ubuntu 18.04 LTS environment . 
Download the code here

Output :
 Operations on linked list

            ____Menu____

          1. Create a Linked List
          2. Delete node at Begining  
          3. Delete node at End
          4. Delete node at Position
          5. Display Linked List
          6. Exit 
      Yours choise :  1
How many nodes do you want to add ?  4
Enter the data :10
Node inserted succesfully at End

Enter the data :20
Node inserted succesfully at End

Enter the data :30
Node inserted succesfully at End

Enter the data :40
Node inserted succesfully at End


            ____Menu____

          1. Create a Linked List
          2. Delete node at Begining  
          3. Delete node at End
          4. Delete node at Position
          5. Display Linked List
          6. Exit 
      Yours choise :  5
Displaying the elements of linked list :
    10
    20
    30
    40
Node count : 4

            ____Menu____

          1. Create a Linked List
          2. Delete node at Begining  
          3. Delete node at End
          4. Delete node at Position
          5. Display Linked List
          6. Exit 
      Yours choise :  2
The deleted node is : 10

            ____Menu____

          1. Create a Linked List
          2. Delete node at Begining  
          3. Delete node at End
          4. Delete node at Position
          5. Display Linked List
          6. Exit 
      Yours choise :  5
Displaying the elements of linked list :
    20
    30
    40
Node count : 3

            ____Menu____

          1. Create a Linked List
          2. Delete node at Begining  
          3. Delete node at End
          4. Delete node at Position
          5. Display Linked List
          6. Exit 
      Yours choise :  3
The deleted node is : 40

            ____Menu____

          1. Create a Linked List
          2. Delete node at Begining  
          3. Delete node at End
          4. Delete node at Position
          5. Display Linked List
          6. Exit 
      Yours choise :  5
Displaying the elements of linked list :
    20
    30
Node count : 2

            ____Menu____

          1. Create a Linked List
          2. Delete node at Begining  
          3. Delete node at End
          4. Delete node at Position
          5. Display Linked List
          6. Exit 
      Yours choise :  4
Enter the position : 2
The  deleted node is : 30

            ____Menu____

          1. Create a Linked List
          2. Delete node at Begining  
          3. Delete node at End
          4. Delete node at Position
          5. Display Linked List
          6. Exit 
      Yours choise :  5
Displaying the elements of linked list :
    20
Node count : 1

            ____Menu____

          1. Create a Linked List
          2. Delete node at Begining  
          3. Delete node at End
          4. Delete node at Position
          5. Display Linked List
          6. Exit 
      Yours choise :  2
The deleted node is : 20

            ____Menu____

          1. Create a Linked List
          2. Delete node at Begining  
          3. Delete node at End
          4. Delete node at Position
          5. Display Linked List
          6. Exit 
      Yours choise :  5
Displaying the elements of linked list :
Node count : 0

 

Conclusion : 

 Deletion of nodes at Start , End and at a Position in singly linked list is implemented successfully using C++.