Linked List Program in C - W3 Coding Club

Linked List ( लिंक लिस्ट)

जैसा कि हमने इस  अध्याय के प्रथम भाग यानी Dynamic Memory Allocation  अध्याय  में व्याख्या की गई है कि एरे कुछ परिस्थितियों में डेटा को स्टोर करने के लिए उपयुक्त नहीं है। ऐसी स्थिति में लिक लिस्ट का प्रयोग किया जाता है। लिंक लिस्ट में प्रोग्राम के प्रारंभ में ही लिस्ट का आकार पता होना आवश्यक नहीं होता है। जैसे-जैसे जरूरत होती है, लिंक लिस्ट का आकार बढ़ाया जा सकता है।

list link(लिंक लिस्ट) का प्रयोग structure(स्ट्रक्चर) की सहायता किया जाता है।  structure(स्ट्रक्चर)   में डेटा स्टोर करने के लिए आवश्यक मैम्बर्स के अतिरिक्त एक मैम्बर (पॉइंटर) ऐसा होता है जो लिस्ट के अगले item को point करता है। इसिलिए इसे list link(लिंक लिस्ट)  कहा जाता है।

उदाहरण के लिए यदि हमें कुछ कर्मचारियों के बारे में जानकारी स्टोर करनी है तो इसके लिए निम्न प्रकार    structure(स्ट्रक्चर)   बनाया जा सकता है

struct emp
{
int emp_code;
float salary;
}

उपरोक्त स्ट्रक्चर लिंक लिस्ट के लिए पर्याप्त नहीं है। इसमें emp_code तथा salary के अतिरिक्त एक pointer(पॉइंटर)    और होना चाहिए जो अगले कर्मचारी के डेटा की तरफ पॉइंट करते हुए होगा। चूंकि अगले कर्मचारी का data(डेटा)  भी emp  structure(स्ट्रक्चर)    में ही स्टोर करना है, 

अत: उस pointer(पॉइंटर)   का डेटा टाइप emp ही होगा। निम्न स्ट्रक्चर लिंक लिस्ट के लिए प्रयोग किया जा सकता है

struct emp
{
    int emp_code;
    float salary;
    struct emp *ptr_next
}

ऊपर दिए गए Example में मैमोरी का वह  Address store होगा जहां अगले Employee का data  store होगा। 

लिंक  लिस्ट को निम्न प्रकार दर्शाया जा सकता हैं:-

इस प्रकार प्रोग्राम में जब किसी कर्मचारी का data store(डेटा स्टोर) करना हो उसी समय मैमोरी एलोकेट (आरक्षित) की जा सकती है। चूंकि इस प्रकार प्रत्येक कर्मचारी के लिए अलग-अलग बार मैमोरी आरक्षित की जाएगी तो यह जरूरी नहीं है कि सभी कर्मचारियों का डेटा मैमोरी में एक क्रम  (contiguous) ही हो। इसी कारण से प्रत्येक कर्मचारी का डेटा अगले कर्मचारी के डेटा की ओर इंगित करते हुए सभी कर्मचारियों के डेटा तक हमारी पहुंच बना देता है।

Example:-

 निम्न उदाहरण में link list (लिंक लिस्ट) बनाई गई हैं। 

   

 #include <stdio.h>

    #include <conio.h>

    #include <stdlib.h>

    #define NULL 0

    struct list

    {

        int n;

        struct list *next;

    };

    typedef struct list node;

    void main()

    {

        node *head;

        void create(node * p);

        void print(node * P);

        head = (node *)malloc(sizeof(node));

        create(head);

        printf("\n");

        print(head);

        printf("\n");

    }

    void create(node *list)

    {

        printf("\nEnter a Number");

        printf("(\ntype -999 at end) : ");

        scanf("%d", &list->n);

        if (list->n == -999)

        {

            list->next = NULL;

        }

        else

        {

            list->next = (node *)malloc(sizeof(node));

            create(list->next);

        }

        return;

    }

    void print(node *list)

    {

        if (list->next != NULL)

        {

            printf("\nItem is : %d", list->n);

            print(list->next);

        }

        return;

    }

Output:-

Enter a Number(       
type -999 at end) : 2 

Enter a Number(     
type -999 at end) : 5

Enter a Number(     
type -999 at end) : 6

Enter a Number(     
type -999 at end) : 9

Enter a Number(
type -999 at end) : 55

Enter a Number(
type -999 at end) : -999

Item is : 2
Item is : 5
Item is : 6
Item is : 9
Item is : 55

Explain Example:-

उपरोक्त उदाहरण में फंक्शन main () के अतिरिक्त create() तथा print() फंक्शन भी बनाए गए है। create () फंक्शन दिए गए एड्रेस से प्रारंभ करते हुए लिंक लिस्ट बनाने का कार्य कर रहा है। वहीं print() फंक्शन लिंक लिस्ट के प्रथम नोड को लेते हुए शेष नोड को प्रिंट करने का कार्य कर रहा है।

create () फंक्शन में यह माना गया है कि जब यूजर को अतिरिक्त नोड स्टोर नहीं कराने होंगे तो वह कीबोर्ड से 999 टाइप कर देगा।   if(list->n== 999)   के माध्यम से यही जांच की जा रही है। यदि ऐसा पाया जाता है तो करंट नोड के next पर null स्टोर करवाया जा रहा है। null यह इंगित करता है कि यह अंतिम नोड है। यदि करंट node अंतिम नहीं है तो नए नोड के लिए allocation(एलोकेशन) करवाते हुए उस नए नोड का एड्रेस करंट नोड के next में स्टोर करवाया जा रहा है। इससे current node , new node  की तरफ इंगित करने लगेगा। तत्पश्चात्     create(list->next)     के माध्यम से रिकर्जन का प्रयोग करते हुए नए नोड बनाए जा रहे हैं।

print() फंक्शन भी रिकर्जन पर आधारित है, जो करंट नोड पर null वैल्यू मिलने पर रूक जाएगा अन्यथा प्रत्येक नोड की वैल्यू को प्रिंट करता जाएगा।

लिंक लिस्ट पर किए जाने वाले अन्य ऑपरेशन

 एक बार link list(लिंक लिस्ट)  बना लेने पर उस पर किए जाने वाले कुछ मूलभूत ऑपरेशन निम्न प्रकार हैं:

• बीच में नया आइटम (नोड) जोड़ना।
• मौजूदा आइटम को डिलीट करना।

इन्हें बारी-बारी से समझते हैं:

बीच में नया आइटम (नोड) जोड़ना:-

किसी मौजूदा लिंक लिस्ट में बीच में नया नोड जोड़ने के लिए हमें नए नोड के लिए memory Allocate(मैमोरी एलोकेट) करवाते हुए उसमें नई  Value store(वैल्यूज स्टोर)  करवानी होती है। तत्पश्चात् उस new node(नए नोड) को बीच में insert(इंसर्ट) करना होता है। इसे निम्न चित्र से समझते हैं:-

(A)  New node insert करने से पूर्व की स्थिति 👇👇

(B) New node insert करने से बाद किन्तु pointer में बदलाव से पूर्व की स्थिति 👇👇

(C) New node insert करने से बाद तथा pointer में बदलाव से  बाद की  स्थिति 👇👇

Node  को  Delete करना:-

इसी प्रकार किसी मौजूदा link list(लिंक लिस्ट) से किसी  node को delete करना हो तो निर्दिष्ट नोड को free() फक्शन के माध्यम से मुक्त (डिलीट) किया जा सकता है, किंतु उसे डिलीट कर देने से पूर्व कुछ पॉइंटर्स की वैल्यू निम्न चित्रानुसार परिवर्तित करनी होगी:                                                                 

(A) नोड डिलीट करने से पूर्व की स्थिति👇👇

(B) नोड डिलीट करने तथा पॉइंटर में बदलाव के बाद की स्थिति👇👇

Example:-

निम्न उदाहरण में link list को बनाने मौजूदा लिस्ट में नया नोड जोड़ने तथा मौजूदा node को delete करने का कार्य विभिन्न functions के माध्यम से किया गया है:-                                 

  

  #include <stdio.h>

    #include <conio.h>

    #include <stdlib.h>

    #define NULL 0

    struct list

    {

        int n;

        struct list *next;

    };

    typedef struct list node;

    void main()

    {

        node *insert_node(node *head);

        node *find_node(node *list, int key);

        node *delete_node(node *head);

        node *head;

        void create(node *p);

        void print(node *p);

        head = (node *)malloc(sizeof(node));

        create(head);

        printf("\n");

        print(head);

        printf("\n");

        head = insert_node(head);

        printf("\n");

        print(head);

        printf("\n");

        head = delete_node(head);

        printf("\n");

        print(head);

        printf("\n");

    }

    void create(node *list)

    {

        printf("Enter a Number \n");

        printf("type -999 at end : ");

        scanf("%d", &list->n);

        if (list->n == -999)

        {

            list->next = NULL;

        }

        else

        {

             list->next = (node *)malloc(sizeof(node));

            create(list->next);

        }

        return;

    }

    void print(node *list)

    {

        if (list->next != NULL)

        {

            printf("\nItem is : %d", list->n);

            print(list->next);

        }

        return;

    }

    /* - - -- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

    /* This function will insert new node in liknk list */

    /* - - -- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

    node *insert_node(node *head)

    {

        node *find_node(node * p, int a);

        node *new_node, *nl;

        int new_val, key;

        printf("Type new value : ");

        scanf("%d", &new_val);

        printf("Where to insert new value(key) : ");

        scanf("%d", &key);

        if (head->n == key)

        {

            new_node = (node *) malloc(sizeof(node));

            new_node->n = new_val;

            new_node->next = head;

            head = new_node;

        }

        else

        {

            nl = find_node(head, key);

            if (nl == NULL)

            {

                printf("\nkey value not found \n");

            }

            else

            {

                new_node = (node *)malloc(sizeof(node));

                new_node->n = new_val;

                new_node->next = nl->next;

                nl->next = new_node;

            }

        }

        return head;

    }

    /* - - -- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

     /* This function will find given node from liknk list */

    /* - - -- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/

    node *find_node(node *list, int key)

    {

        if (list->next->n == key)

        {

            return list;

        }

        else

        {

            if (list->next->next == NULL)

            {

                return NULL;

            }

            else

            {

                (list->next, key);

                return NULL;

            }

        }

    }

    node *delete_node(node *head)

    {

        node *find_node(node * p, int a);

        int key;

        node *nl, *p;

        printf("\nType the value for deletion : ");

        scanf("%d", &key);

        if (head->n == key)

        {

            p = head->next;

            free(head);

            head = p;

        }

        else

        {

            nl = find_node(head, key);

            if (nl == NULL)

            {

                printf("\nValue not found\n");

            }

            else

            {

                p = nl->next->next;

                free(nl->next);

                nl->next = p;

            }

        }

        return (head);

    }

Output:-

Enter a Number 
type -999 at end : 45                                                                                                                                                                 
Enter a Number                  
type -999 at end : 50

Enter a Number 
type -999 at end : 55

Enter a Number 
type -999 at end : -999


Item is : 45
Item is : 50
Item is : 55
Type new value : 5
Where to insert new value(key) : 50

Item is : 45
Item is : 5
Item is : 50
Item is : 55

Type the value for deletion : 5

Item is : 45
Item is : 50
Item is : 55

Explain Example:-

insert_node(....):-

function insert_node()  में सर्वप्रथम find_node() फंक्शन को डिफाइन किया गया है। चूंकि जो भी वैल्यू इंसर्ट कराई जाएगी उसके लिए यह बताना आवश्यक होगा कि उसे किस वैल्यू को के बाद में इंसर्ट करवाना है। इसी कारण से हमें उस पहले से मौजूद वैल्यू ढूंढ़ना होगा। फंक्शन में new_val वेरिएबल नई इंसर्ट कराए जाने वाली वैल्यू के लिए प्रयोग किया गया है। वेरिएबल key का प्रयोग उस वैल्यू को इनपुट लेने के लिए किया गया है, जिसके बाद नई वैल्यू इंसर्ट करायी जानी है।

find_node (...):-

फंक्शन find_node() आरग्यूमेंट के रूप में मिली लिंक लिस्ट में key को ढूंढने का कार्य करने के लिए बनाया गया है। यह फंक्शन वह Node return  करता है जिसके बाद नई वैल्यू (नोड) इंसर्ट कराई जानी है। यह फंक्शन रिकर्जन पर आधारित है। सर्वप्रथम   if (list->next->n ==key)       के माध्यम से यह जांच की जा रही है कि क्या इंसर्ट कराए जाने वाली वैल्यू प्रथम नोड के तुरंत बाद ही है। यदि ऐसा है तो return(list) के माध्यम से प्रथम नोड रिटर्न करवाया जा रहा है। यदि ऐसा नहीं है तो रिकर्जन का प्रयोग करते हुए आगे के नोड में key वैल्यू को ढूंढा जा रहा है।

delete_node (...):-

फंक्शन delete_node() भी सर्वप्रथम find_node() फंक्शन को प्रयोग कर रहा है। जो भी डिलीट कराई जानी है वह इस फक्शन के माध्यम से ढूंढी जा रही है। जब delete की जाने वाली वैल्यू मिल जाती है तो उस नोड के veriable next में स्टोर pointer value(पॉइंटर वैल्यू) को वेरिएबल में स्टोर किया जा रहा है, जिसे मैमोरी को free() करने के बाद संबंधित स्थान पर स्टोर करवाया जा रहा है। 

लिंक लिस्ट के प्रकार

हम लिंक लिस्ट का मूल रूप से अध्ययन कर चुके हैं। यही लिंक लिस्ट विभिन्न प्रकार की हो सकती है। इन विभिन्न प्रकारों को निम्न चित्र से स्पष्ट किया जा रहा है:

1.) Linear Link List:-

2.) Circular Link List:-

3.) Doubly (Two-way) Link List:-

4.) Double Circular Link List:-