सर्कुलर लिंक्ड लिस्ट: फायदे और नुकसान

सर्कुलर लिंक्ड सूची क्या है?

एक परिपत्र लिंक्ड सूची नोड्स का एक क्रम है जो इस तरह से व्यवस्थित किया जाता है कि प्रत्येक नोड को खुद से वापस लिया जा सके। यहाँ एक "नोड" एक स्व-संदर्भित तत्व है जिसके तत्काल आस-पास के एक या दो नोड्स के लिए पॉइंटर्स हैं।

नीचे 3 नोड्स वाली एक वृत्ताकार लिंक्ड सूची का चित्रण है।

यहाँ, आप देख सकते हैं कि प्रत्येक नोड अपने आप में रिट्रेसेबल है। ऊपर दिखाया गया उदाहरण एक सर्कुलर सिंगल लिंक्ड लिस्ट है।

नोट: सबसे सरल परिपत्र लिंक्ड सूची, एक नोड है जो केवल स्वयं को ही ट्रेस करता है जैसा कि दिखाया गया है

बुनियादी Operaसर्कुलर लिंक्ड सूचियों में

वृत्ताकार लिंक्ड सूची पर मूल परिचालन इस प्रकार हैं:

1. निवेशन
2. हटाना और
3. traversal

• सम्मिलन (इंसर्शन) एक नोड को वृत्ताकार लिंक्ड सूची में निर्दिष्ट स्थान पर रखने की प्रक्रिया है।
• विलोपन लिंक्ड सूची से किसी मौजूदा नोड को हटाने की प्रक्रिया है। नोड को उसके मान की उपस्थिति या उसकी स्थिति से पहचाना जा सकता है।
• वृत्ताकार लिंक्ड सूची का ट्रैवर्सल, संपूर्ण लिंक्ड सूची की सामग्री को प्रदर्शित करने और स्रोत नोड पर वापस लौटने की प्रक्रिया है।

अगले अनुभाग में, आप नोड के सम्मिलन तथा सर्कुलर सिंगल लिंक्ड सूची में सम्भव सम्मिलन के प्रकारों को समझेंगे।

निवेशन Operaउत्पादन

शुरुआत में, आपको एक नोड बनाना होगा जो खुद की ओर इशारा करता हो जैसा कि इस छवि में दिखाया गया है। इस नोड के बिना, सम्मिलन पहला नोड बनाता है।

इसके बाद, दो संभावनाएं हैं:

• सर्कुलर लिंक्ड सूची की वर्तमान स्थिति पर सम्मिलन। यह एक नियमित एकवचन लिंक्ड सूची के अंत की शुरुआत में सम्मिलन के अनुरूप है। एक सर्कुलर लिंक्ड सूची में, शुरुआत और अंत समान होते हैं।
• अनुक्रमित नोड के बाद प्रविष्टि। नोड को उसके तत्व मान के अनुरूप अनुक्रमणिका संख्या द्वारा पहचाना जाना चाहिए।

वृत्ताकार लिंक्ड सूची के आरंभ/अंत में सम्मिलित करने के लिए, अर्थात उस स्थान पर जहां सबसे पहले नोड जोड़ा गया था,

• आपको मौजूदा नोड से मौजूदा सेल्फ-लिंक को तोड़ना होगा
• नये नोड का अगला पॉइंटर मौजूदा नोड से लिंक हो जाएगा।
• अंतिम नोड का अगला पॉइंटर सम्मिलित नोड की ओर संकेत करेगा।

नोट: टोकन मास्टर या सर्कल की शुरुआत/अंत वाला पॉइंटर बदला जा सकता है। यह ट्रैवर्सल पर उसी नोड पर वापस लौटेगा, जिसकी चर्चा आगे की गई है।

(a) i-iii में चरण नीचे दर्शाए गए हैं:

(मौजूदा नोड)

चरण 1) मौजूदा लिंक को तोड़ें

चरण 2) एक फॉरवर्ड लिंक बनाएं (नए नोड से मौजूदा नोड तक)

चरण 3) पहले नोड के लिए एक लूप लिंक बनाएं

इसके बाद, आप नोड के बाद सम्मिलन का प्रयास करेंगे।

उदाहरण के लिए, आइए हम "VALUE2" वाले नोड के बाद "VALUE0" डालें। आइए हम मान लें कि शुरुआती बिंदु "VALUE0" वाला नोड है।

• आपको पहले और दूसरे नोड के बीच की रेखा को तोड़ना होगा और बीच में “VALUE2” वाला नोड रखना होगा।
• पहले नोड का अगला पॉइंटर इस नोड से लिंक होना चाहिए, और इस नोड का अगला पॉइंटर पहले वाले दूसरे नोड से लिंक होना चाहिए।
• बाकी व्यवस्था अपरिवर्तित रहती है। सभी नोड्स को स्वयं तक वापस लाया जा सकता है।

नोट: चूँकि यहाँ चक्रीय व्यवस्था है, इसलिए नोड डालने में किसी भी नोड के लिए समान प्रक्रिया शामिल है। चक्र पूरा करने वाला पॉइंटर किसी भी अन्य नोड की तरह ही चक्र पूरा करता है।

यह नीचे दर्शाया गया है:

(मान लीजिए कि केवल दो नोड हैं। यह एक मामूली मामला है)

चरण 1) जुड़े हुए नोड्स के बीच आंतरिक लिंक को हटाएँ

चरण 2) बायीं ओर के नोड को नये नोड से जोड़ें

चरण 3) नये नोड को दाएँ हाथ की ओर वाले नोड से जोड़ें।

विलोपन Operaउत्पादन

आइए हम 3-नोड सर्कुलर लिंक्ड सूची मान लें। विलोपन के मामले नीचे दिए गए हैं:

• वर्तमान तत्व हटाना
• किसी तत्व के बाद विलोपन.

आरंभ/अंत में विलोपन:

1. अंतिम नोड से प्रथम नोड तक जाएँ।
2. अंत से हटाने के लिए, अंतिम नोड से प्रथम नोड तक केवल एक ही ट्रैवर्सल चरण होना चाहिए।
3. अंतिम नोड और अगले नोड के बीच के लिंक को हटाएँ।
4. अंतिम नोड को पहले नोड के अगले तत्व से लिंक करें।
5. प्रथम नोड को मुक्त करें.

(मौजूदा व्यवस्था)

1 कदम) परिपत्र लिंक हटाएँ

चरण 2) पहले और अगले के बीच का लिंक हटाएँ, अंतिम नोड को पहले के बाद वाले नोड से लिंक करें

चरण 3) प्रथम नोड को मुक्त/अनियंत्रित करें

नोड के बाद विलोपन:

1. तब तक आगे बढ़ें जब तक कि अगला नोड वह नोड न हो जिसे हटाया जाना है।
2. पिछले नोड पर पॉइंटर रखते हुए अगले नोड पर जाएँ।
3. इसके अगले पॉइंटर का उपयोग करके पिछले नोड को वर्तमान नोड के बाद वाले नोड से कनेक्ट करें।
4. वर्तमान (डिलिंक्ड) नोड को मुक्त करें।

चरण 1) मान लीजिए कि हमें “VALUE1” वाले नोड को हटाना है।

चरण 2) पिछले नोड और वर्तमान नोड के बीच लिंक हटाएँ। इसके पिछले नोड को वर्तमान नोड द्वारा इंगित अगले नोड के साथ लिंक करें (VALUE1 के साथ)।

चरण 3) वर्तमान नोड को मुक्त या विकेन्द्रित करें।

सर्कुलर लिंक्ड सूची का ट्रैवर्सल

किसी सर्कुलर लिंक्ड लिस्ट को पार करने के लिए, आखिरी पॉइंटर से शुरू करते हुए, जाँच करें कि क्या आखिरी पॉइंटर खुद NULL है। अगर यह शर्त गलत है, तो जाँचें कि क्या केवल एक ही तत्व है। अन्यथा, एक अस्थायी पॉइंटर का उपयोग करके तब तक पार करें जब तक कि आखिरी पॉइंटर फिर से न पहुँच जाए, या जितनी बार ज़रूरत हो, जैसा कि नीचे GIF में दिखाया गया है।

सर्कुलर लिंक्ड लिस्ट के लाभ

वृत्ताकार लिंक्ड सूचियों के कुछ लाभ इस प्रकार हैं:

1. कोड में NULL असाइनमेंट की कोई आवश्यकता नहीं है। सर्कुलर सूची कभी भी NULL पॉइंटर की ओर इशारा नहीं करती जब तक कि उसे पूरी तरह से डी-एलोकेट न कर दिया जाए।
2. वृत्ताकार लिंक्ड सूचियाँ अंतिम परिचालनों के लिए लाभदायक होती हैं, क्योंकि इनमें आरंभ और अंत एक ही होते हैं। Algorithms जैसे राउंड रॉबिन शेड्यूलिंग उन प्रक्रियाओं को आसानी से समाप्त कर सकता है जो लटकते या शून्य-संदर्भित संकेतकों का सामना किए बिना एक गोलाकार ढंग से पंक्तिबद्ध होती हैं।
3. सर्कुलर लिंक्ड लिस्ट भी सिंगल लिंक्ड लिस्ट के सभी नियमित कार्य करती है। वास्तव में, सर्कुलर लिंक्ड लिस्ट दोगुनी लिंक्ड सूचियाँ नीचे चर्चा की गई विधि किसी तत्व का पता लगाने के लिए पूर्ण लंबाई के ट्रैवर्सल की आवश्यकता को भी समाप्त कर सकती है। वह तत्व अधिकतम केवल शुरुआत के बिल्कुल विपरीत होगा, जो लिंक्ड सूची का केवल आधा हिस्सा पूरा करेगा।

सर्कुलर लिंक्ड लिस्ट के नुकसान

परिपत्र लिंक्ड सूची का उपयोग करने में निम्नलिखित नुकसान हैं:

1. परिपत्र सूचियाँ अन्य की तुलना में जटिल हैं एकल लिंक्ड सूचियाँ.
2. Revएकल या दोहरी सूची की तुलना में वृत्ताकार सूची अधिक जटिल होती है।
3. यदि सावधानी से नहीं संभाला गया तो कोड अनंत लूप में जा सकता है।
4. सूची का अंत और लूप नियंत्रण ढूंढना कठिन है।
5. प्रारंभ में सम्मिलित करते समय, हमें अंतिम नोड को खोजने के लिए पूरी सूची को पार करना होगा। (कार्यान्वयन परिप्रेक्ष्य)

एकल लिंक्ड सूची एक परिपत्र लिंक्ड सूची के रूप में

आपको नीचे दिए गए कोड को पढ़ने और लागू करने का प्रयास करने के लिए प्रोत्साहित किया जाता है। यह परिपत्र लिंक्ड सूचियों से जुड़े पॉइंटर अंकगणित को प्रस्तुत करता है।

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int item;
    struct node *next;
};

struct node* addToEmpty(struct node*,int);
struct node *insertCurrent(struct node *, int);
struct node *insertAfter(struct node *, int, int);
struct node *removeAfter(struct node *, int);
struct node *removeCurrent(struct node *);

void peek(struct node *);

int main()
{
...

कोड का स्पष्टीकरण:

1. कोड की पहली दो पंक्तियाँ आवश्यक हेडर फ़ाइलें हैं।
2. अगला खंड प्रत्येक स्व-संदर्भित नोड की संरचना का वर्णन करता है। इसमें संरचना के समान प्रकार का एक मान और एक पॉइंटर शामिल होता है।
3. प्रत्येक संरचना बार-बार एक ही प्रकार की संरचना वस्तुओं से जुड़ती है।
4. इसके लिए अलग-अलग फ़ंक्शन प्रोटोटाइप हैं:
   1. रिक्त लिंक्ड सूची में तत्व जोड़ना
   2. पर डालें वर्तमान में इंगित एक परिपत्र लिंक्ड सूची की स्थिति.
   3. किसी विशेष के बाद सम्मिलित करना अनुक्रमित लिंक्ड सूची में मान.
   4. किसी विशेष के बाद हटाना/मिटाना अनुक्रमित लिंक्ड सूची में मान.
   5. वृत्ताकार लिंक्ड सूची के वर्तमान इंगित स्थान को हटाना
5. अंतिम फ़ंक्शन लिंक्ड सूची की किसी भी स्थिति पर प्रत्येक तत्व को एक वृत्ताकार यात्रा के माध्यम से प्रिंट करता है।

int main()
{
    struct node *last = NULL;
    last = insertCurrent(last,4);
    last = removeAfter(last, 4);
    peek(last);
    return 0;
}

struct node* addToEmpty(struct node*last, int data)
{
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp->item = data;
    last = temp;
    last->next = last;
    return last;
}
    
struct node *insertCurrent(struct node *last, int data)

कोड का स्पष्टीकरण:

1. addEmpty कोड के लिए, malloc फ़ंक्शन का उपयोग करके एक रिक्त नोड आवंटित करें।
2. इस नोड के लिए, डेटा को अस्थायी चर में रखें।
3. एकमात्र चर को अस्थायी चर से निर्दिष्ट और लिंक करें
4. अंतिम तत्व को main() / अनुप्रयोग संदर्भ में लौटाएं।

struct node *insertCurrent(struct node *last, int data)
{
    if(last == NULL)
    {
       return    addToEmpty(last, data);
    }
    struct node *temp = (struct node *)malloc(sizeof( struct node));
    temp -> item = data;
    temp->next = last->next;
    last->next = temp;
    return last;
}
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
…

कोड का स्पष्टीकरण

1. यदि सम्मिलित करने के लिए कोई तत्व नहीं है, तो आपको खाली सूची में जोड़ना सुनिश्चित करना चाहिए और नियंत्रण वापस करना चाहिए।
2. वर्तमान तत्व के बाद रखने के लिए एक अस्थायी तत्व बनाएँ।
3. दिखाए गए अनुसार पॉइंटर्स को लिंक करें।
4. पिछले फ़ंक्शन की तरह अंतिम पॉइंटर लौटाएँ.

...
struct node *insertAfter(struct node *last, int data, int item)
{
    struct node *temp = last->next, *prev = temp, *newnode =NULL;
    if (last == NULL)
    {
       return addToEmpty(last, item);
    }
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );


    if(temp->item != data)
    {
       printf("Element not found. Please try again");
...

कोड का स्पष्टीकरण:

1. यदि सूची में कोई तत्व नहीं है, तो डेटा को अनदेखा करें, वर्तमान आइटम को सूची में अंतिम आइटम के रूप में जोड़ें और नियंत्रण वापस करें
2. Do-while लूप में प्रत्येक पुनरावृत्ति के लिए सुनिश्चित करें कि एक पिछला पॉइंटर मौजूद है जो अंतिम बार पार किए गए परिणाम को धारण करता है।
3. तभी अगला पारगमन संभव हो सकेगा।
4. यदि डेटा मिल जाता है, या temp अंतिम पॉइंटर तक वापस पहुंच जाता है, तो do-while समाप्त हो जाता है। कोड का अगला भाग तय करता है कि आइटम के साथ क्या किया जाना है।

...
    if(temp->item != data)
    {
       printf("Element not found. Please try again");
       return last;
    }
    else
    {
   	 newnode = (struct node *)malloc(sizeof(struct node));
             newnode->item = item;
             prev->next = newnode;
             newnode->next = temp;
    }
    return last;
}

struct node *removeCurrent(struct node *last)
...

कोड का स्पष्टीकरण:

1. यदि पूरी सूची देख ली गई है, फिर भी आइटम नहीं मिला है, तो "आइटम नहीं मिला" संदेश प्रदर्शित करें और फिर कॉलर को नियंत्रण वापस कर दें।
2. यदि कोई नोड मिल जाए, और/या वह नोड अभी अंतिम नोड नहीं है, तो एक नया नोड बनाएं।
3. संपर्क पिछले नोड को नए नोड से जोड़ें। वर्तमान नोड को temp (ट्रैवर्सल वैरिएबल) से लिंक करें।
4. यह सुनिश्चित करता है कि तत्व को सर्कुलर लिंक्ड सूची में किसी विशेष नोड के बाद रखा गया है। कॉलर पर वापस लौटें।

struct node *removeCurrent(struct node *last)
{
    if(last == NULL)
    {
        printf("Element Not Found");
        return NULL;
    }
    struct node *temp = last->next;
    last->next = temp->next;
    free(temp);
    return last;
}

struct node *removeAfter(struct node *last, int data)

कोड का स्पष्टीकरण

1. केवल अंतिम (वर्तमान) नोड को हटाने के लिए, जाँच करें कि क्या यह सूची खाली है। यदि यह खाली है, तो कोई भी तत्व हटाया नहीं जा सकता।
2. अस्थायी चर केवल एक लिंक आगे बढ़ता है।
3. अंतिम पॉइंटर को पहले के बाद वाले पॉइंटर से लिंक करें.
4. अस्थायी पॉइंटर को मुक्त करें। यह अन-लिंक किए गए अंतिम पॉइंटर को हटा देता है।

struct node *removeAfter(struct node *last,int data)
{
    struct node *temp = NULL,*prev = NULL;
    if (last == NULL)
    {
   	 printf("Linked list empty. Cannot remove any element\n");
   	 return NULL;
    }
    temp = last->next;
    prev = temp;
    do
    {
        prev = temp;
        temp = temp->next;
    } while (temp->next != last && temp->item != data );

    if(temp->item != data)
    {
      printf("Element not found");
...

कोड का स्पष्टीकरण

1. पिछले निष्कासन फ़ंक्शन की तरह, जाँच करें कि कोई तत्व तो नहीं है। यदि यह सत्य है, तो कोई भी तत्व हटाया नहीं जा सकता।
2. संकेत हटाए जाने वाले तत्व का पता लगाने के लिए उन्हें विशिष्ट स्थान दिए जाते हैं।
3. संकेत एक दूसरे के पीछे आगे की ओर हैं। (अस्थायी पीछे पिछला)
4. यह प्रक्रिया तब तक जारी रहती है जब तक कोई तत्व नहीं मिल जाता, या अगला तत्व अंतिम पॉइंटर तक वापस नहीं आ जाता।

    if(temp->item != data)
    {
        printf("Element not found");
        return last;
    }
    else
    {
        prev->next = temp->next;
        free(temp);
    }
    return last;
}

void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
   return;	

कार्यक्रम का स्पष्टीकरण

1. यदि संपूर्ण लिंक्ड सूची को पार करने के बाद तत्व मिलता है, तो एक त्रुटि संदेश प्रदर्शित होता है जिसमें कहा जाता है कि आइटम नहीं मिला।
2. अन्यथा, चरण 3 और 4 में तत्व को अलग कर दिया जाता है और मुक्त कर दिया जाता है।
3. पिछला पॉइंटर हटाए जाने वाले तत्व (अस्थायी) द्वारा "अगला" के रूप में इंगित पते से जुड़ा हुआ है।
4. इसलिए अस्थायी सूचक को हटा दिया जाता है और मुक्त कर दिया जाता है।

...
void peek(struct node * last)
{
    struct node *temp = last;
    if (last == NULL)
    {
         return;    
    }
    if(last -> next == last)
    {
        printf("%d-", temp->item);
    }
    while (temp != last)
    {
       printf("%d-", temp->item);
       temp = temp->next;
    }
}

कोड का स्पष्टीकरण

1. यदि शून्य की आवश्यकता है तो पीक या ट्रैवर्सल संभव नहीं है। उपयोगकर्ता को नोड आवंटित या सम्मिलित करने की आवश्यकता है।
2. यदि केवल एक नोड है, तो ट्रैवर्स करने की कोई आवश्यकता नहीं है, नोड की सामग्री को प्रिंट किया जा सकता है, और while लूप निष्पादित नहीं होता है।
3. यदि एक से अधिक नोड हैं, तो अस्थायी अंतिम तत्व तक सभी आइटम प्रिंट करता है।
4. जैसे ही अंतिम तत्व तक पहुंचा जाता है, लूप समाप्त हो जाता है, और फ़ंक्शन मुख्य फ़ंक्शन को कॉल लौटाता है।

सर्कुलर लिंक्ड लिस्ट के अनुप्रयोग

• सिस्टम प्रक्रियाओं में राउंड-रॉबिन शेड्यूलिंग और उच्च गति ग्राफिक्स में सर्कुलर शेड्यूलिंग का कार्यान्वयन।
• कंप्यूटर नेटवर्क में टोकन रिंग शेड्यूलिंग।
• इसका उपयोग दुकान बोर्ड जैसी प्रदर्शन इकाइयों में किया जाता है, जिनमें डेटा के निरंतर संचरण की आवश्यकता होती है।