Deletion in singly linked list after the specified node

by
  • Reach the node after which the node should be deleted, by skipping the desired number of nodes, to delete the node, which is present after the specified node. It is necessary to keep track of both the nodes, one which is to be deleted and the one which is present before that node. To serve this purpose, we can use the below statements, that involves two pointers, ptr and ptr1. 
    ptr=head;  
for(i=0;i<loc;i++)  
{  
  ptr1 = ptr;       
  ptr = ptr->next;  
 
  if(ptr == NULL)  
   {  
    printf("\nThere are less than %d elements in the list..",loc);  
    return;  
   }  
}
  • The next step is to make a few pointer adjustments. We will use the below statements, to make the next of ptr1 (points to the specified node) point to the next of ptr (the node which is to be deleted). 
    ptr1 ->next = ptr ->next;  
free(ptr);

Algorithm:

  • STEP 1:IF HEAD = NULL
    WRITE UNDERFLOW
    GOTO STEP 10
    END OF IF
  • STEP 2: SET TEMP = HEAD
  • STEP 3: SET I = 0
  • STEP 4: REPEAT STEP 5 TO 8 UNTIL I
  • STEP 5: TEMP1 = TEMP
  • STEP 6: TEMP = TEMP → NEXT
  • STEP 7:IF TEMP = NULL
    WRITE “DESIRED NODE NOT PRESENT”
    GOTO STEP 12
    END OF IF
  • STEP 8:I = I+1
    END OF LOOP
  • STEP 9: TEMP1 → NEXT = TEMP → NEXT
  • STEP 10: FREE TEMP
  • STEP 11: EXIT

Example in C:

#include<stdio.h>  
#include<stdlib.h>  
 
struct node   
{  
    int data;  
    struct node *next;   
};  
 
struct node *head;  
 
void insertAtLast ();  
void deleteAtRandom();  
void show();  
void main ()  
{  
    int choice =0;  
    while(choice != 9)   
    {  
 
        printf("\n1.Insert Node\n2.Delete node after specified location\n3.Show\n4.Exit\n");  
        printf("\nEnter your choice:\n");         
        scanf("\n%d",&choice);  
        switch(choice)  
        {  
            case 1:  
            insertAtLast();         
            break;   
            case 2:  
            deleteAtRandom();          
            break;   
            case 3:  
            show();        
            break;  
            case 4:  
            exit(0);  
            break;  
            default:  
            printf("Enter a valid choice.");  
        }  
    }  
}  
 
void insertAtLast()  
{  
    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 successfully inserted!!");  
        }  
        else  
        {  
            temp = head;  
            while (temp -> next != NULL)  
            {  
                temp = temp -> next;  
            }  
            temp->next = ptr;  
            ptr->next = NULL;  
            printf("\nNode successfully inserted!!");  
 
        }  
    }  
}  
 
void deleteAtRandom()  
{  
    struct node *ptr,*ptr1;  
    int loc,i;    
    printf("\nEnter the location of the node after which you want to perform deletion: \n");  
    scanf("%d",&loc);  
    ptr=head;  
    for(i=0;i<loc;i++)  
    {  
        ptr1 = ptr;       
        ptr = ptr->next;  
 
        if(ptr == NULL)  
        {  
            printf("\nDeletion not possible!!\n");  
            return;  
        }  
    }  
    ptr1 ->next = ptr ->next;  
    free(ptr);  
    printf("\nDeleted node %d ",loc+1);  
}  
 
void show()  
{  
    struct node *ptr;  
    ptr = head;   
    if(ptr == NULL)  
    {  
        printf("Nothing to print");  
    }  
    else  
    {  
        printf("\nPrinting list . . . . .\n");   
        while (ptr!=NULL)  
        {  
            printf("\n%d",ptr->data);  
            ptr = ptr -> next;  
        }  
    }  
}

Output:

1.Insert Node 
2.Delete node after specified location 
3.Show 
4.Exit 
 
Enter your choice: 
1 
 
Enter value: 
2 
 
Node successfully inserted!! 
1.Insert Node 
2.Delete node after specified location 
3.Show 
4.Exit 
 
Enter your choice: 
1 
 
Enter value: 
4 
 
Node successfully inserted!! 
1.Insert Node 
2.Delete node after specified location 
3.Show 
4.Exit 
 
Enter your choice: 
1 
 
Enter value: 
6 
 
Node successfully inserted!! 
1.Insert Node 
2.Delete node after specified location 
3.Show 
4.Exit 
 
Enter your choice: 
3 
 
Printing list . . . . . 
 
2 
4 
6 
1.Insert Node 
2.Delete node after specified location 
3.Show 
4.Exit 
 
Enter your choice: 
2 
 
Enter the location of the node after which you want to perform deletion: 
1 
 
Deleted node 2 
1.Insert Node 
2.Delete node after specified location 
3.Show 
4.Exit 
 
Enter your choice: 
3 
 
Printing list . . . . . 
 
2 
6 
1.Insert Node 
2.Delete node after specified location 
3.Show 
4.Exit 
 
Enter your choice: 
4