परिपत्र लिंक्ड सूची: सी प्रोग्राम उदाहरण के साथ लाभ

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

एक सर्कुलर लिंक्ड लिस्ट, नोड्स का एक क्रम है जो इस तरह से व्यवस्थित किया गया है कि प्रत्येक नोड को अपने आप ही फिर से तैयार किया जा सकता है। यहाँ एक "नोड" एक स्व-रेफ़रेंशियल तत्व है, जो कि आईआई की ऐमीडिएट आसपास के क्षेत्र में एक या दो नोड्स की ओर इशारा करता है।

नीचे 3 नोड्स के साथ एक परिपत्र जुड़ी सूची का चित्रण है।

यहां, आप देख सकते हैं कि प्रत्येक नोड स्वयं के लिए वापस लेने योग्य है। ऊपर दिखाया गया उदाहरण एक गोलाकार रूप से जुड़ी हुई सूची है।

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

इस परिपत्र लिंक्ड सूची ट्यूटोरियल में, आप सीखेंगे:

• एक सर्कुलर लिंक्ड सूची क्या है?
• बुनियादी संचालन
• निवेशन ऑपरेशन
• विलोपन ऑपरेशन
• एक सर्कुलर लिंक्ड सूची की त्रैमासिक
• सर्कुलर लिंक्ड सूची के लाभ
• सर्कुलर लिंक्ड लिस्ट के रूप में सिंगली-लिंक्ड लिस्ट
• सर्कुलर लिंक्ड लिस्ट के आवेदन

बुनियादी संचालन

एक सर्कुलर लिंक्ड सूची में मूल संचालन हैं:

1. प्रविष्टि
2. विचलन और
3. traversal

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

अगले भाग में, आप एक नोड की प्रविष्टि, और एक सर्कुलर सिंगली लिंक्ड लिस्ट में संभव प्रकार के सम्मिलन को समझेंगे।

निवेशन ऑपरेशन

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

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

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

सर्कुलर लिंक्ड लिस्ट की शुरुआत / अंत में डालने के लिए, वह उस स्थिति में है जहाँ पहले-पहले नोड को जोड़ा गया था,

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

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

नीचे (ए) i-iii के चरण दिखाए गए हैं:

(मौजूदा नोड)

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

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

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

अगला, आप नोड के बाद प्रविष्टि की कोशिश करेंगे।

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

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

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

यह नीचे दिखाया गया है:

(हम कहते हैं कि केवल दो नोड हैं। यह एक तुच्छ मामला है)

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

चरण 2) बाईं ओर के नोड को नए नोड से कनेक्ट करें

STEP 3) नए नोड को राइट हैंड साइड नोड से कनेक्ट करें।

विलोपन ऑपरेशन

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

• वर्तमान तत्व को हटाना
• एक तत्व के बाद विलोपन।

शुरुआत / अंत में विचलन:

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

(मौजूदा सेटअप)

चरण 1 ) परिपत्र लिंक निकालें

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

चरण 3) पहले नोड को नि: शुल्क / निपटाएं

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

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

चरण 1) हमें बताएं कि हमें "VALUE1" के साथ नोड को हटाने की आवश्यकता है।

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

चरण 3) वर्तमान नोड को नि: शुल्क या निपटाएं।

एक सर्कुलर लिंक्ड सूची की त्रैमासिक

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

सर्कुलर लिंक्ड सूची के लाभ

परिपत्र लिंक्ड सूची के कुछ लाभ हैं:

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

सर्कुलर लिंक्ड लिस्ट के रूप में सिंगली लिंक्ड लिस्ट

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

#include#includestruct 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 कोड के लिए, मॉलॉक फ़ंक्शन का उपयोग करके एक खाली नोड आवंटित करें।
2. इस नोड के लिए, डेटा को अस्थायी चर पर रखें।
3. असाइन करें और केवल चर को अस्थायी चर से लिंक करें
4. अंतिम तत्व को मुख्य () / आवेदन के संदर्भ में लौटाएं।

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

… 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. यदि केवल एक नोड है, तो ट्रैवस करने की कोई आवश्यकता नहीं है, नोड की सामग्री मुद्रित की जा सकती है, और जबकि लूप निष्पादित नहीं करता है।
3. यदि एक से अधिक नोड हैं, तो अस्थायी अंतिम तत्व तक सभी आइटम प्रिंट करता है।
4. अंतिम तत्व तक पहुंच गया है, लूप समाप्त हो गया है, और फ़ंक्शन मुख्य फ़ंक्शन पर कॉल करता है।

सर्कुलर लिंक्ड लिस्ट के आवेदन

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