Monday, July 9, 2012

deleting a node from linked list!!

Deleting a node in a linked list is little bit complex. There are three three cases we need to handle while doing delete operation.
  • Empty list
  • Deleting node is first node in the list (this is similar to deleting current node in the list)
  • Deleting other than first node
The basic concept we need to understand while doing delete operation in single linked list that, there is no backward traversing in single linked list. We cant access the previous node. So we need to maintain current and next node and need to check the next node info field for matching. Lets see three cases one by one.

Empty List:  If we are trying to do deleting a node in the empty list. This will find out by check the head node NULL or not. If head node is NULL, it is an empty list so just return.
Deleting node is first node: If the deleting node is first node, there will be two cases. One is list contains only one node and another case is list contains more than one node. In first case we need to delete the node and make it that node as NULL, in another case where a list has more than single node, for this we need to follow the idea of deleting the current node in the list. sample code is given below.
head->info = head->next->info;
temp = head->next;
head->next = head->next->next;
free(temp);
Actually, here no node time temp, but to free the deleted memory, we need to use temp.
Deleting other than first node: Deleting a node is not a first node in the list. This is the general case. As mentioned above, need to maintain current and  next pointers. and check for the next pointer info field and find out the deleted node. see the C code snippet below.
while(h->next!=NULL)
 {
     if((h->next->info == info))
     {
             temp = h->next;
             h->next=h->next->next;
             free(temp);
   return;
     }
     h=h->next;
 }


Here is the complete working C code for deleting a node form linked list.

No comments:

Popular Posts