Data Structure: Linked List- Part 3

INSERTION A NEW NODE INTO A HEADER LINKED LIST

সমস্যাঃ একটি নতুন node linked list এর একটি node (যার data মান x) ও তার পরবর্তি (successor) node এর মাঝে insert (যুক্ত) করতে হবে। 

সমাধান: প্রথমে আমাকে linked list এর x মান বিশিষ্ট node টি খুঁজে বের করতে হবে। ধরি, LOC pointer টি নির্দিষ্ট node কে point করে আছে। x মান বিশিষ্ট node যদি linked list এ না থাকে তাহলে তা linked list এর শেষে যুক্ত হবে অর্থাৎ LOC pointer শেষ node কে point করে থাকবে। কিছু শর্ত নিয়ে এখন আলোচনা করব। 

শর্ত-১ linked list এ কোন node না থাকে, অর্থাৎ head←∧ 

 q pointer যদি নতুন node কে point করে থাকে তাহলে নতুন node টি head node হবে। তাহলে instruction হবে, 

head←q

শর্ত-২ linked list এর x মান বিশিষ্ট node টি খুঁজে বের করতে হবে (LOC point করে থাকবে) অথবা LOC pointer শেষ node কে point করে থাকবে। 

q pointer যদি নতুন node কে point করে থাকে তাহলে নতুন node টির link এ LOC point করে থাকা node এর link এর মান চলে আসবে, আর LOC point করে থাকা node এর link এ q চলে আসবে। তাহলে instruction হবে 

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

Algorithm-1.1: This algorithm insert a new node between the node which data field is x and its successor 

1. Call New_Node(q)
2. If head = ∧, then: [CASE-I]
               head←q and exit.
3. LOC←head 4. Repeat step 5 while LOC↑.LINK≠∧ and LOC↑.INFO≠x
5.            LOC←LOC↑.LINK
6. q↑.LINK←LOC↑.LINK and LOC↑.LINK←q
7. 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

#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{ LOC=head; while(LOC->LINK!=NULL && LOC->INFO!=x){ LOC=LOC->LINK; } q->LINK=LOC->LINK; LOC->LINK=q; } /*Traverse*/ printf("\n\n"); p=head; while(p!=NULL){ printf("%d ",p->INFO); p=p->LINK; } return 0; }