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();
}