circular linked list data structure c with illustration
सर्कुलर लिंक्ड लिस्ट का पूरा अवलोकन।
एक सर्कुलर लिंक्ड लिस्ट लिंक्ड लिस्ट की विभिन्नता है। यह एक लिंक की गई सूची है जिसके नोड्स इस तरह से जुड़े हुए हैं कि यह एक सर्कल बनाता है।
सर्कुलर लिंक्ड लिस्ट में, पिछले नोड के अगले पॉइंटर को शून्य करने के लिए सेट नहीं किया गया है, लेकिन इसमें पहले नोड का पता होता है, इस प्रकार एक सर्कल बनता है।
=> स्क्रैच से C ++ जानने के लिए यहाँ जाएँ।
आप क्या सीखेंगे:
सी ++ में परिपत्र लिंक्ड सूची
नीचे दी गई व्यवस्था एक एकल लिंक की गई सूची के लिए है।
एक सर्कुलर लिंक्ड लिस्ट एक सिंगल लिस्टेड लिस्ट या डबल लिंक लिस्ट हो सकती है। दोहरी रूप से गोलाकार लिंक्ड सूची में, पहले नोड का पिछला पॉइंटर अंतिम नोड से जुड़ा होता है जबकि अंतिम नोड का अगला पॉइंटर पहले नोड से जुड़ा होता है।
इसका प्रतिनिधित्व नीचे दिखाया गया है।
घोषणा
हम नीचे दिखाए गए अनुसार किसी अन्य नोड के रूप में एक गोलाकार लिंक्ड सूची में नोड घोषित कर सकते हैं:
struct Node { int data; struct Node *next; }; सर्कुलर लिंक्ड लिस्ट को लागू करने के लिए, हम एक एक्सटर्नल पॉइंटर 'लास्ट' को बनाए रखते हैं जो सर्कुलर लिंक्ड लिस्ट में आखिरी नोड की ओर इशारा करता है। इसलिए अंतिम-> अगली सूची में पहले नोड को इंगित करेगा।
ऐसा करने से हम यह सुनिश्चित करते हैं कि जब हम शुरुआत में या सूची के अंत में एक नया नोड डालें, तो हमें पूरी सूची को पार करने की आवश्यकता नहीं है। ऐसा इसलिए है क्योंकि अंतिम बिंदु के अंतिम बिंदु, जबकि अंतिम-> अगले अंक के पहले नोड के लिए।
यदि हम बाहरी पॉइंटर को पहले नोड की ओर इशारा करते तो यह संभव नहीं होता।
बुनियादी संचालन
परिपत्र से जुड़ी सूची सूची के सम्मिलन, विलोपन और ट्रैवर्सल का समर्थन करती है। हम प्रत्येक ऑपरेशन पर अब विस्तार से चर्चा करेंगे।
प्रविष्टि
हम एक नोड को एक गोलाकार लिंक्ड सूची में पहले नोड (खाली सूची) के रूप में, शुरुआत में, अंत में या अन्य नोड्स के बीच में सम्मिलित कर सकते हैं। नीचे दिए गए चित्रात्मक प्रतिनिधित्व का उपयोग करते हुए हम इनमें से प्रत्येक को सम्मिलित करते हैं।
# 1) एक खाली सूची में डालें
जब परिपत्र सूची में कोई नोड नहीं होते हैं और सूची खाली होती है, तो अंतिम सूचक शून्य होता है, फिर हम अंतिम सूचक को नोड एन को इंगित करके एक नया नोड एन डालते हैं जैसा कि ऊपर दिखाया गया है। N का अगला पॉइंटर नोड N को इंगित करेगा क्योंकि केवल एक नोड है। इस प्रकार एन सूची में पहला और अंतिम नोड बन जाता है।
# 2) सूची की शुरुआत में डालें
जैसा कि उपरोक्त प्रतिनिधित्व में दिखाया गया है, जब हम सूची की शुरुआत में एक नोड जोड़ते हैं, तो पिछले नोड का अगला पॉइंटर नए नोड एन को इंगित करता है जिससे यह एक पहला नोड बनता है।
एन-> अगला = आखिरी-> अगला
अंतिम-> अगला = एन
# 3) सूची के अंत में सम्मिलित करें
सूची के अंत में एक नया नोड सम्मिलित करने के लिए, हम इन चरणों का पालन करते हैं:
बाइनरी ट्री कार्यान्वयन c ++
एन-> अगला = अंतिम -> अगला;
अंतिम -> अगला = एन
अंतिम = एन
# 4) सूची के बीच में डालें
मान लें कि हमें N3 और N4 के बीच एक नया नोड एन सम्मिलित करने की आवश्यकता है, हमें पहले सूची को ट्रेस करना होगा और नोड का पता लगाना होगा जिसके बाद नया नोड डाला जाना है, इस स्थिति में, इसका N3।
नोड स्थित होने के बाद, हम निम्न चरणों का पालन करते हैं।
एन -> अगला = एन 3 -> अगला;
एन 3 -> अगला = एन
यह N3 के बाद एक नया नोड N सम्मिलित करता है।
विलोपन
सर्कुलर लिंक्ड लिस्ट को डिलीट करने के ऑपरेशन में उस नोड का पता लगाना शामिल है जिसे डिलीट करना है और फिर उसकी मेमोरी को फ्रीज करना है।
इसके लिए हम दो अतिरिक्त बिंदुओं को बनाए रखते हैं और प्रबल होते हैं और फिर नोड का पता लगाने के लिए सूची को आगे बढ़ाते हैं। हटाए गए नोड को पहले नोड, अंतिम नोड या बीच में नोड हो सकता है। स्थान के आधार पर हमने वक्र और प्रचलित बिंदुओं को सेट किया और फिर वक्र नोड को हटा दिया।
हटाए गए ऑपरेशन का एक सचित्र प्रतिनिधित्व नीचे दिखाया गया है।
traversal
ट्रैवर्सल प्रत्येक और प्रत्येक नोड पर जाने की एक तकनीक है। रैखिक लिंक्ड लिस्ट में जैसे कि सिंगलली लिस्टेड लिस्ट और दोगुनी लिंक्ड लिस्ट में, ट्रवलर्स आसान है क्योंकि हम प्रत्येक नोड पर जाते हैं और जब NULL का सामना होता है तो रुक जाते हैं।
हालांकि, एक गोलाकार लिंक्ड सूची में यह संभव नहीं है। एक गोलाकार लिंक्ड सूची में, हम पिछले नोड के अगले भाग से शुरू करते हैं जो कि पहले नोड है और प्रत्येक नोड को पार करता है। जब हम एक बार फिर से पहले नोड पर पहुँचते हैं तो हम रुक जाते हैं।
अब हम C ++ और Java का उपयोग करके सर्कुलर लिंक्ड लिस्ट ऑपरेशंस का कार्यान्वयन प्रस्तुत करते हैं। हमने यहां प्रविष्टि, विलोपन और ट्रैवर्सल संचालन को लागू किया है। स्पष्ट समझ के लिए, हमने परिपत्र से जुड़ी सूची का चित्रण किया है
इस प्रकार अंतिम नोड 50 के लिए, हम फिर से नोड 10 संलग्न करते हैं जो कि पहला नोड है, जिससे यह एक गोलाकार लिंक्ड सूची के रूप में इंगित होता है।
#include using namespace std; struct Node { int data; struct Node *next; }; //insert a new node in an empty list struct Node *insertInEmpty(struct Node *last, int new_data) { // if last is not null then list is not empty, so return if (last != NULL) return last; // allocate memory for node struct Node *temp = new Node; // Assign the data. temp -> data = new_data; last = temp; // Create the link. last->next = last; return last; } //insert new node at the beginning of the list struct Node *insertAtBegin(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //set new data to node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; return last; } //insert new node at the end of the list struct Node *insertAtEnd(struct Node *last, int new_data) { //if list is empty then add the node by calling insertInEmpty if (last == NULL) return insertInEmpty(last, new_data); //else create a new node struct Node *temp = new Node; //assign data to new node temp -> data = new_data; temp -> next = last -> next; last -> next = temp; last = temp; return last; } //insert a new node in between the nodes struct Node *insertAfter(struct Node *last, int new_data, int after_item) { //return null if list is empty if (last == NULL) return NULL; struct Node *temp, *p; p = last -> next; do { if (p ->data == after_item) { temp = new Node; temp -> data = new_data; temp -> next = p -> next; p -> next = temp; if (p == last) last = temp; return last; } p = p -> next; } while(p != last -> next); cout << 'The node with data '< next; // Point to the first Node in the list. // Traverse the list starting from first node until first node is visited again do { cout < data <'; p = p -> next; } while(p != last->next); if(p == last->next) coutdata==key && (*head)->next==*head) { free(*head); *head=NULL; } Node *last=*head,*d; // If key is the head if((*head)->data==key) { while(last->next!=*head) // Find the last node of the list last=last->next; // point last node to next of head or second node of the list last->next=(*head)->next; free(*head); *head=last->next; } // end of list is reached or node to be deleted not there in the list while(last->next!=*head&&last->next->data!=key) { last=last->next; } // node to be deleted is found, so free the memory and display the list if(last->next->data==key) { d=last->next; last->next=d->next; cout<<'The node with data '< आउटपुट:
बनाई गई परिपत्र से जुड़ी सूची इस प्रकार है:
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
डेटा 10 के साथ नोड सूची से हटा दिया गया है
10 हटाने के बाद परिपत्र से जुड़ी सूची इस प्रकार है:
20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 20
अगला, हम सर्कुलर लिंक्ड सूची संचालन के लिए जावा कार्यान्वयन प्रस्तुत करते हैं।
//Java class to demonstrate circular linked list operations class Main { static class Node { int data; Node next; }; //insert a new node in the empty list static Node insertInEmpty(Node last, int new_data) { // if list is not empty, return if (last != null) return last; Node temp = new Node(); // create a new node temp.data = new_data; // assign data to new node last = temp; last.next = last; // Create the link return last; } //insert a new node at the beginning of the list static Node insertAtBegin(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); //set data for the node temp.data = new_data; temp.next = last.next; last.next = temp; return last; } //insert a new node at the end of the list static Node insertAtEnd(Node last, int new_data) { //if list is null, then return and call funciton to insert node in empty list if (last == null) return insertInEmpty(last, new_data); //create a new node Node temp = new Node(); temp.data = new_data; temp.next = last.next; last.next = temp; last = temp; return last; } //insert node in between the nodes in the list static Node addAfter(Node last, int new_data, int after_item) { //if list is null, return if (last == null) return null; Node temp, p; p = last.next; do { if (p.data == after_item) { temp = new Node(); temp.data = new_data; temp.next = p.next; p.next = temp; if (p == last) last = temp; return last; } p = p.next; { while(p != last.next); System.out.println('The node with data ' + after_item + ' not present in the list.'); return last; } //traverse the circular linked list static void traverse(Node last) { Node p; // If list is empty, return. if (last == null) { System.out.println('Cicular linked List is empty.'); return; } p = last.next; // Point to first Node of the list. // Traversing the list. do{ System.out.print(p.data + '==>'); p = p.next; } while(p != last.next); if(p == last.next) System.out.print(p.data); System.out.print('
'); } //delete a node from the list static Node deleteNode(Node head, int key) { //if list is null, return if (head == null) return null; // Find the required node that is to be deleted Node curr = head, prev = new Node(); while (curr.data != key) { if (curr.next == head) { System.out.printf('
Given node ' + key + ' is not found' + “in the list!'); break; } prev = curr; curr = curr.next; } // Check if node is only node if (curr.next == head) { head = null; return head; } // If more than one node, check if it is first node if (curr == head) { prev = head; while (prev.next != head) prev = prev.next; head = curr.next; prev.next = head; } // check if node is last node else if (curr.next == head) { prev.next = head; } else { prev.next = curr.next; } System.out.println('After deleting ' + key + ' the circular list is:'); traverse(head); return head; } // Main code public static void main(String() args){ Node last = null; last = insertInEmpty(last, 30); last = insertAtBegin(last, 20); last = insertAtBegin(last, 10); last = insertAtEnd(last, 40); last = insertAtEnd(last, 60); last = addAfter(last, 50, 40); System.out.println('Circular linked list created is:'); traverse(last); last = deleteNode(last,40); } } आउटपुट:
बनाई गई परिपत्र से जुड़ी सूची है:
10 ==> 20 ==> 30 ==> 40 ==> 50 ==> 60 ==> 10
40 को हटाने के बाद परिपत्र सूची है:
10 ==> 20 ==> 30 ==> 50 ==> 60 ==> 10
फायदे नुकसान
आइए हम सर्कुलर लिंक्ड लिस्ट के कुछ फायदों और नुकसान पर चर्चा करें।
लाभ:
- हम किसी भी नोड में जा सकते हैं और किसी भी नोड से पार कर सकते हैं। जब हम दोबारा उसी नोड पर जाते हैं तो हमें रुकने की आवश्यकता होती है।
- जैसा कि अंतिम नोड पहले नोड को इंगित करता है, अंतिम नोड से पहले नोड पर जाने के लिए सिर्फ एक कदम होता है।
नुकसान:
- एक गोलाकार लिंक्ड सूची को उलटना बोझिल है।
- चूंकि नोड्स एक सर्कल बनाने के लिए जुड़े हुए हैं, सूची के लिए शुरुआत या अंत के लिए कोई उचित अंकन नहीं है। इसलिए, सूची या लूप नियंत्रण के अंत का पता लगाना मुश्किल है। यदि ध्यान नहीं दिया जाता है, तो एक कार्यान्वयन एक अनंत लूप में समाप्त हो सकता है।
- हम एक भी चरण में पिछले नोड पर वापस नहीं जा सकते। हमें पहले से पूरी सूची का पता लगाना होगा।
सर्कुलर लिंक्ड लिस्ट के आवेदन
- सर्कुलर लिंक्ड लिस्ट का रियल-टाइम एप्लिकेशन एक मल्टी-प्रोग्रामिंग ऑपरेटिंग सिस्टम हो सकता है जिसमें यह कई कार्यक्रमों को शेड्यूल करता है। प्रत्येक कार्यक्रम को निष्पादित करने के लिए एक समर्पित टाइमस्टैम्प दिया जाता है जिसके बाद संसाधनों को दूसरे कार्यक्रम में पारित किया जाता है। यह एक चक्र में लगातार चलता रहता है। यह प्रतिनिधित्व कुशलता से एक परिपत्र लिंक्ड सूची का उपयोग करके प्राप्त किया जा सकता है।
- कई खिलाड़ियों के साथ खेले जाने वाले खेलों को एक गोलाकार लिंक्ड सूची का उपयोग करके भी दिखाया जा सकता है जिसमें प्रत्येक खिलाड़ी एक नोड होता है जिसे खेलने का मौका दिया जाता है।
- हम एक परिपत्र कतार का प्रतिनिधित्व करने के लिए एक परिपत्र लिंक्ड सूची का उपयोग कर सकते हैं। ऐसा करने से, हम कतार के लिए उपयोग किए जाने वाले दो बिंदुओं को आगे और पीछे हटा सकते हैं। इसके बजाय, हम केवल एक पॉइंटर का उपयोग कर सकते हैं।
निष्कर्ष
एक गोलाकार लिंक्ड सूची नोड्स का एक संग्रह है जिसमें नोड्स एक सर्कल बनाने के लिए एक दूसरे से जुड़े हुए हैं। इसका मतलब अंतिम नोड के अगले पॉइंटर को शून्य करने के लिए सेट करने के बजाय यह पहले नोड से जुड़ा हुआ है।
एक सर्कुलर लिंक्ड सूची उन संरचनाओं या गतिविधियों का प्रतिनिधित्व करने में सहायक होती है, जिन्हें एक मल्टीग्रोग्रामिंग वातावरण में कार्यक्रमों की तरह एक विशिष्ट समय अंतराल के बाद बार-बार दोहराया जाना चाहिए। यह एक गोलाकार कतार डिजाइन करने के लिए भी फायदेमंद है।
परिपत्र से जुड़ी सूचियाँ प्रविष्टि, विलोपन और ट्रैवर्सल्स जैसे विभिन्न परिचालनों का समर्थन करती हैं। इस प्रकार हमने इस ट्यूटोरियल के संचालन को विस्तार से देखा है।
डेटा संरचनाओं पर हमारे अगले विषय में, हम स्टैक डेटा संरचना के बारे में जानेंगे।
=> C ++ प्रशिक्षण ट्यूटोरियल के ए-जेड को देखने के लिए यहां देखें।
अनुशंसित पाठ
- सी + + में चित्र संरचना के साथ लिंक्ड सूची डेटा संरचना
- संदेह के साथ सी ++ में संदिग्ध रूप से सूचीबद्ध डेटा संरचना
- कतार डेटा संरचना चित्रण के साथ C ++ में
- चित्रण के साथ C ++ में स्टैक डेटा संरचना
- चित्रण के साथ C ++ में प्राथमिकता कतार डेटा संरचना
- शीर्ष 15 सर्वश्रेष्ठ मुफ्त डेटा खनन उपकरण: सबसे व्यापक सूची
- C ++ में डेटा स्ट्रक्चर्स का परिचय
- 2021 में 15 सर्वश्रेष्ठ ईटीएल उपकरण (पूरी अपडेट सूची)