Data Structure: Linked List : Part 7

একটি নতুন node কে Circular 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
tail←q
head↑.LINK←q

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

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

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

শর্ত-৩ linked list এর x মান বিশিষ্ট node টি খুঁজে বের করতে হবে (LOC point করে থাকবে)। যদি node টি tail node হলে,

q↑.LINK←head
LOC↑.LINK←q
tail←q

Algorithm

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, tail←q, head↑.LINK←q and exit.
3. LOC←head
4. Repeat step 5 while LOC↑.LINK≠head and LOC↑.INFO≠x
5.                  LOC←LOC↑.LINK
6. q↑.LINK←LOC↑.LINK and LOC↑.LINK←q
7. if LOC=tail then: tail←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

#include<stdio.h> #include<stdlib.h> struct node{ int INFO; struct node *LINK; }; int main(){ struct node *q=NULL,*p=NULL,*head=NULL,*tail=NULL,*LOC=NULL; int i,n=5,x; 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; } p->LINK=head; tail=p; /*INSERTION (Successor)*/ printf("Insert the value of target node:"); scanf("%d",&x); q = (struct node *)malloc(sizeof(struct node)); q->LINK = NULL; q->INFO = 10; if(head==NULL){ head=q; tail=q; head->LINK=q; } else{ LOC=head; while(LOC->LINK!=head && LOC->INFO!=x){ LOC=LOC->LINK; } q->LINK=LOC->LINK; LOC->LINK=q; if (LOC==tail){ tail=q; } } /*Traverse the CHLL*/ p=head; do{ printf("%d ",p->INFO); p=p->LINK; }while(p!=head); return 0; }