Insert a node into sorted list

A singly linked list is a data structure where each node is linked to the next node. In such a list, if you have to add a new node, it can be done in a simple way such as


    find the last node
    link last node to new node

Which can be done using code such as

 NODEPTR insertnode(NODEPTR head, NODEPTR newnode)  
 {  
    if(head==NULL)  
     {  
      head = newnode;  
     }  
     else  
    {  
      NODEPTR temp = head;  
      while(temp->next !=NULL)//till we have not reached last node  
      {  
        temp = temp->next;  
      }  
     // now temp is our last node. add new node after this  
     temp->next = newnode;  
 }  

But if we have a sorted list and we want to add a new node to this list

• we should traverse to first node temp which is greater than new node
• add the new node to previous node of this
• prev->next = newnode;
• newnode->next = temp;
• To find previous node, each time store current node in prev before moving to next node

We also need to consider one special case, where the newnode is smaller than head.

• If the first node greater than newnode is head
• Add the newnode before head
•  newnode->next = head
• head = newnode

Here is our code

 NODEPTR insert_into_sorted_list(NODEPTR head, NODEPTR newnode)  
 {  
   NODEPTR temp = head;  
   NODEPTR prev = temp;  
   while(temp && temp->n < newnode->n)  
   {   
     prev = temp;  
     temp = temp->next;  
   }  
   //special case. insert before head  
   if(temp==head)  
   {  
     newnode ->next = head;  
     head = newnode;  
     return head;  
   }  
   //temp is bigger node. New node should be inserted before temp  
   //after prev. when we move to next node, we are saving node in prev  
   prev->next = newnode;  
   newnode->next = temp;  
   return head;//does not change head actually in this case  
 }