Program to delete a node from linked list

How do you remove a node from a linked list? If you have to delete a node, first you need to search the node. Then you should find its previous node. Then you should link the previous node to the next node. If node containing 8 has to be deleted, then n1 should be pointing to n2.

Looks quite simple. Isn't it?

But there are at least two special cases you have to consider.

1. Of course, when the node is not found.
2. If the node is first node of the list viz head.

If the node to be deleted is head node, then if you delete, the list would be lost. You should avoid that and make the second node as the head node. So it becomes mandatory that you return the changed head node from the function.

 

Now let us have a look at the code.

#include<stdio.h>  
#include<stdlib.h>
 struct node  
 {  
   int data;  
   struct node *next;   
 };  
 typedef struct node * NODEPTR;   

 NODEPTR create_node(int value)  
 {  
   NODEPTR temp = (NODEPTR) malloc(sizeof(struct node));  
    temp->next = NULL;  
   temp->data= value;  
   return temp;  
 } 
 NODEPTR append_node(NODEPTR head, int n)  
 {  
    NODEPTR temp = head;
    NODEPTR newnode = create_node(n);
    if(temp==NULL)
      return newnode;
    while(temp->next !=NULL)
 temp = temp->next;
    temp->next = newnode;
    return head;  
 } 
NODEPTR find_node(NODEPTR head, int val)
{
     NODEPTR temp = head;
     while(temp!=NULL && temp->data!=val)
     {
             temp = temp->next;
     }
     return temp;
}

/*function to find the previous node for a given node in the list*/
NODEPTR find_previous_node(NODEPTR head, NODEPTR temp)
{
     NODEPTR previousNode = head;
     while(previousNode !=NULL && previousNode ->next !=temp)
     {
             previousNode = previousNode ->next;
     }
     return previousNode ;
}

/*function deletes the node with val as data and returns the head node*/
NODEPTR delete_node(NODEPTR head,int val)
{
    NODEPTR temp = find_node(head,val); 

    if (temp!=NULL)
    {
          /*check if node is first node*/
        if(temp==head)
          {
              head = head->next;
              free(temp);
              return head;
          }
          NODEPTR previousNode = find_previous_node(head,temp);
          if(previousNode!=NULL)
          {
               /*Now point previous node to next node of temp */
              previousNode->next = temp->next; 
           }
           else
           {
                printf("Some serious error. Previous node is not found");   
           }
    }
    else
    {
            printf("Node is not found."); 
    }
   return head;
}

void display_nodes(NODEPTR head)  
 {  
   NODEPTR temp = head;//redundant 
   while (temp!= NULL)  
   {  
     printf("%d====>",temp->data);  
     temp = temp->next;  
   }  
   printf("\n");
 } 

int main()
{
   NODEPTR head = NULL;
   int i;
   for(i = 0;i<10;i++)
   {
       int n;
       printf("Enter a number (-1 to exit) :");
       scanf("%d",&n);
       if(n==-1)break;
       head = append_node(head,n);
    }
    printf("The list is :");
    display_nodes(head);
    printf("Enter the node to be deleted :");
    scanf("%d",&i);
    head = delete_node(head,i);
    printf("After deleting the node, the list is ");
    display_nodes(head);
    return 0;
}

Now let us some tricky questions on deletion.

1. What will happen if the list is empty?
2. Can you delete a node, provided you have only pointer to that node, and do not have head node info.?
3. Will the program crash if the list has only one node head, and that is to be deleted?

Answer to the first question is,

1. the current program will work fine. If the list is empty, find_node function returns NULL, and delete will not delete anything.
2.  you take next_node as temp->next, then copy next_node->data to temp->data and then say temp->next = temp->next->next.
3.  The program will not crash because before deleting the only node in the list, we set head to head->next. Now head will be NULL and this NULL will be returned and assigned  to head. For all further operations, list is empty.

If you have any doubts, please leave a comment.