Deletion in singly linked list at the end

by

If a node is deleted from the end of the linked list, there can be any of the two scenarios:

  • Only one node is there in the list and this node is to be deleted.
  • More than one node is there in the list and we need to delete the last node of the list.

Case 1: Only one node is there in the list and this node is to be deleted:

In this case, the only node head of the list will be assigned to null, because the condition head → next = NULL will survive. We can use the below statements for this.

ptr = head  
head = NULL  
free(ptr)

Case 2: More than one node is there in the list and we need to delete the last node of the list:

In this case, we need to traverse the node to reach the last node of the list, because the head → next = NULL condition would fail here. We will thus declare a temporary pointer temp and assign it to the head of the list and keep track of the second last node of the list. For this purpose, we can use the below statements, where we are using two pointers ptr and ptr1 to point to the last node and the second last node of the list, respectively.

ptr = head;   
  while(ptr->next != NULL)  
   {  
     ptr1 = ptr;  
     ptr = ptr ->next;  
   }

Now, we will use the below statements, to make the pointer ptr1 point to the NULL and the last node of the list that is pointed by ptr, free.

ptr1->next = NULL;  
free(ptr);

Algorithm:

  • Step 1:IF HEAD = NULL
    Write UNDERFLOW
    Go to Step 8
    [END OF IF]
  • Step 2: SET PTR = HEAD
  • Step 3: Repeat Steps 4 and 5 while PTR -> NEXT!= NULL
  • Step 4: SET PREPTR = PTR
  • Step 5:SET PTR = PTR -> NEXT
    [END OF LOOP]
  • Step 6: SET PREPTR -> NEXT = NULL
  • Step 7: FREE PTR
  • Step 8: EXIT

Example in C:

#include<stdio.h>  
#include<stdlib.h>  
void createNode(int);  
void deleteNodeAtEnd();  
struct node  
{  
    int data;  
    struct node *next;  
};  
struct node *head;  
void main ()  
{  
    int choice,item;  
    do   
    {  
        printf("\n1.Insert Node\n2.Delete Node\n3.Exit\n4.Enter your choice:\n");  
        scanf("%d",&choice);  
        switch(choice)  
        {  
            case 1:  
            printf("\nEnter the element to insert:\n");  
            scanf("%d",&item);  
            createNode(item);  
            break;   
            case 2:  
            deleteNodeAtEnd();  
            break;   
            case 3:  
            exit(0);  
            break;    
            default:  
            printf("\nPlease enter a valid choice.\n");  
        }  
 
    }while(choice != 3);  
}  
void createNode(int item)  
    {  
        struct node *ptr = (struct node *)malloc(sizeof(struct node *));  
        if(ptr == NULL)  
        {  
            printf("\nOVERFLOW\n");  
        }  
        else  
        {  
            ptr->data = item;  
            ptr->next = head;  
            head = ptr;  
            printf("\nNode inserted successfully!!\n");  
        }  
 
    }  
void deleteNodeAtEnd()  
    {  
        struct node *ptr,*ptr1;  
        if(head == NULL)  
        {  
            printf("\nThe list is empty.");  
        }  
        else if(head -> next == NULL)  
        {  
            head = NULL;  
            free(head);  
            printf("\nOnly node of the list deleted successfully!!");  
        }  
 
        else  
        {  
            ptr = head;   
            while(ptr->next != NULL)  
                {  
                    ptr1 = ptr;  
                    ptr = ptr ->next;  
                }  
                ptr1->next = NULL;  
                free(ptr);  
                printf("\nNode from the end of the list deleted successfully!!");  
            }     
        }

Output:

1.Insert Node
2.Delete Node
3.Exit
4.Enter your choice:
1
 
Enter the element to insert:
2
 
Node inserted successfully!!
 
1.Insert Node
2.Delete Node
3.Exit
4.Enter your choice:
1
 
Enter the element to insert:
4
 
Node inserted successfully!!
 
1.Insert Node
2.Delete Node
3.Exit
4.Enter your choice:
1
 
Enter the element to insert:
6
 
Node inserted successfully!!
 
1.Insert Node
2.Delete Node
3.Exit
4.Enter your choice:
2
 
Node from the end of the list deleted successfully!!
1.Insert Node
2.Delete Node
3.Exit
4.Enter your choice:
2
 
Node from the end of the list deleted successfully!!
1.Insert Node
2.Delete Node
3.Exit
4.Enter your choice:
3