Data Structure: Linked List - Part 4

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

শর্ত-৩ নির্দিষ্ট node (যার data মান x) খুঁজে পাওয়া যাবে অর্থাৎ i.e. LOC≠∧

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

LOCP↑.LINK ← LOC↑.LINK 

শর্ত-৪ যদি x মান বিশিষ্ট কোন node পাওয়া না যায় অর্থাৎ LOC=∧, তাহলে “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 and exit.
3. LOC←head↑.LINK and LOCP ← head
4. Repeat step 5 while LOC≠∧ and LOC↑.INFO≠x
5.                      LOCP←LOC and LOC←LOC↑.LINK
6. If LOC≠∧ then: [CASE-III]
            LOCP↑.LINK←LOC↑.LINK
        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

#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; } /*DELETION*/ printf("Enter a Value of a node:"); scanf("%d",&x); if(head==NULL){ printf("Empty\n"); } else if(head->INFO == x) head=head->LINK; else{ LOC=head->LINK;LOCP=head; while(LOC!=NULL && LOC->INFO!=x){ LOCP=LOC; LOC=LOC->LINK; } if(LOC!=NULL) LOCP->LINK=LOC->LINK; else printf("Not Found\n"); } /*Traverse*/ printf("\n\n"); p=head; while(p!=NULL){ printf("%d ",p->INFO); p=p->LINK; } return 0; }