सूचना हमारे चारों ओर है।

सॉफ्टवेयर की दुनिया में, हम अपनी जानकारी को व्यवस्थित करने के लिए जो तरीके चुनते हैं, वह आधी लड़ाई है। हालांकि यहाँ बात है: एक समस्या को हल करने के लिए बहुत सारे तरीके हैं । और जब हमारे डेटा को व्यवस्थित करने की बात आती है, तो बहुत सारे उपकरण हैं जो नौकरी के लिए काम कर सकते हैं। चाल जान रही है कि कौन सा उपकरण उपयोग करने के लिए सही है ।

भले ही हम किस भाषा में कोडिंग करना शुरू करते हैं, पहली चीज़ जो हमारे सामने आती है, वह डेटा संरचनाएं हैं , जो कि हमारे डेटा को व्यवस्थित करने के विभिन्न तरीके हैं; चर , सरणियाँ , हैश और वस्तुएँ सभी प्रकार की डेटा संरचनाएँ हैं। लेकिन ये अभी भी हिमशैल के टिप हैं जब यह डेटा संरचनाओं की बात आती है; बहुत अधिक हैं, जिनमें से कुछ सुपर जटिल लगने लगते हैं जितना कि आप उनके बारे में सुनते हैं।

मेरे लिए उन जटिल चीजों में से एक हमेशा से जुड़ी हुई सूचियाँ हैं । मैं अब कुछ वर्षों के लिए लिंक की गई सूचियों के बारे में जानता हूं, लेकिन मैं उन्हें कभी भी सीधे अपने सिर में नहीं रख सकता। मैं केवल उनके बारे में सोचता हूं जब मैं तकनीकी साक्षात्कार के लिए (या कभी-कभी, बीच में) तैयारी कर रहा होता हूं, और कोई मुझसे उनके बारे में पूछता है। मैं थोड़ा शोध करूंगा और सोचूंगा कि मैं समझता हूं कि वे क्या कर रहे हैं, लेकिन कुछ हफ्तों के बाद, मैं उन्हें फिर से भूल जाता हूं। पूरी बात काफी अक्षम है, और यह सब इस तथ्य से उपजा है कि मुझे पता है कि वे मौजूद हैं, लेकिन मैं मौलिक रूप से उन्हें नहीं समझता हूं! तो, यह उस समय को बदलने और सवाल का जवाब देने का समय है: पृथ्वी पर क्या एक जुड़ी हुई सूची है, वैसे भी?

रैखिक डेटा संरचनाएं

यदि हम वास्तव में लिंक्ड लिस्ट की मूल बातों को समझना चाहते हैं, तो यह महत्वपूर्ण है कि हम किस प्रकार की डेटा संरचना के बारे में बात करें ।

लिंक की गई सूचियों की एक विशेषता यह है कि वे रैखिक डेटा संरचनाएं हैं , जिसका अर्थ है कि एक क्रम और एक क्रम है कि वे कैसे निर्मित और ट्रैवर्स किए जाते हैं। हम hopscotch के एक खेल की तरह एक रेखीय डेटा संरचना के बारे में सोच सकते हैं : सूची के अंत में जाने के लिए, हमें क्रम में सभी वस्तुओं से गुजरना होगा, या क्रमिक रूप से । हालांकि, रैखिक संरचनाएं, गैर-रैखिक संरचनाओं के विपरीत हैं। में गैर रेखीय डाटा संरचनाओं , आइटम क्रम में व्यवस्थित किया जाना है, जिसका अर्थ है कि हम डेटा संरचना पार कर सकता है की जरूरत नहीं है गैर क्रमिक रूप से ।

हम इसे हमेशा महसूस नहीं कर सकते हैं, लेकिन हम सभी हर रोज रैखिक और गैर-रैखिक डेटा संरचनाओं के साथ काम करते हैं! जब हम अपने डेटा को हैश में व्यवस्थित करते हैं (कभी-कभी शब्दकोष कहा जाता है ), तो हम एक गैर-रैखिक डेटा संरचना को लागू कर रहे हैं। पेड़ और रेखांकन भी गैर-रेखीय डेटा संरचनाएं हैं जिन्हें हम अलग-अलग तरीकों से पार करते हैं, लेकिन हम उनके बारे में अधिक गहराई से बाद में बात करेंगे।

इसी तरह, जब हम अपने कोड में सरणियों का उपयोग करते हैं, तो हम एक रैखिक डेटा संरचना लागू कर रहे हैं! यह सरणियों और लिंक्ड सूचियों के बारे में सोचने के लिए सहायक हो सकता है जिस तरह से हम डेटा अनुक्रम करते हैं। इन दोनों संरचनाओं में, आदेश मायने रखता है । लेकिन क्या arrays और लिंक्ड सूची अलग बनाता है?

स्मृति प्रबंधन

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

लेकिन इसका मतलब यह नहीं है कि स्मृति आवंटन नहीं हो रहा है! अमूर्तता जादू नहीं है, यह सिर्फ उन चीजों को छिपाने की सरलता है जो आपको हर समय देखने या उससे निपटने की आवश्यकता नहीं है। यहां तक ​​कि अगर हमें कोड लिखते समय मेमोरी आवंटन के बारे में सोचने की ज़रूरत नहीं है, अगर हम वास्तव में समझना चाहते हैं कि एक लिंक की गई सूची में क्या चल रहा है और यह शक्तिशाली बनाता है, तो हमें अल्पविकसित स्तर पर उतरना होगा।

हमने पहले से ही बाइनरी के बारे में सीखा है और डेटा को बिट्स और बाइट्स में कैसे तोड़ा जा सकता है । जिस तरह वर्ण, संख्या, शब्द, वाक्य को उनका प्रतिनिधित्व करने के लिए मेमोरी बाइट्स की आवश्यकता होती है, उसी प्रकार डेटा संरचनाएं।

जब एक सरणी बनाई जाती है, तो उसे निश्चित मात्रा में मेमोरी की आवश्यकता होती है। यदि हमारे पास 7 पत्र हैं जिन्हें हमें किसी सरणी में संग्रहीत करने की आवश्यकता है, तो हमें उस सरणी का प्रतिनिधित्व करने के लिए 7 बाइट्स मेमोरी की आवश्यकता होगी। लेकिन, हमें एक सन्निहित ब्लॉक में उस मेमोरी की आवश्यकता होगी । कहने का तात्पर्य यह है कि, हमारे कंप्यूटर को मेमोरी के 7 बाइट का पता लगाने की आवश्यकता होती है, जो कि एक जगह पर, दूसरे के बगल में, एक साथ एक बाइट पर, एक ही जगह पर होता है।

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

सरणियों और लिंक की गई सूचियों के बीच मौलिक अंतर यह है कि सरणियों है कर रहे हैं स्थिर डेटा संरचनाओं , जबकि जुड़ा हुआ सूचियों हैं गतिशील डेटा संरचनाओं । एक स्थैतिक डेटा संरचना को इसके सभी संसाधनों की आवश्यकता होती है जब संरचना बनाई जाती है; इसका मतलब यह है कि भले ही संरचना आकार में बढ़ने या सिकुड़ने के लिए थी और तत्वों को जोड़ा या हटाया जाना था, फिर भी इसे हमेशा दिए गए आकार और स्मृति की मात्रा की आवश्यकता होती है। यदि स्थैतिक डेटा संरचना में और अधिक तत्वों को जोड़ने की आवश्यकता है और इसमें पर्याप्त मेमोरी नहीं है, तो आपको उस सरणी के डेटा को कॉपी करने की आवश्यकता होगी, उदाहरण के लिए, और इसे अधिक मेमोरी के साथ फिर से बनाना, ताकि आप तत्वों को जोड़ सकें। यह।

दूसरी ओर, एक गतिशील डेटा संरचना सिकुड़ सकती है और स्मृति में बढ़ सकती है। इसे मौजूद रहने के लिए मेमोरी की एक निर्धारित राशि की आवश्यकता नहीं होती है, और इसका आकार और आकार बदल सकता है, और इसकी जितनी मात्रा में स्मृति की आवश्यकता हो सकती है बदल सकती है।

अब तक, हम पहले से ही सरणियों और लिंक की गई सूचियों के बीच कुछ प्रमुख अंतर देख सकते हैं। लेकिन यह सवाल भी पैदा करता है: क्या एक जुड़ी हुई सूची इसकी स्मृति को हर जगह बिखेर देती है? इस प्रश्न का उत्तर देने के लिए, हमें उस तरह से देखने की जरूरत है, जिससे एक लिंक की गई सूची संरचित है।

एक लिंक्ड सूची के कुछ हिस्सों

एक लिंक की गई सूची छोटी या बड़ी हो सकती है, लेकिन कोई फर्क नहीं पड़ता कि आकार, इसे बनाने वाले हिस्से वास्तव में काफी सरल हैं। एक लिंक की गई सूची नोड्स की एक श्रृंखला से बनी है , जो सूची के तत्व हैं।

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

एक एकल नोड भी बहुत सरल है। इसके केवल दो भाग हैं: डेटा , या नोड में मौजूद जानकारी और अगले नोड का संदर्भ ।

यदि हम इसके चारों ओर अपने सिर लपेट सकते हैं, तो हम वहां आधे रास्ते पर हैं। जिस तरह से नोड्स काम करते हैं वह सुपर महत्वपूर्ण है, और सुपर शक्तिशाली है, और इसे संक्षेप में प्रस्तुत किया जा सकता है:

एक नोड केवल यह जानता है कि इसमें कौन सा डेटा शामिल है, और इसका पड़ोसी कौन है।

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

और यह एक बहुत ही कारण है कि एक लिंक की गई सूची को मेमोरी के एक सन्निहित ब्लॉक की आवश्यकता नहीं है। क्योंकि किसी एकल नोड में "पता" या अगले नोड का संदर्भ है, उन्हें एक दूसरे के ठीक बगल में रहने की आवश्यकता नहीं है, जिस तरह से तत्वों को एक सरणी में रखना है। इसके बजाय, हम केवल इस तथ्य पर भरोसा कर सकते हैं कि हम अपनी सूची को अगले नोड के लिए पॉइंटर संदर्भों पर झुकाव करके आगे बढ़ा सकते हैं, जिसका अर्थ है कि हमारी मशीनों को हमारी सूची का प्रतिनिधित्व करने के लिए स्मृति के एक एकल भाग को बंद करने की आवश्यकता नहीं है।

यह इस बात के लिए भी स्पष्टीकरण है कि लिंक की गई सूचियाँ प्रोग्राम के निष्पादन के दौरान गतिशील रूप से क्यों बढ़ और सिकुड़ सकती हैं। किसी लिंक की गई सूची के साथ एक नोड को जोड़ना या हटाना किसी व्यूह के तत्वों पर कॉपी करने के बजाय कुछ बिंदुओं को पुन: व्यवस्थित करना जितना आसान हो जाता है! हालाँकि, लिंक की गई सूचियों में कुछ कमियां भी हैं, जिनका मैं अभी तक आपसे जिक्र नहीं कर रहा हूँ - लेकिन अगले सप्ताह उन पर।

अभी के लिए, हम बस कैसे जुड़े सूचियों की महिमा में bask हूँ!

सभी आकृतियों और आकारों की सूची

भले ही किसी लिंक की गई सूची के हिस्से नहीं बदलते हैं, लेकिन जिस तरह से हम अपनी लिंक की गई सूचियों को बनाते हैं, वह काफी भिन्न हो सकती है। सॉफ़्टवेयर की अधिकांश चीजों की तरह, जिस समस्या को हम हल करने का प्रयास कर रहे हैं, उसके आधार पर, एक प्रकार की लिंक्ड सूची अन्य की तुलना में नौकरी के लिए बेहतर उपकरण हो सकती है।

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

लेकिन जिस तरह एक नोड अपने बाद के पड़ोसी नोड को संदर्भित कर सकता है, वैसे ही इसके पूर्ववर्ती नोड के लिए भी एक संदर्भ सूचक हो सकता है! इसे हम दोहरी लिंक्ड सूची कहते हैं , क्योंकि प्रत्येक नोड के भीतर दो संदर्भ निहित होते हैं: अगले नोड के साथ-साथ पिछले नोड का भी संदर्भ । यह मददगार हो सकता है यदि हम अपनी डेटा संरचना को न केवल एक ही ट्रैक या दिशा में, बल्कि पीछे की ओर भी ले जाना चाहते हैं।

उदाहरण के लिए, अगर हम सूची के बहुत शुरुआत में वापस जाने के बिना एक नोड और नोड के बीच आशा करना चाहते थे, तो एक दोगुनी लिंक की गई सूची एक एकल लिंक की गई सूची की तुलना में बेहतर डेटा संरचना होगी। हालाँकि, हर चीज के लिए स्थान और स्मृति की आवश्यकता होती है, इसलिए यदि हमारे नोड को केवल एक के बजाय दो संदर्भ बिंदुओं को संग्रहीत करना था, तो विचार करना दूसरी बात होगी।

एक सर्कुलर लिंक्ड लिस्ट थोड़ी अजीब है कि यह एक शून्य मान की ओर इशारा करते हुए समाप्त नहीं होती है। इसके बजाय, इसमें एक नोड है जो सूची की पूंछ (पारंपरिक हेड नोड के बजाय) के रूप में कार्य करता है , और पूंछ नोड के बाद का नोड सूची की शुरुआत है। यह संगठन संरचना सूची के अंत में कुछ जोड़ने के लिए वास्तव में आसान बनाता है, क्योंकि आप इसे टेल नोड पर ट्रेस करना शुरू कर सकते हैं, क्योंकि पहला तत्व और अंतिम तत्व एक दूसरे को इंगित करते हैं। सर्कुलर लिंक्ड लिस्ट वास्तव में क्रेजी होना शुरू कर सकती है क्योंकि हम दोनों एक सिंगली लिंक्ड लिस्ट और दोगुनी लिंक्ड लिस्ट को एक सर्कुलर लिंक्ड लिस्ट में बदल सकते हैं!

कोई फर्क नहीं पड़ता कि कोई लिंक की गई सूची कितनी जटिल है, अगर हम एक नोड के मूल सिद्धांतों को याद रख सकते हैं और यह कैसे काम करता है और हमारी सूची में अलग-अलग सूचक संदर्भ कैसे संरचित हैं, तो कोई लिंक नहीं की गई सूची से हम निपट नहीं सकते हैं!

अगले सप्ताह, इस श्रृंखला के भाग 2 में, हम अपने दांतों को लिंक्ड सूचियों के अंतरिक्ष समय की जटिलता में डुबो देंगे, और वे अपने चचेरे भाई, सरणी से तुलना कैसे करेंगे। मैं वादा करता हूँ कि यह वास्तव में बहुत अधिक मजेदार है जितना लगता है!

संसाधन

अगर आपको लगता है कि लिंक्ड लिस्ट सुपर कूल हैं, तो इन सहायक संसाधनों को देखें।

1. Arrays और लिंक्ड सूची , डेमियन विंटौर के बीच अंतर
2. डेटा स्ट्रक्चर्स: लिंक बनाम लिस्टेड माइकोडस्कूल एरेस
3. लिंक्ड लिस्ट: द बेसिक्स , डॉ। एडवर्ड गेहिंगर
4. लिंक्ड लिस्ट का परिचय , डॉ। विक्टर एडमचिक
5. डेटा संरचना और कार्यान्वयन , डॉ। जेनिफर वेल्च
6. स्टेटिक डेटा स्ट्रक्चर्स बनाम डायनेमिक डेटा स्ट्रक्चर्स , अयोमा गायन विजेथुंगा