Data Structure: Linked List - Part 6

একটি নতুন node কে Circular header linked list এ সংযুক্ত করার পদ্ধতি 

সমস্যাঃ একটি নতুন node circular linked list এর একটি node (যার data মান x) ও তার পূর্ববর্তী(predecesor) node এর মাঝে insert (যুক্ত) করতে হবে। যদি x মান বিশিষ্ট কোন node পাওয়া না যায় তাহলে নতুন node টি linked list এর শেষে সংযুক্ত করে দিতে হবে।

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

কিছু শর্ততে ভাগ করে এখন Insertion পদ্ধতিটি আলোচনা করব।

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

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

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

শর্ত-২ নতুন node যদি head হিসেবে সংযুক্ত করা লাগে অর্থাৎ LOC←head or head↑.INFO = x

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

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

শর্ত-৩ নির্দিষ্ট node (যার data মান x) ও তার পূর্ববর্তী(predecesor) node এর মাঝে insert (যুক্ত) করতে হলে, অর্থাৎ i.e. LOC≠head

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

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

শর্ত-৪ যদি x মান বিশিষ্ট কোন node পাওয়া না যায় অর্থাৎ LOC=head, তাহলে tail node হিসেবে insert হবে।

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

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

Algorithm:
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↑.LINK←q, tail←q, and exit.
3. if head↑.INFO = x, then: [CASE-II]
             q↑.LINK←head, head←q, tail←q and exit.
4. LOC←head↑.LINK and LOCP ← head
5. Repeat step 6 while LOC≠head and LOC↑.INFO≠x
6.                LOCP←LOC and LOC←LOC↑.LINK
7. IF LOC≠head then: [CASE-III]
          LOCP↑.LINK←q and q↑.LINK←LOC
    ELSE: [CASE-IV]
          tail↑.LINK←q, q↑.LINK←head and 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 58 59 60 61 62 63 64 65 66 67 68

#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,*LOCP=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 (Predecessor)*/ 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 if(head->INFO ==x){ q->LINK=head; head=q; tail->LINK=q; } else{ LOC=head->LINK; LOCP=head; while(LOC!=head && LOC->INFO!=x){ LOCP=LOC; LOC=LOC->LINK; } if (LOC!=head){ LOCP->LINK=q; q->LINK = LOC; } else{ tail->LINK=q; q->LINK=head; tail=q; } } /*Traverse the CHLL*/ p=head; do{ printf("%d ",p->INFO); p=p->LINK; }while(p!=head); return 0; }