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

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

एक वृत्ताकार लिंक्ड लिस्ट नोड्स का एक ऐसा क्रम है जिसे इस प्रकार व्यवस्थित किया जाता है कि प्रत्येक नोड को पुनः प्राप्त किया जा सके।tracप्रत्येक "नोड" स्वयं से संबंधित होता है। प्रत्येक "नोड" एक स्व-संदर्भित तत्व होता है जिसमें उसके आस-पास के एक या दो नोड्स के लिए पॉइंटर होते हैं।

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

यहां आप देख सकते हैं कि प्रत्येक नोड पुनःtracस्वयं के लिए सक्षम। ऊपर दिखाया गया उदाहरण एक वृत्ताकार एकल लिंक्ड लिस्ट है।

नोट: सबसे सरल वृत्ताकार लिंक्ड लिस्ट एक सिंगल नोड होती है जिसका नेक्स्ट पॉइंटर tracयह नीचे दिखाए अनुसार वापस अपनी मूल स्थिति में आ जाता है।

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

एक वृत्ताकार लिंक्ड लिस्ट पर तीन मूलभूत संक्रियाएँ इस प्रकार हैं:

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

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

अगले भाग में बताया गया है कि इंसर्शन कैसे काम करता है और एक सर्कुलर सिंगली लिंक्ड लिस्ट में संभव दो प्रकार के इंसर्शन कौन-कौन से हैं।

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

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

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

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

वृत्ताकार लिंक्ड लिस्ट के प्रारंभ या अंत में — अर्थात्, उस स्थान पर जहां पहला नोड जोड़ा गया था — कोई नोड सम्मिलित करने के लिए, नीचे दिए गए चरणों का पालन करें:

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

नोट: वृत्त के आरंभ या अंत को चिह्नित करने वाले पॉइंटर को किसी भी नोड को पुनः असाइन किया जा सकता है। जैसा कि इस लेख में आगे चर्चा की गई है, ट्रैवर्सल अभी भी उसी नोड पर वापस आएगा।

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

(मौजूदा नोड)

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

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

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

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

उदाहरण के लिए, "VALUE0" वाले नोड के बाद "VALUE2" डालें, यह मानते हुए कि प्रारंभिक बिंदु "VALUE0" वाला नोड है।

• पहले और दूसरे नोड के बीच का लिंक तोड़ें, और "VALUE2" वाले नोड को उनके बीच में रखें।
• पहले नोड का नेक्स्ट पॉइंटर नए नोड से जुड़ता है, और नए नोड का नेक्स्ट पॉइंटर उस नोड से जुड़ता है जो पहले दूसरा नोड था।
• बाकी व्यवस्था अपरिवर्तित रहती है। सभी नोड्स पुनःtracस्वयं को सक्षम बनाने में सक्षम।

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

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

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

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

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

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

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

मान लीजिए कि एक 3-नोड वाली वृत्ताकार लिंक्ड लिस्ट है। विलोपन के दो मामले इस प्रकार हैं:

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

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

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

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

चरण 1) गोलाकार लिंक हटाएँ

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

चरण 3) पहले नोड को मुक्त/डी-आवंटित करें

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

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

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

चरण 2) पिछले नोड और वर्तमान नोड के बीच के लिंक को हटा दें, फिर पिछले नोड को सीधे उस नोड से लिंक करें जिसे वर्तमान नोड का अगला पॉइंटर इंगित करता है (VALUE1 के बाद वाला नोड)।

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

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

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

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

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

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

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

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

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

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

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

#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. addToEmpty कोड के लिए, 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. यदि सूची खाली है, तो addToEmpty() फ़ंक्शन को सौंप दें और नियंत्रण वापस कर दें।
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. डू-व्हाइल लूप के प्रत्येक पुनरावृति में, एक पिछला पॉइंटर अंतिम बार ट्रैवर्स किए गए परिणाम को रखता है।
3. तभी अगला ट्रैवर्सल चरण होता है।
4. लक्ष्य डेटा मिलने पर या temp लूप के अंतिम पॉइंटर पर दोबारा पहुँचने पर dowhile लूप समाप्त हो जाता है। नीचे दिया गया कोड ब्लॉक यह तय करता है कि मिले हुए आइटम के साथ क्या करना है।

...
    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. संपर्क पिछले नोड को नए नोड से जोड़ें, और नए नोड के नेक्स्ट पॉइंटर को टेम्प (ट्रैवर्सल वेरिएबल) से लिंक करें।
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. जैसे ही अंतिम तत्व तक पहुंचा जाता है, लूप समाप्त हो जाता है और फ़ंक्शन नियंत्रण को main() पर वापस कर देता है।

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

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

अक्सर पूछे जाने वाले प्रश्न