Insert New Node Before Given Node in Linked List


In order to insert a new node before a given node in the 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, specified node is not found in the linked list. In this case we can not insert new node before given node.
(B) Linked List is not empty (FIRST ≠ NULL). In this case we have to traverse from first node to last node in the list until given node is found. If node is found in the linked list then we can insert new node before that node otherwise we can not insert new node before given node.

     

Algorithm to Insert New Node Before Given Node


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


Program to Insert New Node Before Given Node


#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 insertbefore(int x)
{
      struct node *NEW_NODE,*SAVE,*PRED;
      int value;
      NEW_NODE=(struct node *)malloc(sizeof(struct node));
      printf("Enter value of node:");
      scanf("%d",&value);
      NEW_NODE->info=value;
      if(FIRST==NULL)
      {
         printf("Specified Node Not Found\n");
      }
      else
      {
          SAVE=FIRST;
          while(x!=SAVE->info && SAVE->link!=NULL)
          {
          PRED=SAVE;
          SAVE=SAVE->link;
          }
          if(SAVE->info==x)
          {
          if(FIRST==SAVE)
          {
              NEW_NODE->link=SAVE;
              FIRST=NEW_NODE;
          }
          else
          {
              NEW_NODE->link=SAVE;
              PRED->link=NEW_NODE;
          }
          }
          else
          {
          printf("Specified Node Not Found");
          }
      }
}
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()
{
      int x;
      clrscr();
      FIRST=NULL;
      createlist();
      display();
      printf("Enter value of Node before which you want to enter new node:");
      scanf("%d",&x);
      insertbefore(x);
      display();
      getch();
}

Download Projects


Download Programs