डेटा संरचना में लिंक लिस्ट डेटा एलिमेंट्स का एक रैखिक संग्रह है। लिस्ट का प्रत्येक एलिमेंट या नोड दो आइटम्स से मिलकर बना होता है - डेटा और अगले नोड का रेफरेंस। अंतिम नोड का रेफरेंस नल होता है। लिंक्ड लिस्ट में एंट्री पॉइंट को लिस्ट का हेड कहा जाता है।
एक डबली लिंक्ड लिस्ट में क्रमिक रूप से लिंक्ड रिकॉर्ड्स का एक सेट होता है जिन्हें नोड्स कहा जाता है। प्रत्येक नोड में तीन फील्ड होते हैं: एक डेटा फील्ड और दो लिंक फील्ड; नोड्स के क्रम में पिछले और अगले नोड के रेफरेंस।
सॉर्टेड डबली लिंक्ड लिस्ट के मामले में, सॉर्टेड डेटा फील्ड मानों के अनुसार लिंक्ड लिस्ट सॉर्टेड रहेगी।
एल्गोरिदम
शुरुआत
फ़ंक्शन createnode() लिस्ट में नोड डालने के लिए:
यह एक न्यू नोड बनाता है और न्यू नोड के डेटा फील्ड में नंबर डालता है।
यह जांचता है कि लिस्ट खाली है या नहीं। यदि लिस्ट खाली है तो नोड को पहले एलिमेंट के रूप में रखें और हेड अपडेट करें।
प्रीव और नेक्स्ट दोनों पॉइंटर्स को NULL से इनिशियलाइज़ किया जाएगा।
यदि लिस्ट खाली नहीं है, तो यह न्यू नोड मौजूदा लिंक्ड लिस्ट में इस तरह डाला जाएगा कि अंततः लिंक्ड लिस्ट सॉर्टेड रहे।
प्रीव और नेक्स्ट पॉइंटर्स को तदनुसार अपडेट किया जाएगा।
समाप्ति
शुरुआत
फ़ंक्शन display_head() हेड से लिस्ट प्रदर्शित करने के लिए:
c=0 इनिशियलाइज़ करें।
पॉइंटर वेरिएबल को हेड नोड एड्रेस से इनिशियलाइज़ करें।
while (c <= i )
नोड इन्फो प्रिंट करें
पॉइंटर वेरिएबल अपडेट करें
c बढ़ाएं।
समाप्ति
शुरुआत
फ़ंक्शन display_tail() टेल से लिस्ट प्रदर्शित करने के लिए:
m=0 इनिशियलाइज़ करें।
पॉइंटर वेरिएबल को टेल नोड एड्रेस से इनिशियलाइज़ करें।
while (m <= i )
नोड इन्फो प्रिंट करें
पॉइंटर वेरिएबल अपडेट करें
m बढ़ाएं।
समाप्ति
उदाहरण कोड
#include<iostream> using namespace std; struct nod { int d; nod *n, *p; } *p = NULL, *head = NULL, *r = NULL, *np = NULL, *tail = NULL; int c = 0; void createnode(int n) { np = new nod; np->d = n; np->n = NULL; np->p = NULL; if (c == 0) { tail = np; head = np; p = head; p->n = head; p->p = head; c++; } else if (c == 1) { p = head; r = p; if (np->d < p->d) { np->n = p; p->p = np; head = np; p->n = np; np->p = p; tail = p; } else if (np->d > p->d) { p->n = np; np->p = p; np->n= head; p->p = np; } c++; } else { p = head; r = p; if (np->d < p->d) { np->n = p; p->p = np; head = np; do { p = p->n; } while (p->n != r); tail = p; p->n = np; np->p = p; } else if (np->d > p->d) { while (p->n != head && np->d > p->d) { r = p; p = p->n; if (p->n == head && (p->d < np->d)) { p->n = np; np->p = p; np->n = head; tail = np; head->p = np; break; } else if (np->d< p->d) { r->n= np; np->p = r; np->n= p; p->p= np; if (p->n != head) { do { p = p->n; } while (p->n != head); } tail = p; break; } } } } } void display_head(int i) { nod *t = head; int c = 0; while (c <= i) { cout<<t->d<<"\t"; t = t->n; c++; } cout<<endl; } void display_tail(int i) { nod *t = tail; int m = 0; while (m <= i) { cout<<t->d<<"\t"; t = t->p; m++; } cout<<endl; } int main() { int i = 0, n, a, ch; cout<<"enter the no of nodes\n"; cin>>n; while (i < n) { cout<<"\nenter value of node\n"; cin>>a; createnode(a); i++; } cout<<"\nsorting Doubly Linked List head first\n"; display_head(n); cout<<"\nsorting Doubly Linked List tail first\n"; display_tail(n); }
आउटपुट
enter the no of nodes 5 enter value of node 7 enter value of node 4 enter value of node 6 enter value of node 2 enter value of node 1 sorting Doubly Linked List head first 1 2 4 6 7 1 sorting Doubly Linked List tail first 7 6 4 2 1 7
