Data Structure: Linked List - Part 8

Circular header linked list হতে একটি node বাদ দেওয়ার পদ্ধতি

সমস্যাঃ একটি node (যার data মান x) header linked list হতে delete (বাদ) দিতে হবে।

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

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

শর্ত-১ linked list এ কোন node না থাকে, অর্থাৎ head←∧, তখন “Underflow/Empty” দেখাবে।

শর্ত-২ যদি head কে delete করতে হলে অর্থাৎ LOC←head or head↑.INFO = x

তাহলে instruction হবে,

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

শর্ত-৩ নির্দিষ্ট node (যার data মান x) খুঁজে পাওয়া যায় তাহলে LOC≠head

LOC pointer টি নির্দিষ্ট node কে point করে থাকবে আর LOCP নির্দিষ্ট node এর পূরবর্তী node কে point করে থাকবে। তাহলে instruction হবে,

LOCP↑.LINK ← LOC↑.LINK

যদি LOC tail node কে point করে থাকে তাহলে

tail←LOCP

শর্ত-৪ যদি x মান বিশিষ্ট কোন node পাওয়া না যায় অর্থাৎ LOC=head, তাহলে “Not Found” দেখাবে।
Algorithm:

This algorithm delete a node from a linked list (head pointer) which data field is x.
1. If head = ∧, then: [CASE-I]
                  Write: Empty and exit.
2. if head↑.INFO = x, then: [CASE-II]
              head← head↑.LINK, tail↑.LINK←head and exit.
3. LOC←head↑.LINK and LOCP ← head
4. Repeat step 5 while LOC≠head and LOC↑.INFO≠x
5.                       LOCP←LOC and LOC←LOC↑.LINK
6. IF LOC≠head then: [CASE-III]
                LOCP↑.LINK←LOC↑.LINK
                If LOC=tail then: tail←LOCP
    ELSE: [CASE-IV]
           Write: Not Found
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 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,*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 (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){ printf("Empty\n"); } else if (head->INFO==x){ head = head->LINK; tail->LINK=head; } else{ LOCP=head;LOC=head->LINK; while(LOC->LINK!=head && LOC->INFO!=x){ LOCP=LOC; LOC=LOC->LINK; } if(LOC!=head){ LOCP->LINK=LOC->LINK; if(LOC==tail) tail=LOCP; } else printf("Not Found\n"); } /*Traverse the CHLL*/ p=head; do{ printf("%d ",p->INFO); p=p->LINK; }while(p!=head); return 0; }