सिंगली लिंक्ड लिस्ट: नोड, लिंक और ट्रैवर्सल

ऐरे के स्थान से लिंक के क्रम तक

ऐरे को स्कैन करते समय हम स्थान 0, 1, 2 आदि पर जाते हैं। सिंगली लिंक्ड लिस्ट (singly linked list) का नियम अलग है: हेड (head) से शुरू करें, उस नोड का डेटा पढ़ें और उसके नेक्स्ट लिंक (next link) पर जाएँ। अगला नोड ऐरे के अगले स्थान पर हो, यह ज़रूरी नहीं है। इस पाठ में आप इस क्रम को दर्शाना और समझना, अंतिम लिंक पहचानना तथा खाली लिस्ट को सुरक्षित ढंग से संभालना सीखेंगे।

पूर्वज्ञान: आरंभिक मानों वाले पूर्णांक ऐरे, वैध इंडेक्स, if, while, फ़ंक्शन, लौटाए गए मान और ऐरे पैरामीटर का नियम। पिछले रिकर्शन मॉड्यूल में अलग-अलग कॉल और उनकी वापसी पढ़ी थी; यहाँ ट्रैवर्सल जानबूझकर लूप से किया गया है। रिकर्शन का कॉल स्टैक और लिंक्ड लिस्ट में रखा डेटा अलग बातें हैं। इस लिस्ट पर चलने के लिए रिकर्शन आवश्यक नहीं है।

हम सीमित आकार के नोड-रिकॉर्ड ऐरे में पूर्णांक इंडेक्स को लिंक बनाएँगे। यह ऐरे के भीतर लिंक से जुड़ा निरूपण है; इसका अर्थ यह नहीं कि हर लिंक्ड लिस्ट ऐरे इस्तेमाल करती है। पॉइंटर वाले नोड, malloc/free से डायनैमिक आवंटन, नोड हटाना और खाली स्लॉट दोबारा इस्तेमाल करना, डबली लिंक्ड लिस्ट, ट्री तथा औपचारिक जटिलता-विश्लेषण आगे के विषय हैं। यहाँ मेमोरी का डायनैमिक आवंटन या मुक्त करना नहीं होता।

प्रोग्राम से पहले C का नया सिंटैक्स

struct नाम वाले फ़ील्ड को एक रिकॉर्ड में जोड़ता है। typedef struct { int value; int next; } Node; इस रिकॉर्ड प्रकार को छोटा नाम Node देता है। एक Node में value डेटा फ़ील्ड और next लिंक फ़ील्ड है। डॉट से फ़ील्ड चुनते हैं: nodes[2].next का अर्थ है “इंडेक्स 2 वाले नोड का next फ़ील्ड।” दोनों पूर्णांक होने पर भी उनका काम अलग है।

Node nodes[4] निश्चित आकार के एक ऐरे में चार रिकॉर्ड बनाता है। {10, 1} आरंभिक मानों में घोषणा के क्रम के अनुसार value को 10 और next को 1 देता है। enum { CAP = 4, END = -1 }; दो पूर्णांक स्थिरांक बनाता है। CAP भंडारण क्षमता है; END लिंक का अर्थ है “कोई अगला नोड नहीं।” END को कभी ऐरे का इंडेक्स मानकर नहीं पढ़ते। डेटा का मान -1 होना पूरी तरह वैध है; केवल लिंक या head में -1 अंत-संकेत (sentinel) है।

पैरामीटर const Node nodes[] फ़ंक्शन को उन्हीं रिकॉर्ड को पढ़ने देता है, लेकिन इस पैरामीटर के माध्यम से उनके फ़ील्ड बदलने नहीं देता। पहले के ऐरे पैरामीटर की तरह C इसे पॉइंटर पैरामीटर मानता है; इससे पूरा ऐरे कॉपी नहीं होता और क्षमता अपने-आप पता नहीं चलती। कॉलर को ठीक CAP रिकॉर्ड वाला जीवित, आरंभिक मानों से भरा ऐरे देना होगा। हम पॉइंटर अंकगणित, हीप आवंटन या स्पष्ट पॉइंटर लिंक नहीं इस्तेमाल करते। फिर भी C के इस ऐरे पैरामीटर का आधार पॉइंटर ही है।

ReadResult एक और रिकॉर्ड है जिसमें ok और value हैं। फ़ंक्शन पूरा रिकॉर्ड मान के रूप में लौटा सकता है। ok = 1 का अर्थ है कि value सफलतापूर्वक पढ़ा गया है; ok = 0 का अर्थ है कि पढ़ना सफल नहीं हुआ और कॉलर को value अनदेखा करना चाहिए। इससे 0 या -1 जैसे वैध डेटा को त्रुटि-संकेत मानने की भूल नहीं होती। !x का अर्थ है “x शून्य है”; || तार्किक OR और && तार्किक AND हैं। वे बाएँ से दाएँ शॉर्ट-सर्किट नियम अपनाते हैं। इसलिए अमान्य लिस्ट या खाली head मिलने पर पहले नोड का डेटा नहीं पढ़ा जाता।

निरूपण का अनुबंध

इस छोटे मॉडल में:

• वास्तविक ऐरे में CAP = 4 रिकॉर्ड हैं और सभी को आरंभिक मान दिए गए हैं। used का मान 0 से 4 तक है।
• सक्रिय रिकॉर्ड के इंडेक्स 0 से used - 1 हैं; बाकी स्लॉट लिस्ट के सदस्य नहीं हैं। इन सक्रिय नोड के लिंक इन इंडेक्स को किसी भी क्रम में जोड़ सकते हैं।
• खाली लिस्ट का head = END होता है। अन्यथा head पहले सक्रिय नोड का इंडेक्स है।
• प्रत्येक सक्रिय नोड का next किसी दूसरे सक्रिय नोड का इंडेक्स या END है। head से शुरू करके सभी used सक्रिय नोड पर ठीक एक बार जाना चाहिए और फिर END आना चाहिए।
• वैध निरूपण में चक्र या head से न पहुँच सकने वाला सक्रिय नोड नहीं है। दूसरे कार्यान्वयन में अलग रखे आवंटित रिकॉर्ड हो सकते हैं; इस शिक्षण मॉडल में ऐसे रिकॉर्ड used में नहीं गिने जाते।

क्षमता, सदस्य संख्या, इंडेक्स और डेटा का मान अलग-अलग हैं। तीन सदस्यों की लिस्ट इंडेक्स 2 से शुरू हो सकती है। किसी नोड का डेटा 30 होने का अर्थ इंडेक्स 30 पर लिंक होना नहीं है। किसी अनुपयोगी स्लॉट के फ़ील्ड में संख्याएँ रखी हों, तो केवल इसी कारण वह लिस्ट का सदस्य नहीं बन जाता।

हल सहित ट्रेस: भंडारण का क्रम और लिंक का क्रम

शुरुआत के सक्रिय रिकॉर्ड हैं:

head = 2 और used = 3 होने पर लिंक की शृंखला 2 -> 0 -> 1 -> END है। इसलिए डेटा का क्रम 20, 10, 30 है, 10, 30, 20 नहीं। तीर लिंक फ़ील्ड के मान दर्शाते हैं; उनका अर्थ वर्तमान इंडेक्स में 1 जोड़ना नहीं है।

हम head नहीं बदलते, बल्कि current नाम का अलग चल-सूचक बदलते हैं। current = current + 1 लिखना ऐरे स्कैन होगा, इन लिंक पर ट्रैवर्सल नहीं। nodes[END] पढ़ने पर इंडेक्स -1 इस्तेमाल होगा, जो C में अमान्य है; लूप को उससे पहले रुकना चाहिए।

C11 का पूरा सीमित उदाहरण

चलाने से पहले पहली आउटपुट लाइन का अनुमान लगाएँ। यह प्रोग्राम निरूपण जाँचता है, पहला मान पढ़ता है, सामने एक नोड जोड़ता है और फिर ट्रैवर्सल करता है। हर पढ़ने से पहले आवश्यक सुरक्षा-जाँच की जाती है।

#include <stdio.h>

enum { CAP = 4, END = -1 };

typedef struct {
    int value;
    int next;
} Node;

typedef struct {
    int ok;
    int value;
} ReadResult;

int valid_list(const Node nodes[], int used, int head) {
    if (used < 0 || used > CAP) {
        return 0;
    }
    int current = head;
    int count = 0;
    while (current != END) {
        if (current < 0 || current >= used || count == used) {
            return 0;
        }
        current = nodes[current].next;
        count = count + 1;
    }
    return count == used;
}

int print_list(const Node nodes[], int used, int head) {
    if (!valid_list(nodes, used, head)) {
        return 0;
    }
    int current = head;
    while (current != END) {
        printf("%d ", nodes[current].value);
        current = nodes[current].next;
    }
    printf("END\n");
    return 1;
}

ReadResult read_front(const Node nodes[], int used, int head) {
    ReadResult result = {0, 0};
    if (!valid_list(nodes, used, head) || head == END) {
        return result;
    }
    result.ok = 1;
    result.value = nodes[head].value;
    return result;
}

int main(void) {
    Node nodes[CAP] = {{10, 1}, {30, END}, {20, 0}, {0, END}};
    int used = 3;
    int head = 2;
    if (!print_list(nodes, used, head)) {
        return 1;
    }
    ReadResult first = read_front(nodes, used, head);
    if (first.ok) {
        printf("front: %d\n", first.value);
    }
    if (valid_list(nodes, used, head) && used < CAP) {
        int fresh = used;
        nodes[fresh].value = 7;
        nodes[fresh].next = head;
        head = fresh;
        used = used + 1;
    }
    if (!print_list(nodes, used, head)) {
        return 1;
    }
    return 0;
}

ठीक यही आउटपुट मिलता है:

20 10 30 END
front: 20
7 20 10 30 END

जाँचने वाला फ़ंक्शन सुरक्षित ढंग से क्यों रुकता है

valid_list पहले used का 0 से CAP के बाहर होना अस्वीकार करता है। फिर लिंक पर चलते हुए पढ़े गए नोड गिनता है। हर ऐरे-पठन से पहले वह जाँचता है कि current, [0, used) में है और अब तक used से कम कदम चले हैं। इसलिए END से अलग ऋणात्मक लिंक, बहुत बड़ा लिंक या चक्र मिलने पर असुरक्षित पठन अथवा अनंत लूप से पहले विफलता लौटती है। निश्चित next वाले नोड पर दोबारा पहुँचने से ट्रैवर्सल चक्र में फँस जाता है; बाद में उसी नोड से किसी अलग next पर निकल नहीं सकता। अधिकतम used पठन की सीमा ऐसा चक्र पकड़ लेती है।

यहाँ END तक पहुँचना आवश्यक है, लेकिन पर्याप्त नहीं। count == used यह भी जाँचता है कि सभी सक्रिय नोड तक पहुँचे। used = 3 हो, लेकिन शृंखला केवल इंडेक्स 0 से END तक हो, तो इस मॉडल का सभी सक्रिय नोड शामिल करने वाला नियम टूटता है। जाँच फ़ील्ड और लिंक की त्रुटियाँ पकड़ती है; कॉलर ने सच में CAP जीवित और आरंभिक मानों वाले रिकॉर्ड दिए हैं या नहीं, यह नहीं जाँच सकती। भंडारण का यह वादा कॉलर को निभाना होगा।

प्रिंट फ़ंक्शन पहले पूरी वैधता जाँचता है, इसलिए अमान्य इनपुट पर अधूरी लिस्ट भी नहीं छापता। सामने का मान पढ़ने वाला फ़ंक्शन भी पहले जाँचता है; खाली या अमान्य लिस्ट पर {0, 0} लौटता है। यदि पहले नोड का वैध डेटा 0 है, तो {1, 0} लौटता है। संख्यात्मक value के बजाय ok जाँचें। विफल परिणाम के दोनों शून्य केवल आरंभिक मान हैं; वे शून्य-डेटा वाले नोड को सफलतापूर्वक पढ़ना नहीं दर्शाते।

सामने नोड जोड़ना: head बदलने से पहले पुरानी शृंखला बचाएँ

main में जोड़ा गया नोड अगले अनुपयोगी स्लॉट, इंडेक्स 3, में रखा जाता है। यह तभी होता है जब पुराना निरूपण वैध हो और used < CAP हो।

1. fresh = used से 3 मिलता है; कोई सक्रिय नोड नहीं मिटता।
2. nodes[3].value = 7 डेटा रखता है।
3. nodes[3].next = head पुराने head का मान 2 रखता है।
4. head = 3 नए नोड को पहला बनाता है।
5. used का मान 4 होता है, इसलिए नई शृंखला चारों सक्रिय स्लॉट इस्तेमाल करती है।

नई लिंक-शृंखला 3 -> 2 -> 0 -> 1 -> END है। पुराने रिकॉर्ड भौतिक रूप से खिसकते नहीं हैं। अगर nodes[fresh].next = head से पहले head को fresh कर दें, तो नया नोड खुद की ओर लिंक करेगा और head से पुरानी शृंखला तक रास्ता टूट जाएगा। इन दोनों असाइनमेंट का क्रम महत्वपूर्ण है।

used == CAP होने पर सुरक्षा-शर्त जोड़ने वाले सभी कथन छोड़ देती है; head, used और सभी रिकॉर्ड वैसे ही रहते हैं। nodes[CAP] कोई वैध स्लॉट नहीं है। आरंभिक मानों वाले CAP-रिकॉर्ड ऐरे और used = 0, head = END से शुरू करने पर वही ब्लॉक इंडेक्स 0 पर next = END वाला नोड बनाता है: यह सही एक-नोड लिस्ट है। इस पाठ में कोई नोड हटाया नहीं जाता, इसलिए अगला अनुपयोगी इंडेक्स हमेशा used है। नोड हटाने और स्लॉट दोबारा इस्तेमाल करने में खाली स्लॉट का नियम बनाए बिना यही नीति न अपनाएँ।

एक सटीक उपमा

चार नंबर वाले लॉकर सोचें। हर लॉकर में एक संदेश और अगले लॉकर का नंबर है। अलग शुरुआती कार्ड पहले लॉकर का नंबर बताता है। END का अर्थ है कि कोई और लॉकर खोले बिना काम पूरा करें। लॉकर का नंबर इस छोटे मॉडल में स्थान पहचानता है, जबकि संदेश डेटा है; संदेश खुद आगे जाने का रास्ता नहीं बताता। लॉकर खिसकाए बिना कार्ड बदलकर जाने का क्रम बदला जा सकता है।

यह उपमा लिंक के क्रम और head को समझाती है। इससे अमान्य नंबर पर जाने की अनुमति नहीं मिलती, कंप्यूटर की मनमानी मेमोरी का मॉडल नहीं बनता और कार्ड पर चलते हुए रुकने की गारंटी भी नहीं मिलती। कार्ड का चक्र भी लिंक के चक्र की तरह अस्वीकार करना होगा।

मुख्य बातें

• एक नोड में डेटा और आगे जाने का एक next लिंक है; इस मॉडल में “सिंगली” का अर्थ हर नोड में एक next लिंक है।
• head पहले नोड को पहचानता है; END का अर्थ कोई नोड नहीं, खाली head के लिए भी यही नियम है।
• nodes[current].next पर चलें; अगले इंडेक्स का अनुमान न लगाएँ।
• स्थायी head और ट्रैवर्सल के current को अलग रखें।
• इंडेक्स से पढ़ने से पहले जाँच करें। खाली, भरी और अमान्य अवस्थाओं को अलग संभालना होता है।
• सामने जोड़ते समय head बदलने से पहले पुराने head को नए next में रखें।
• ऐरे-इंडेक्स लिंक सीमित शिक्षण निरूपण हैं। वे C के असली पॉइंटर नहीं हैं।

पहले स्वयं करें, फिर मिलाएँ

1. शुरू के तीन रिकॉर्ड रखें, लेकिन इंडेक्स 0 का डेटा -1 कर दें। क्या ट्रैवर्सल वहीं रुकता है? नहीं। डेटा 20, -1, 30 होगा; लिंक 2, 0, 1, END ही रहेंगे। अंत-संकेत लिंक पर लागू है, डेटा पर नहीं।
2. आरंभिक मानों वाले खाली ऐरे से शुरू करके दिखाए ब्लॉक से पहले 8, फिर 5 जोड़ें। लिंक 1 -> 0 -> END बनेंगे और डेटा 5, 8 होगा। used = 2 और head = 1 है।
3. शुरुआती लिस्ट में नोड 1 के next को END से 2 कर दें। जाँच इस चक्र को अस्वीकार करती है: तीन पठन के बाद current = 2 और count = used है। चौथा ऐरे-पठन नहीं होता।

छह मौलिक अभ्यास प्रश्न

चार विकल्पों में से ठीक एक चुनें। ये मौलिक बुनियादी अभ्यास हैं, पिछले वर्ष के प्रश्न या पूरा GATE मॉक नहीं। सभी प्रश्न ऊपर के सीमित निरूपण और C परिभाषाओं पर आधारित हैं; किसी लिंक में बदलाव अलग से बताए जाने पर ही मानें।

प्रश्न 1

शुरुआती तीन रिकॉर्ड और head = 2 के लिए ट्रैवर्सल END से पहले किस क्रम में डेटा छापता है?

A. 10, 30, 20 B. 20, 10, 30 C. 2, 0, 1 D. 20, 30, 10

प्रश्न 2

आरंभिक मानों वाले CAP-रिकॉर्ड ऐरे में used = 0 और head = END है। read_front क्या लौटाता है?

A. {1, 0}, क्योंकि खाली होने का अर्थ रखा हुआ शून्य है B. यह nodes[-1] पढ़कर उसका डेटा लौटाता है C. {0, 0}, बिना नोड का डेटा पढ़े D. {1, -1}, क्योंकि END पहला डेटा है

प्रश्न 3

मूल लिस्ट में head = 2 और used = 3 है। नए स्लॉट 3 में डेटा 7 सामने जोड़ने का सही क्रम कौन-सा है? मानें nodes[3].value = 7 हो चुका है।

A. head = 3; nodes[3].next = head; used = 4; B. nodes[3].next = head; head = 3; used = 4; C. nodes[3].next = END; head = 3; used = 4; D. nodes[2].next = 3; head = 3; used = 4;

प्रश्न 4

एक वैध लिस्ट में used = CAP = 4 है। main का सुरक्षा-शर्त वाला जोड़ने का ब्लॉक क्या करता है?

A. nodes[3] को बदल देता है B. nodes[4] में लिखकर used बढ़ाता है C. head को END कर देता है D. जोड़ना छोड़ देता है और पूरी अवस्था सुरक्षित रखता है

प्रश्न 5

शुरुआती लिस्ट में केवल nodes[1].next को END से 2 करते हैं। valid_list क्या और क्यों लौटाता है?

A. 0: शृंखला दोहराती है और कदम-जाँच चौथा लिंक पढ़ने से पहले अस्वीकार करती है B. 1: हर अलग इंडेक्स सीमा के भीतर है C. 1: END तक पहुँचे बिना भी तीन नोड पर एक बार जाना पर्याप्त है D. इसे अनंत रिकर्शन करना ही होगा

प्रश्न 6

जिस वैध पहले नोड का value = -1 है, उसके बारे में कौन-सा कथन सही है?

A. लिस्ट अवश्य खाली है B. read_front, ok = 0 लौटाता है क्योंकि -1 हमेशा विफलता है C. read_front, ok = 1 और value = -1 लौटाता है; ट्रैवर्सल अलग next फ़ील्ड से तय होता है D. उसका next भी -1 होना चाहिए

समझाए गए उत्तर

1. B

A गलत है: यह ऐरे में भंडारण का क्रम है, लिंक का क्रम नहीं।

B सही है: इंडेक्स 2, 0, 1 पर डेटा 20, 10, 30 है।

C गलत है: ये गए हुए इंडेक्स हैं, उनका डेटा नहीं।

D गलत है: नोड 2 का लिंक इंडेक्स 0 पर है, जिसका डेटा 10 है; वह सीधे इंडेक्स 1 पर नहीं जाता।

2. C

A गलत है: खाली लिस्ट से पहला डेटा सफलतापूर्वक नहीं पढ़ा जा सकता, इसलिए ok = 0 है।

B गलत है: वैधता और head की जाँच END से इंडेक्स करने से पहले लौट जाती है।

C सही है: खाली निरूपण वैध है; head की जाँच आरंभिक विफल परिणाम लौटाती है।

D गलत है: END head या लिंक का संकेत है, मौजूद डेटा नोड नहीं।

3. B

A गलत है: head = 3 के बाद next = head करने से 3 पर खुद का चक्र बनता है।

B सही है: नया head 3 करने से पहले पुराने head 2 को next में बचाता है। शृंखला 3, 2, 0, 1, END है।

C गलत है: नया head तुरंत शृंखला समाप्त कर देता है; तीन पुराने सक्रिय नोड तक पहुँचना बंद हो जाता है।

D गलत है: पुराना head लिंक बदलता है, लेकिन नया नोड पुराने head से नहीं जुड़ता। अनुपयोगी स्लॉट का शुरुआती next = END होने से केवल नोड 3 तक पहुँचा जा सकता है।

4. D

A गलत है: used < CAP असत्य है, इसलिए जोड़ने का कोई असाइनमेंट नहीं चलता।

B गलत है: nodes[4] चार-स्लॉट ऐरे के बाहर है; सुरक्षा-शर्त यह लेखन रोकती है।

C गलत है: विफलता पर head बदलने वाला कोई कथन नहीं है।

D सही है: क्षमता भर चुकी है, इसलिए head, used और हर रिकॉर्ड वैसे ही रहते हैं।

5. A

A सही है: इंडेक्स 2, 0, 1 पढ़ने के बाद current = 2 और count = used = 3 है; अगली पुनरावृत्ति पढ़ने से पहले 0 लौटाती है।

B गलत है: इंडेक्स सीमा में होने से चक्र की संभावना समाप्त नहीं होती।

C गलत है: सभी सक्रिय नोड तक पहुँचने के बाद वैध शृंखला को END पर समाप्त भी होना चाहिए।

D गलत है: जाँच फ़ंक्शन लूप वाला है और लिंक-पठन की संख्या स्पष्ट रूप से सीमित करता है।

6. C

A गलत है: खाली होना head == END से तय होता है, डेटा से नहीं।

B गलत है: read_front अलग ok फ़ील्ड इस्तेमाल करता है; int का हर डेटा मान स्वीकार है।

C सही है: सफल पठन में -1 डेटा हो सकता है। केवल head और next में END का अर्थ कोई नोड नहीं है।

D गलत है: डेटा और लिंक अलग फ़ील्ड हैं; इस नोड के बाद दूसरा नोड हो सकता है।

सीमा और अगला कदम

अब आप डेटा, नोड इंडेक्स और लिंक का अंतर पहचान सकते हैं, सीमित सिंगली लिंक्ड लिस्ट का ट्रेस बना सकते हैं और सुरक्षित ढंग से सामने नोड जोड़ सकते हैं। आगे स्टैक का LIFO नियम और क्यू का FIFO नियम पढ़ें। ये तीन पाठ शुरुआती सेतु हैं, संपूर्ण डेटा-स्ट्रक्चर या GATE CS तैयारी नहीं। इनसे किसी मौजूदा कोर्स का परीक्षा-वर्ष नहीं बदलता। हिंदी शिक्षण में सहायता है, आधिकारिक हिंदी GATE पेपर होने का दावा नहीं।