लिंक्ड डेटा संरचना: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Tag: Manual revert
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
[[कंप्यूटर विज्ञान]] में, लिंक्ड [[डेटा संरचना]] एक डेटा संरचना है जिसमें एक साथ जुड़े [[रिकॉर्ड (कंप्यूटर विज्ञान)|डेटा रिकॉर्ड (कंप्यूटर विज्ञान)]] ("'[[नोड (कंप्यूटर विज्ञान)]]'') का एक समूह होता है और [[संदर्भ (कंप्यूटर विज्ञान)|संदर्भ (लिंक या पॉइंटर्स)]]'' द्वारा व्यवस्थित किया जाता है। डेटा के बीच के लिंक को योजक भी कहा जा सकता है।
[[कंप्यूटर विज्ञान]] में, लिंक्ड [[डेटा संरचना]] एक डेटा संरचना है जिसमें एक साथ जुड़े [[रिकॉर्ड (कंप्यूटर विज्ञान)|डेटा रिकॉर्ड (कंप्यूटर विज्ञान)]] ("'[[नोड (कंप्यूटर विज्ञान)]]'') का एक समूह होता है और [[संदर्भ (कंप्यूटर विज्ञान)|संदर्भ (लिंक या पॉइंटर्स)]]'' द्वारा व्यवस्थित किया जाता है। डेटा के बीच के लिंक को योजक भी कहा जा सकता है।


लिंक की गई डेटा संरचनाओं में, लिंक को सामान्यतः विशेष [[डेटा प्रकार]] के रूप में माना जाता है जो केवल संदर्भ (कंप्यूटर विज्ञान) किया जा सकता है या समानता के लिए तुलना की जा सकती है। लिंक्ड डेटा संरचनाओं इस प्रकार सरणियों डेटा संरचना और अन्य डेटा संरचनाओं के विपरीत हैं, जिन्हें पॉइंटर्स पर अंकगणितीय ऑपरेशन करने की आवश्यकता होती है। यह अंतर तब भी होता है जब नोड्स वास्तव में एकल सरणी के तत्वों के रूप में प्रायुक्त होते हैं, और संदर्भ वास्तविक में [[सरणी डेटा संरचना|सरणी डेटा सूचकांक]] होते हैं: जब तक कि उन सूचकांकों पर कोई अंकगणित नहीं किया जाता है, तब तक डेटा संरचना अनिवार्य रूप से जुड़ा होता है।
लिंक की गई डेटा संरचनाओं में, लिंक को सामान्यतः विशेष [[डेटा प्रकार]] के रूप में माना जाता है जो केवल संदर्भ (कंप्यूटर विज्ञान) किया जा सकता है या समानता के लिए तुलना की जा सकती है। लिंक्ड डेटा संरचनाओं इस प्रकार सरणियों डेटा संरचना और अन्य डेटा संरचनाओं के विपरीत हैं, जिन्हें पॉइंटर्स पर अंकगणितीय ऑपरेशन करने की आवश्यकता होती है। यह अंतर तब भी होता है जब नोड्स वास्तविक में एकल सरणी के तत्वों के रूप में प्रायुक्त होते हैं, और संदर्भ वास्तविक में [[सरणी डेटा संरचना|सरणी डेटा सूचकांक]] होते हैं: जब तक कि उन सूचकांकों पर कोई अंकगणित नहीं किया जाता है, तब तक डेटा संरचना अनिवार्य रूप से जुड़ा होता है।


डायनेमिक आवंटन का उपयोग करके और सरणी सूचकांक लिंकिंग का उपयोग करके लिंकिंग दो विधियों से की जा सकती है।
डायनेमिक आवंटन का उपयोग करके और सरणी सूचकांक लिंकिंग का उपयोग करके लिंकिंग दो विधियों से की जा सकती है।


लिंक्ड डेटा संरचना में [[ लिंक्ड सूची ]], [[ खोज पेड़ | सर्च ट्री]] , [[ अभिव्यक्ति वृक्ष | एक्सप्रेशन ट्री]] और कई अन्य व्यापक रूप से उपयोग किए जाने वाले डेटा संरचना सम्मिलित हैं। वे कई कुशल एल्गोरिदम, जैसे [[टोपोलॉजिकल सॉर्ट]]<ref name="knuth">[[Donald Knuth]], [[The Art of Computer Programming]]</ref> और सेट यूनियन-फाइंड के लिए महत्वपूर्ण बिल्डिंग ब्लॉक भी हैं।<ref name="galfis">[[Bernard A. Galler]] and [[Michael J. Fischer]]. An improved equivalence algorithm. ''[[Communications of the ACM]],'' Volume 7, Issue 5 (May 1964), pages 301–303. The paper originating disjoint-set forests. [http://portal.acm.org/citation.cfm?doid=364099.364331 ACM Digital Library]</ref>
लिंक्ड डेटा संरचना में [[ लिंक्ड सूची ]], [[ खोज पेड़ | सर्च ट्री]] , [[ अभिव्यक्ति वृक्ष | एक्सप्रेशन ट्री]] और कई अन्य व्यापक रूप से उपयोग किए जाने वाले डेटा संरचना सम्मिलित हैं। वे कई कुशल एल्गोरिदम, जैसे [[टोपोलॉजिकल सॉर्ट]]<ref name="knuth">[[Donald Knuth]], [[The Art of Computer Programming]]</ref> और सेट यूनियन-फाइंड के लिए महत्वपूर्ण रचक खंड भी हैं।<ref name="galfis">[[Bernard A. Galler]] and [[Michael J. Fischer]]. An improved equivalence algorithm. ''[[Communications of the ACM]],'' Volume 7, Issue 5 (May 1964), pages 301–303. The paper originating disjoint-set forests. [http://portal.acm.org/citation.cfm?doid=364099.364331 ACM Digital Library]</ref>




Line 12: Line 12:


===लिंक की गई सूचियां===
===लिंक की गई सूचियां===
लिंक की गई सूची [[संरचना]]ओं का संग्रह है जो स्मृति में उनके भौतिक प्लेसमेंट द्वारा नहीं बल्कि संरचना में डेटा के हिस्से के रूप में संग्रहीत तार्किक लिंक द्वारा आदेशित है। यह आवश्यक नहीं है कि इसे सन्निकट स्मृति स्थानों में संग्रहित किया जाए। प्रत्येक संरचना में डेटा फ़ील्ड और पता फ़ील्ड होता है। पता फ़ील्ड में इसके उत्तराधिकारी (ग्राफ़ सिद्धांत) का पता होता है।
लिंक की गई सूची [[संरचना|संरचनाओं]] का एक संग्रह है जो स्मृति में उनके भौतिक व्यवस्था द्वारा नहीं किन्तु संरचना में डेटा के भाग के रूप में संग्रहीत तार्किक लिंक द्वारा आदेशित है। यह आवश्यक नहीं है कि इसे सन्निकट स्मृति स्थानों में संग्रहित किया जाए। प्रत्येक संरचना में डेटा क्षेत्र और पता क्षेत्र होता है। पता क्षेत्र में इसके उत्तराधिकारी (ग्राफ़ सिद्धांत) का पता होता है।


लिंक्ड लिस्ट सिंगल, डबल या मल्टीप्ल लिंक्ड हो सकती है और या तो लीनियर या सर्कुलर हो सकती है।
लिंक्ड लिस्ट एकल, दोहरा या एकाधिक लिंक्ड हो सकती है और या तो रेखीय या वृत्तीय हो सकती है।


; मूल गुण
; मूल गुण


* ऑब्जेक्ट्स, जिन्हें नोड कहा जाता है, रेखीय क्रम में जुड़े होते हैं।
* वस्तुएं, जिन्हें नोड कहा जाता है, रेखीय क्रम में जुड़े होते हैं।
* सूची के पहले नोड का संदर्भ हमेशा रखा जाता है। इसे 'सिर' या 'सामने' कहा जाता है।<ref>http://www.cs.toronto.edu/~hojjat/148s07/lectures/week5/07linked.pdf {{Bare URL PDF|date=March 2022}}</ref>
* सूची के पहले नोड का संदर्भ हमेशा रखा जाता है। इसे 'सिर' या 'सामने' कहा जाता है।<ref>http://www.cs.toronto.edu/~hojjat/148s07/lectures/week5/07linked.pdf {{Bare URL PDF|date=March 2022}}</ref>
<डिव वर्ग = केंद्र>[[Image:Singly-linked-list.svg]]<br /><small>''A linked list with three nodes contain two fields each: an integer value and a link to the next node''</small></div>
[[Image:Singly-linked-list.svg]]<br /><small>''तीन नोड्स वाली एक लिंक्ड सूची में दो क्षेत्र होते हैं जिनमें से प्रत्येक एक पूर्णांक मान और अगले नोड के लिए एक लिंक होता है''</small>


[[File:single node1.svg|thumb|center|नोड के साथ लिंक की गई सूची।]]
[[File:single node1.svg|thumb|center|नोड के साथ लिंक की गई सूची।]]
Line 36: Line 36:




==== सी ==== में उदाहरण
 
यह C में लिंक की गई सूची के कार्यान्वयन के लिए उपयोग की जाने वाली संरचना का उदाहरण है:
'''सी में उदाहरण'''
 
यह सी में लिंक की गई सूची के कार्यान्वयन के लिए उपयोग की जाने वाली संरचना का उदाहरण है:


<syntaxhighlight lang=c>
<syntaxhighlight lang=c>
Line 58: Line 60:


</syntaxhighlight>
</syntaxhighlight>
नोट: इस तरह की संरचना जिसमें सदस्य होता है जो समान संरचना की ओर इशारा करता है, स्व-संदर्भित संरचना कहलाती है।
नोट: इस तरह की संरचना जिसमें सदस्य होता है जो समान संरचना की ओर संकेत करता है, स्व-संदर्भित संरचना कहलाती है।
 
'''सी ++ में उदाहरण'''


==== सी ++ ==== में उदाहरण
यह सी++ में लिंक की गई सूची के कार्यान्वयन के लिए उपयोग की जाने वाली नोड वर्ग संरचना का उदाहरण है:
यह C++ में लिंक की गई सूची के कार्यान्वयन के लिए उपयोग की जाने वाली नोड वर्ग संरचना का उदाहरण है:


<syntaxhighlight lang=cpp>
<syntaxhighlight lang=cpp>
Line 73: Line 76:


=== पेड़ खोजें ===
=== पेड़ खोजें ===
सर्च ट्री ट्री डेटा संरचना है जिसके नोड्स में डेटा वैल्यू को कुछ ऑर्डर किए गए समूह से स्टोर किया जा सकता है, जो ऐसा है कि ट्री के [[इन-ऑर्डर ट्रैवर्सल]] में स्टोर किए गए वैल्यू के आरोही क्रम में नोड्स का दौरा किया जाता है।
सर्च ट्री एक ट्री डेटा संरचना है जिसके नोड्स में डेटा मान को कुछ आदिष्ट किए गए समूह से संचय किया जा सकता है, जो ऐसा है कि ट्री के [[इन-ऑर्डर ट्रैवर्सल|क्रम में पथक्रमण]] में संचय किए गए मान के आरोही क्रम में नोड्स का दौरा किया जाता है।


; बुनियादी गुण
; बुनियादी गुण


* ऑब्जेक्ट्स, जिन्हें नोड्स कहा जाता है, ऑर्डर किए गए समूह में स्टोर किए जाते हैं।
* वस्तुएं, जिन्हें नोड्स कहा जाता है, आदिष्ट किए गए समूह में संचय किए जाते हैं।
* इन-ऑर्डर ट्रैवर्सल ट्री में डेटा का आरोही रीडआउट प्रदान करता है।
* क्रम में पथक्रमण ट्री में डेटा का आरोही अनुशीर्षक प्रदान करता है।


== फायदे और नुकसान ==
== लाभ और हानि ==


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


सरणी में, सरणी तत्वों को मेमोरी के कॉन्टिगुटी (कंप्यूटर विज्ञान) (जुड़े और अनुक्रमिक) भाग में होना चाहिए। लेकिन लिंक्ड डेटा संरचना में, प्रत्येक नोड का संदर्भ उपयोगकर्ताओं को अगले को खोजने के लिए आवश्यक जानकारी देता है। सरणियों के विपरीत, लिंक्ड डेटा संरचना के नोड्स को उनके बीच तार्किक कनेक्शन को प्रभावित किए बिना व्यक्तिगत रूप से भौतिक मेमोरी के भीतर अलग-अलग स्थानों पर ले जाया जा सकता है। उचित देखभाल के साथ, निश्चित [[प्रक्रिया (कंप्यूटिंग)]] या [[थ्रेड (कंप्यूटिंग)]] डेटा संरचना के हिस्से में नोड्स को जोड़ या हटा सकता है, जबकि अन्य प्रक्रियाएं या थ्रेड्स अन्य भागों पर काम कर रहे हैं।
सरणी में, सरणी तत्वों को मेमोरी के संस्पर्श (कंप्यूटर विज्ञान) (जुड़े और अनुक्रमिक) भाग में होना चाहिए। लेकिन लिंक्ड डेटा संरचना में, प्रत्येक नोड का संदर्भ उपयोगकर्ताओं को अगले को खोजने के लिए आवश्यक जानकारी देता है। सरणियों के विपरीत, लिंक्ड डेटा संरचना के नोड्स को उनके बीच तार्किक संबंध को प्रभावित किए बिना व्यक्तिगत रूप से भौतिक मेमोरी के अन्दर अलग-अलग स्थानों पर ले जाया जा सकता है। उचित देखभाल के साथ, निश्चित [[प्रक्रिया (कंप्यूटिंग)]] या [[थ्रेड (कंप्यूटिंग)]] डेटा संरचना के हिस्से में नोड्स को जोड़ या हटा सकता है, चूँकि अन्य प्रक्रियाएं या थ्रेड्स अन्य भागों पर काम कर रहे हैं।


दूसरी ओर, लिंक किए गए डेटा संरचना में किसी विशेष नोड तक पहुंच के लिए प्रत्येक नोड में संग्रहीत संदर्भों की श्रृंखला का पालन करना आवश्यक है। यदि संरचना में n नोड हैं, और प्रत्येक नोड में अधिकांश b लिंक हैं, तो कुछ ऐसे नोड होंगे जिन तक लॉग से कम में नहीं पहुँचा जा सकता है<sub>''b''</sub> n चरण, इन नोड्स तक पहुँचने की प्रक्रिया को धीमा करना - यह कभी-कभी काफी मंदी का प्रतिनिधित्व करता है, विशेष रूप से बड़ी संख्या में नोड्स वाली संरचनाओं के मामले में। कई संरचनाओं के लिए, कुछ नोड्स को n−1 चरणों तक सर्वोत्तम, सबसे खराब और औसत मामले की आवश्यकता हो सकती है। इसके विपरीत, कई सरणी डेटा संरचनाएं प्रविष्टियों की संख्या से स्वतंत्र संचालन की निरंतर संख्या के साथ किसी भी तत्व तक पहुंच की अनुमति देती हैं।
दूसरी ओर, लिंक किए गए डेटा संरचना में किसी विशेष नोड तक पहुंच के लिए प्रत्येक नोड में संग्रहीत संदर्भों की श्रृंखला का पालन करना आवश्यक है। यदि संरचना में n नोड हैं, और प्रत्येक नोड में अधिकांश b लिंक हैं, तो कुछ ऐसे नोड होंगे जिन तक log<sub>''b''</sub> n चरण से कम में नहीं पहुँचा जा सकता है, इन नोड्स तक पहुँचने की प्रक्रिया को धीमा करना - यह कभी-कभी विशेष रूप से बड़ी संख्या में नोड्स वाली संरचनाओं के स्थिति में अधिक मंदी का प्रतिनिधित्व करता है।। कई संरचनाओं के लिए, कुछ नोड्स को n−1 चरणों तक सर्वोत्तम, सबसे खराब और औसत स्थिति की आवश्यकता हो सकती है। इसके विपरीत, कई सरणी डेटा संरचनाएं प्रविष्टियों की संख्या से स्वतंत्र संचालन की निरंतर संख्या के साथ किसी भी तत्व तक पहुंच की अनुमति देती हैं।


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


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


सरणियों में, n वें तत्व को तुरंत एक्सेस किया जा सकता है, जबकि लिंक्ड डेटा संरचना में हमें कई पॉइंटर्स का पालन करना पड़ता है, इसलिए एलिमेंट का एक्सेस टाइम अलग-अलग होता है, जहां एलिमेंट संरचना में होता है।
सरणियों में, n वें तत्व को तुरंत एक्सेस किया जा सकता है, चूँकि लिंक्ड डेटा संरचना में हमें कई पॉइंटर्स का पालन करना पड़ता है, इसलिए तत्व का एक्सेस समय अलग-अलग होता है, जहां तत्व संरचना में होता है।


कुछ [[सैद्धांतिक कंप्यूटर विज्ञान]] में जो लिंक्ड संरचनाओं की बाधाओं को लागू करते हैं, जैसे कि [[ सूचक मशीन ]], कई समस्याओं के लिए अनियंत्रित [[रैंडम एक्सेस मशीन]] मॉडल की तुलना में अधिक चरणों की आवश्यकता होती है।
कुछ [[सैद्धांतिक कंप्यूटर विज्ञान]] में जो लिंक्ड संरचनाओं की बाधाओं को प्रायुक्त करते हैं, जैसे कि [[ सूचक मशीन ]], कई समस्याओं के लिए अनियंत्रित [[रैंडम एक्सेस मशीन]] मॉडल की तुलना में अधिक चरणों की आवश्यकता होती है।


== यह भी देखें ==
== यह भी देखें ==
Line 104: Line 107:
{{Reflist}}
{{Reflist}}


{{Data structures}}
[[Category:All articles with bare URLs for citations]]
[[Category: सार डेटा प्रकार]] [[Category: लिंक्ड सूचियाँ]] [[Category: पेड़ (डेटा संरचनाएं)]]  
[[Category:Articles with PDF format bare URLs for citations]]
 
[[Category:Articles with bare URLs for citations from March 2022]]
 
[[Category:Articles with invalid date parameter in template]]
 
[[Category:Collapse templates]]
[[Category: Machine Translated Page]]
[[Category:Created On 24/02/2023]]
[[Category:Created On 24/02/2023]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]

Latest revision as of 17:22, 3 March 2023

कंप्यूटर विज्ञान में, लिंक्ड डेटा संरचना एक डेटा संरचना है जिसमें एक साथ जुड़े डेटा रिकॉर्ड (कंप्यूटर विज्ञान) ("'नोड (कंप्यूटर विज्ञान)) का एक समूह होता है और संदर्भ (लिंक या पॉइंटर्स) द्वारा व्यवस्थित किया जाता है। डेटा के बीच के लिंक को योजक भी कहा जा सकता है।

लिंक की गई डेटा संरचनाओं में, लिंक को सामान्यतः विशेष डेटा प्रकार के रूप में माना जाता है जो केवल संदर्भ (कंप्यूटर विज्ञान) किया जा सकता है या समानता के लिए तुलना की जा सकती है। लिंक्ड डेटा संरचनाओं इस प्रकार सरणियों डेटा संरचना और अन्य डेटा संरचनाओं के विपरीत हैं, जिन्हें पॉइंटर्स पर अंकगणितीय ऑपरेशन करने की आवश्यकता होती है। यह अंतर तब भी होता है जब नोड्स वास्तविक में एकल सरणी के तत्वों के रूप में प्रायुक्त होते हैं, और संदर्भ वास्तविक में सरणी डेटा सूचकांक होते हैं: जब तक कि उन सूचकांकों पर कोई अंकगणित नहीं किया जाता है, तब तक डेटा संरचना अनिवार्य रूप से जुड़ा होता है।

डायनेमिक आवंटन का उपयोग करके और सरणी सूचकांक लिंकिंग का उपयोग करके लिंकिंग दो विधियों से की जा सकती है।

लिंक्ड डेटा संरचना में लिंक्ड सूची , सर्च ट्री , एक्सप्रेशन ट्री और कई अन्य व्यापक रूप से उपयोग किए जाने वाले डेटा संरचना सम्मिलित हैं। वे कई कुशल एल्गोरिदम, जैसे टोपोलॉजिकल सॉर्ट[1] और सेट यूनियन-फाइंड के लिए महत्वपूर्ण रचक खंड भी हैं।[2]


सामान्य प्रकार के लिंक्ड डेटा संरचनाओं

लिंक की गई सूचियां

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

लिंक्ड लिस्ट एकल, दोहरा या एकाधिक लिंक्ड हो सकती है और या तो रेखीय या वृत्तीय हो सकती है।

मूल गुण
  • वस्तुएं, जिन्हें नोड कहा जाता है, रेखीय क्रम में जुड़े होते हैं।
  • सूची के पहले नोड का संदर्भ हमेशा रखा जाता है। इसे 'सिर' या 'सामने' कहा जाता है।[3]

Singly-linked-list.svg
तीन नोड्स वाली एक लिंक्ड सूची में दो क्षेत्र होते हैं जिनमें से प्रत्येक एक पूर्णांक मान और अगले नोड के लिए एक लिंक होता है

नोड के साथ लिंक की गई सूची।

जावा में उदाहरण

यह लिंक की गई सूची के जावा कार्यान्वयन में पूर्णांकों को संग्रहीत करने के लिए उपयोग किए जाने वाले नोड वर्ग का उदाहरण है: 

public class IntNode {
     public int value;
     public IntNode link;
     public IntNode(int v) { value = v; }
}


सी में उदाहरण

यह सी में लिंक की गई सूची के कार्यान्वयन के लिए उपयोग की जाने वाली संरचना का उदाहरण है: 

struct node
{
	int val;
	struct node *next;
};

यह टाइपपीफ का उपयोग करने वाला उदाहरण है: 

typedef struct node node;

struct node
{
	int val;
	node *next;
};

नोट: इस तरह की संरचना जिसमें सदस्य होता है जो समान संरचना की ओर संकेत करता है, स्व-संदर्भित संरचना कहलाती है।

सी ++ में उदाहरण

यह सी++ में लिंक की गई सूची के कार्यान्वयन के लिए उपयोग की जाने वाली नोड वर्ग संरचना का उदाहरण है: 

class Node
{
	int val;
	Node *next;
};


पेड़ खोजें

सर्च ट्री एक ट्री डेटा संरचना है जिसके नोड्स में डेटा मान को कुछ आदिष्ट किए गए समूह से संचय किया जा सकता है, जो ऐसा है कि ट्री के क्रम में पथक्रमण में संचय किए गए मान के आरोही क्रम में नोड्स का दौरा किया जाता है।

बुनियादी गुण
  • वस्तुएं, जिन्हें नोड्स कहा जाता है, आदिष्ट किए गए समूह में संचय किए जाते हैं।
  • क्रम में पथक्रमण ट्री में डेटा का आरोही अनुशीर्षक प्रदान करता है।

लाभ और हानि

लिंक्ड सूची बनाम सरणियाँ

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

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

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

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

सामान्य हानि

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

सरणियों में, n वें तत्व को तुरंत एक्सेस किया जा सकता है, चूँकि लिंक्ड डेटा संरचना में हमें कई पॉइंटर्स का पालन करना पड़ता है, इसलिए तत्व का एक्सेस समय अलग-अलग होता है, जहां तत्व संरचना में होता है।

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

यह भी देखें

संदर्भ

  1. ↑ Donald Knuth, The Art of Computer Programming
  2. ↑ Bernard A. Galler and Michael J. Fischer. An improved equivalence algorithm. Communications of the ACM, Volume 7, Issue 5 (May 1964), pages 301–303. The paper originating disjoint-set forests. ACM Digital Library
  3. ↑ http://www.cs.toronto.edu/~hojjat/148s07/lectures/week5/07linked.pdf[bare URL PDF]
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=लिंक्ड_डेटा_संरचना&oldid=99878’