Data Structure: Linked List- Part 2

INSERT A NEW NODE INTO A HEADER LINKED LIST

Problem-I: Insert a new node between a node which data field is x and its predecessor. If x is not found in header linked list then, the new node insert at the end of the list.

Solution: The first objective is to find the location of the node which data field is x. Let LOC be the pointer to point the target node and LOCP be the pointer that point the predecessor of the target node. If there is not exist any node which data field is x, then we set LOC←NULL and LOCP point to the last node of the linked list . If the target node is header node then we set LOCP←NULL and LOC←head.

CASE-I: Insert Node, if there is no node in header linked list i.e. head←∧

q is a pointer that point to a new node. The instruction to insert new node as header node will be 

head←q

CASE-II: Insert Node as Header node i.e. head↑.INFO = x 

 q is a pointer that point to a new node. The instruction to insert new node as header node will be

q↑.LINK ←LOC 

head←q

CASE-III: Insert Node between the target node and its predecessor i.e. LOC≠∧ 

q is a pointer that point to a new node. The instruction to insert new node as header node will be 

LOCP↑.LINK ←q
q↑.LINK ←LOC

CASE IV: Insert node at the end of the list i.e. LOC=∧ 

q is a pointer that point to a new node. The instruction to insert new node as header node will be 

 LOCP↑.LINK←q

ALGORITHM:

Algorithm-1.1: This algorithm insert a new node between 

the node which data field is x and its predecessor
1. Call New_Node(q)
2. If head = ∧, then: [CASE-I]
            head←q, head↑.INFO←y and exit.
3. If head↑.INFO = x, then: [CASE-II]
            q↑.LINK←head, head←q, and exit.
4. LOC←head↑.LINK and LOCP ← head
5. Repeat step 6 while LOC≠∧ and LOC↑.INFO≠x
6.                      LOCP←LOC and LOC←LOC↑.LINK
7. IF LOC≠∧ then: [CASE-III]
            LOCP↑.LINK←q and q↑.LINK←LOC
        ELSE: [CASE-IV]
             LOCP↑.LINK←q
8. Exit.

FLOW CHART:

Program:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

#include<stdio.h> #include<stdlib.h> struct node{ int INFO; struct node *LINK; }; int main(){ struct node *q=NULL,*LOC=NULL,*LOCP=NULL,*head=NULL,*p=NULL; int i,n=5,x; /*Create A list*/ for(i=1;i<=n;i++){ q = (struct node *)malloc(sizeof(struct node)); q->LINK = NULL; q->INFO = i; if(p==NULL) head = q; else p->LINK = q; p=q; } /*INSERTION*/ printf("Enter a Value of a node:"); scanf("%d",&x); q = (struct node *)malloc(sizeof(struct node)); q->LINK = NULL; q->INFO = 10; /*Manual Value*/ if(head==NULL){ head = q; } else if(head->INFO==x){ q->LINK=head; head=q; } else{ LOC=head->LINK; LOCP=head; while(LOC!=NULL && LOC->INFO!=x){ LOCP=LOC; LOC=LOC->LINK; } if (LOC!=NULL){ LOCP->LINK=q; q->LINK = LOC; } else LOCP->LINK = q; } /*Traverse*/ printf("\n\n"); p=head; while(p!=NULL){ printf("%d ",p->INFO); p=p->LINK; } return 0; }