Insert New Node in Ordered Linked List


In order to insert a new node in the ordered linked list we have to follows the below steps:
(1) First we have to check weather free node is available in the Availability Stack or not. If free node is available then we can allocate memory to new node.
(2) After creating new node we have to check weather linked list is empty or not. We have two possibilities:
(A) Linked List is empty (FIRST=NULL). Hence list is empty; the new node is directly inserted in the linked list. Now new node becomes the first node in linked list.
(B) Linked List is not empty (FIRST ≠ NULL). If value of the node to be inserted is less then the value of INFO part of FIRST node then new node is inserted before FIRST node.
(C) Linked List is not empty (FIRST ≠ NULL) and value of the node to be inserted is greater then the value of INFO part of FIRST node. In this case we have to traverse from first node to last node in the list to locate appropriate position in linked list.

     

Algorithm to Insert New Node in Ordered Linked List.


Step 1: If AVAIL=NULL then
             Write “Availability Stack is Empty”
          Else
          NEW_NODE=AVAIL
          AVAIL = AVAIL->LINK
Step 2: If FIRST = NULL then
           NEW_NODE->INFO = X
           NEW_NODE->LINK = NULL
           NEW_NODE=FIRST
           Else If X < FIRST->INFO then
           NEW_NODE->INFO = X
           NEW_NODE->LINK = FIRST
           NEW_NODE=FIRST
           Else
           SAVE = FIRST
           Repeat while X > SAVE->INFO and SAVE->LINK ≠ NULL
           PRED = SAVE
           SAVE = SAVE->LINK
           If SAVE->LINK = NULL and X > SAVE->INFO then
           NEW_NODE->INFO = X
           NEW_NODE->LINK=NULL
           SAVE->LINK = NEW_NODE
           Else
           NEW_NODE->INFO = X
           NEW_NODE->LINK=SAVE
           PRED->LINK = NEW_NODE
Step 3: Exit


Program to Insert New Node in Ordered Linked List.


#include<stdio.h>
#include<conio.h>
#include<alloc.h>
struct node
{
      int info;
      struct node *link;
};
struct node *FIRST;
void createlist()
{
      char ch;
      printf("Enter n for break\n");
      ch=getchar();
      while(ch!='n')
      {
      struct node *NEW_NODE,*SAVE;int x;
      NEW_NODE=(struct node *)malloc(sizeof(struct node));
      printf("Enter Data:");
      scanf("%d",&x);
      NEW_NODE->info=x;
      if(FIRST==NULL)
      {
         NEW_NODE->link=NULL;
         FIRST=NEW_NODE;
      }
      else
      {
         SAVE=FIRST;
         while(SAVE->link!=NULL)
         {
            SAVE=SAVE->link;
         }
         SAVE->link=NEW_NODE;
         NEW_NODE->link=NULL;
      }
      fflush(stdin);
      printf("Enter n for break\n");
      ch=getchar();
   }
}
void insertord()
{
      struct node *NEW_NODE,*SAVE,*PRED;
      int x;
       NEW_NODE=(struct node *)malloc(sizeof(struct node));
      printf("Enter value of node:");
      scanf("%d",&x);
      NEW_NODE->info=x;
      if(FIRST==NULL)
      {
         NEW_NODE->link=NULL;
         FIRST=NEW_NODE;
      }
      else if (x<FIRST->info)
      {
         NEW_NODE->link=FIRST;
         FIRST=NEW_NODE;
      }
      else
      {
          SAVE=FIRST;
          while(x>SAVE->info && SAVE->link!=NULL)
          {
          PRED=SAVE;
          SAVE=SAVE->link;
          }
          if(SAVE->link==NULL && x>SAVE->info)
          {
          SAVE->link=NEW_NODE;
          NEW_NODE->link=NULL;
          }
          else
          {
          PRED->link=NEW_NODE;
          NEW_NODE->link=SAVE;
          }
      }
      printf("%d is succesfully inserted\n",x);
}
void display()
{
      struct node *SAVE;
      if(FIRST==NULL)
      {
         printf("Linked List is empty\n");
         return;
      }
      printf("elements are:\n");
      SAVE=FIRST;
      while(SAVE!=NULL)
      {
         if(SAVE->link==NULL)
         printf("|%d|",SAVE->info);
         else
         printf("|%d|->",SAVE->info);
         SAVE=SAVE->link;
      }
      printf("\n");
      return;
}
void main()
{
      clrscr();
      FIRST=NULL;
      createlist();
      display();
      insertord();
      display();
      getch();
}

Download Projects


Download Programs