डेटा संरचना में, लिंक्ड लिस्ट डेटा एलिमेंट्स का एक रैखिक संग्रह है। लिस्ट का प्रत्येक एलिमेंट या नोड दो आइटम्स से मिलकर बना होता है - डेटा और अगले नोड का रेफरेंस। अंतिम नोड का रेफरेंस नल होता है। लिंक्ड लिस्ट में एंट्री पॉइंट को लिस्ट का हेड कहा जाता है।
सर्कुलर डबली लिंक्ड लिस्ट में, दो क्रमागत एलिमेंट्स पिछले और अगले पॉइंटर द्वारा लिंक या कनेक्टेड होते हैं और अंतिम नोड नेक्स्ट पॉइंटर द्वारा पहले नोड को इंगित करता है और पहला नोड पिछले पॉइंटर द्वारा अंतिम नोड को इंगित करता है।
सॉर्टेड सर्कुलरली डबली लिंक्ड लिस्ट में, नोड डेटा फील्ड्स में सभी डेटा मान सॉर्टेड रहेंगे। नई नोड डालते समय इसका ध्यान रखा जाएगा।
एल्गोरिदम
शुरुआत
एक क्लास circulardoublylist बनाएं जिसमें निम्न फ़ंक्शन हों:
nod *create_node(int) = नोड के लिए डायनामिकली मेमोरी अलॉट करना।
insert_begin() = लिस्ट की शुरुआत में एलिमेंट्स डालने के लिए।
यदि लिस्ट खाली है, तो नोड डालें और नेक्स्ट और प्रीवियस पॉइंटर को NULL सेट करें।
यदि लिस्ट खाली नहीं है, तो डेटा डालें और नेक्स्ट और प्रीवियस पॉइंटर सेट करें और उन्हें अपडेट करें।
insert_end() = लिस्ट के अंत में एलिमेंट्स डालने के लिए।
यदि लिस्ट खाली है तो एक नोड को सर्कुलर डबली लिस्ट के रूप में बनाएं।
अंतिम नोड ढूंढें।
नोड को डायनामिकली बनाएं।
स्टार्ट न्यू नोड का नेक्स्ट होगा।
न्यू नोड को प्रीवियस नोड बनाएं।
अंतिम को न्यू नोड का प्रीवियस बनाएं।
न्यू नोड को पुराने अंतिम का नेक्स्ट बनाएं।
insert_pos() = लिस्ट में निर्दिष्ट स्थिति पर एलिमेंट्स डालने के लिए।
डेटा डालें।
वह स्थिति दर्ज करें जिस पर एलिमेंट डाला जाना है।
यदि लिस्ट खाली है तो नोड को पहले डालें।
यदि लिस्ट खाली नहीं है तो स्थिति वाले नोड और अगले नोड को ढूंढें।
उनके बीच नोड डालें।
delete_pos() = लिस्ट में निर्दिष्ट स्थिति से एलिमेंट्स डिलीट करने के लिए।
यदि लिस्ट खाली है तो रिटर्न करें।
वह स्थिति दर्ज करें जिससे नोड डिलीट करना है।
यदि लिस्ट में एक नोड है तो उसे डिलीट करें और नेक्स्ट और प्रीव पॉइंटर्स अपडेट करें।
यदि लिस्ट में एक से अधिक नोड्स हैं तो उस विशेष स्थिति पर नोड डिलीट करें और नेक्स्ट और प्रीव पॉइंटर अपडेट करें।
sort() = लिस्ट में एलिमेंट्स को सॉर्ट करने के लिए।
यदि लिस्ट खाली है तो रिटर्न करें।
लिस्ट में एलिमेंट्स को सॉर्ट करें।
display() = लिस्ट प्रदर्शित करने के लिए।
reverse() = लिस्ट को रिवर्स करने के लिए।
समाप्ति
उदाहरण कोड
#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; struct nod { int info; struct nod *n; struct nod *p; }*start, *last; int count = 0; class circulardoublylist { public: nod *create_node(int); void insert_begin(); void insert_end(); void insert_pos(); void delete_pos(); void sort(); void display(); void reverse(); circulardoublylist() { start = NULL; last = NULL; } }; int main() { int c; circulardoublylist cdl; while (1) { cout<<"1.Insert at Beginning"<<endl; cout<<"2.Insert at End"<<endl; cout<<"3.Insert at Position"<<endl; cout<<"4.Delete at Position"<<endl; cout<<"5.sort the list"<<endl; cout<<"6.Display List"<<endl; cout<<"7.Reverse List"<<endl; cout<<"8.Exit"<<endl; cout<<"Enter your choice : "; cin>>c; switch(c) { case 1: cdl.insert_begin(); break; case 2: cdl.insert_end(); break; case 3: cdl.insert_pos(); break; case 4: cdl.delete_pos(); break; case 5: cdl.sort(); break; case 6: cdl.display(); break; case 7: cdl.reverse(); break; case 8: exit(1); default: cout<<"Wrong choice"<<endl; } } return 0; } nod* circulardoublylist::create_node(int v) { count++; struct nod *t; t = new(struct nod); t->info = v; t->n = NULL; t->p = NULL; return t; } void circulardoublylist::insert_begin() { int v; cout<<endl<<"Enter the element to be inserted: "; cin>>v; struct nod *t; t = create_node(v); if (start == last && start == NULL) { cout<<"Element inserted in empty list"<<endl; start = last = t; start->n = last->n = NULL; start->p = last->p = NULL; } else { t->n = start; start->p = t; start = t; start->p = last; last->n = start; cout<<"Element inserted"<<endl; } } void circulardoublylist::insert_end() { int v; cout<<endl<<"Enter the element to be inserted: "; cin>>v; struct nod *t; t = create_node(v); if (start == last && start == NULL) { cout<<"Element inserted in empty list"<<endl; start = last = t; start->n= last->n = NULL; start->p = last->p= NULL; } else { last->n= t; t->p= last; last = t; start->p = last; last->n= start; } } void circulardoublylist::insert_pos() { int v, pos, i; cout<<endl<<"Enter the element to be inserted: "; cin>>v; cout<<endl<<"Enter the position of element inserted: "; cin>>pos; struct nod *t, *s, *ptr; t = create_node(v); if (start == last && start == NULL) { if (pos == 1) { start = last = t; start->n = last->n = NULL; start->p = last->p = NULL; } else { cout<<"Position out of range"<<endl; count--; return; } } else { if (count < pos) { cout<<"Position out of range"<<endl; count--; return; } s = start; for (i = 1;i <= count;i++) { ptr = s; s = s->n; if (i == pos - 1) { ptr->n = t; t->p= ptr; t->n= s; s->p = t; cout<<"Element inserted"<<endl; break; } } } } void circulardoublylist::delete_pos() { int pos, i; nod *ptr, *s; if (start == last && start == NULL) { cout<<"List is empty, nothing to delete"<<endl; return; } cout<<endl<<"Enter the position of element to be deleted: "; cin>>pos; if (count < pos) { cout<<"Position out of range"<<endl; return; } s = start; if(pos == 1) { count--; last->n = s->n; s->n->p = last; start = s->n; free(s); cout<<"Element Deleted"<<endl; return; } for (i = 0;i < pos - 1;i++ ) { s = s->n; ptr = s->p; } ptr->n = s->n; s->n->p = ptr; if (pos == count) { last = ptr; } count--; free(s); cout<<"Element Deleted"<<endl; } void circulardoublylist::sort() { struct nod *t, *s; int v, i; if (start == last && start == NULL) { cout<<"The List is empty, nothing to sort"<<endl; return; } s = start; for (i = 0;i < count;i++) { t= s->n; while (t != start) { if (s->info > t->info) { v = s->info; s->info = t->info; t->info = v; } t = t->n; } s = s->n; } cout<<"List sorted"<<endl; } void circulardoublylist::display() { int i; struct nod *s; if (start == last && start == NULL) { cout<<"The List is empty, nothing to display"<<endl; return; } s = start; for (i = 0;i < count-1;i++) { cout<<s->info<<"<->"; s = s->n; } cout<<s->info<<endl; } void circulardoublylist::reverse() { if (start == last && start == NULL) { cout<<"The List is empty, nothing to reverse"<<endl; return; } struct nod *p1, *p2; p1 = start; p2 = p1->n; p1->n = NULL; p1->p= p2; while (p2 != start) { p2->p = p2->n; p2->n = p1; p1 = p2; p2 = p2->p; } last = start; start = p1; cout<<"List Reversed"<<endl; }
आउटपुट
1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 1 Enter the element to be inserted: 7 Element inserted in empty list 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 1 Enter the element to be inserted: 6 Element inserted 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 2 Enter the element to be inserted: 4 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 2 Enter the element to be inserted: 5 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 6 6<->7<->4<->5 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 5 List sorted 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 4 Enter the position of element to be deleted: 3 Element Deleted 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 3 Enter the element to be inserted: 5 Enter the position of element inserted: 2 Element inserted 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 7 6<->5<->7<->4 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 8 List Reversed 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 6 7<->5<->4 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 8
