लिंक्ड डेटा संरचना: Difference between revisions
No edit summary |
No edit summary |
||
| Line 36: | Line 36: | ||
यह | '''सी में उदाहरण''' | ||
यह सी में लिंक की गई सूची के कार्यान्वयन के लिए उपयोग की जाने वाली संरचना का उदाहरण है: | |||
<syntaxhighlight lang=c> | <syntaxhighlight lang=c> | ||
| Line 60: | Line 62: | ||
नोट: इस तरह की संरचना जिसमें सदस्य होता है जो समान संरचना की ओर इशारा करता है, स्व-संदर्भित संरचना कहलाती है। | नोट: इस तरह की संरचना जिसमें सदस्य होता है जो समान संरचना की ओर इशारा करता है, स्व-संदर्भित संरचना कहलाती है। | ||
'''सी ++ में उदाहरण''' | |||
यह | |||
यह सी++ में लिंक की गई सूची के कार्यान्वयन के लिए उपयोग की जाने वाली नोड वर्ग संरचना का उदाहरण है: | |||
<syntaxhighlight lang=cpp> | <syntaxhighlight lang=cpp> | ||
| Line 73: | Line 76: | ||
=== पेड़ खोजें === | === पेड़ खोजें === | ||
सर्च ट्री ट्री डेटा संरचना है जिसके नोड्स में डेटा | सर्च ट्री एक ट्री डेटा संरचना है जिसके नोड्स में डेटा मान को कुछ आदिष्ट किए गए समूह से संचय किया जा सकता है, जो ऐसा है कि ट्री के [[इन-ऑर्डर ट्रैवर्सल|क्रम में पथक्रमण]] में संचय किए गए मान के आरोही क्रम में नोड्स का दौरा किया जाता है। | ||
; बुनियादी गुण | ; बुनियादी गुण | ||
* वस्तुएं, जिन्हें नोड्स कहा जाता है, | * वस्तुएं, जिन्हें नोड्स कहा जाता है, आदिष्ट किए गए समूह में संचय किए जाते हैं। | ||
* | * क्रम में पथक्रमण ट्री में डेटा का आरोही अनुशीर्षक प्रदान करता है। | ||
== | == लाभ और हानि == | ||
=== लिंक्ड सूची बनाम सरणियाँ === | === लिंक्ड सूची बनाम सरणियाँ === | ||
सरणियों की तुलना में, लिंक्ड डेटा संरचनाएँ डेटा को व्यवस्थित करने और इसके लिए स्थान आवंटित करने में अधिक लचीलेपन की अनुमति देती हैं। सरणियों में, सरणी के आकार को शुरुआत में सटीक रूप से निर्दिष्ट किया जाना चाहिए, जो स्मृति की संभावित बर्बादी हो सकती है, या मनमाना सीमा हो सकती है जो बाद में किसी तरह से कार्यक्षमता को बाधित करेगी। लिंक की गई डेटा संरचना गतिशील रूप से बनाई गई है और इसे कभी भी प्रोग्राम की आवश्यकता से बड़ा नहीं होना चाहिए। कितनी जगह आवंटित की जानी चाहिए, इसके संदर्भ में इसे निर्माण समय पर अनुमान लगाने की भी आवश्यकता नहीं है। यह ऐसी विशेषता है जो स्मृति के अपव्यय से बचने के लिए महत्वपूर्ण है। | सरणियों की तुलना में, लिंक्ड डेटा संरचनाएँ डेटा को व्यवस्थित करने और इसके लिए स्थान आवंटित करने में अधिक लचीलेपन की अनुमति देती हैं। सरणियों में, सरणी के आकार को शुरुआत में सटीक रूप से निर्दिष्ट किया जाना चाहिए, जो स्मृति की संभावित बर्बादी हो सकती है, या मनमाना सीमा हो सकती है जो बाद में किसी तरह से कार्यक्षमता को बाधित करेगी। लिंक की गई डेटा संरचना गतिशील रूप से बनाई गई है और इसे कभी भी प्रोग्राम की आवश्यकता से बड़ा नहीं होना चाहिए। कितनी जगह आवंटित की जानी चाहिए, इसके संदर्भ में इसे निर्माण समय पर अनुमान लगाने की भी आवश्यकता नहीं है। यह ऐसी विशेषता है जो स्मृति के अपव्यय से बचने के लिए महत्वपूर्ण है। | ||
सरणी में, सरणी तत्वों को मेमोरी के कॉन्टिगुटी (कंप्यूटर विज्ञान) (जुड़े और अनुक्रमिक) भाग में होना चाहिए। लेकिन लिंक्ड डेटा संरचना में, प्रत्येक नोड का संदर्भ उपयोगकर्ताओं को अगले को खोजने के लिए आवश्यक जानकारी देता है। सरणियों के विपरीत, लिंक्ड डेटा संरचना के नोड्स को उनके बीच तार्किक कनेक्शन को प्रभावित किए बिना व्यक्तिगत रूप से भौतिक मेमोरी के भीतर अलग-अलग स्थानों पर ले जाया जा सकता है। उचित देखभाल के साथ, निश्चित [[प्रक्रिया (कंप्यूटिंग)]] या [[थ्रेड (कंप्यूटिंग)]] डेटा संरचना के हिस्से में नोड्स को जोड़ या हटा सकता है, | सरणी में, सरणी तत्वों को मेमोरी के कॉन्टिगुटी (कंप्यूटर विज्ञान) (जुड़े और अनुक्रमिक) भाग में होना चाहिए। लेकिन लिंक्ड डेटा संरचना में, प्रत्येक नोड का संदर्भ उपयोगकर्ताओं को अगले को खोजने के लिए आवश्यक जानकारी देता है। सरणियों के विपरीत, लिंक्ड डेटा संरचना के नोड्स को उनके बीच तार्किक कनेक्शन को प्रभावित किए बिना व्यक्तिगत रूप से भौतिक मेमोरी के भीतर अलग-अलग स्थानों पर ले जाया जा सकता है। उचित देखभाल के साथ, निश्चित [[प्रक्रिया (कंप्यूटिंग)]] या [[थ्रेड (कंप्यूटिंग)]] डेटा संरचना के हिस्से में नोड्स को जोड़ या हटा सकता है, चूँकि अन्य प्रक्रियाएं या थ्रेड्स अन्य भागों पर काम कर रहे हैं। | ||
दूसरी ओर, लिंक किए गए डेटा संरचना में किसी विशेष नोड तक पहुंच के लिए प्रत्येक नोड में संग्रहीत संदर्भों की श्रृंखला का पालन करना आवश्यक है। यदि संरचना में n नोड हैं, और प्रत्येक नोड में अधिकांश b लिंक हैं, तो कुछ ऐसे नोड होंगे जिन तक | दूसरी ओर, लिंक किए गए डेटा संरचना में किसी विशेष नोड तक पहुंच के लिए प्रत्येक नोड में संग्रहीत संदर्भों की श्रृंखला का पालन करना आवश्यक है। यदि संरचना में n नोड हैं, और प्रत्येक नोड में अधिकांश b लिंक हैं, तो कुछ ऐसे नोड होंगे जिन तक log<sub>''b''</sub> n चरण से कम में नहीं पहुँचा जा सकता है, इन नोड्स तक पहुँचने की प्रक्रिया को धीमा करना - यह कभी-कभी काफी मंदी का प्रतिनिधित्व करता है, विशेष रूप से बड़ी संख्या में नोड्स वाली संरचनाओं के मामले में। कई संरचनाओं के लिए, कुछ नोड्स को n−1 चरणों तक सर्वोत्तम, सबसे खराब और औसत मामले की आवश्यकता हो सकती है। इसके विपरीत, कई सरणी डेटा संरचनाएं प्रविष्टियों की संख्या से स्वतंत्र संचालन की निरंतर संख्या के साथ किसी भी तत्व तक पहुंच की अनुमति देती हैं। | ||
सामान्यतः इन लिंक्ड डेटा संरचना का कार्यान्वयन [[गतिशील डेटा संरचनाएं]] के माध्यम से होता है। यह हमें फिर से विशेष स्थान का उपयोग करने का मौका देता है। इन डेटा संरचनाओं का उपयोग करके मेमोरी का अधिक कुशलता से उपयोग किया जा सकता है। मेमोरी को आवश्कता के गणना से आवंटित किया जाता है और जब मेमोरी की और आवश्कता नहीं होती है, तो डीलोकेशन किया जाता है। | |||
=== सामान्य | === सामान्य हानि === | ||
लिंक्ड डेटा संरचनाएं पर्याप्त गतिशील मेमोरी आवंटन ओवरहेड (यदि नोड्स व्यक्तिगत रूप से आवंटित की जाती हैं) और [[ आभासी मेमोरी ]] और [[कैश (कंप्यूटिंग)]] एल्गोरिदम को निराश कर सकती हैं (क्योंकि उनके पास सामान्यतः संदर्भ की खराब इलाके होती है)। कुछ मामलों में, लिंक्ड डेटा संरचना प्रतिस्पर्धी सरणी संरचनाओं की तुलना में अधिक मेमोरी (लिंक फ़ील्ड के लिए) का उपयोग कर सकते हैं। ऐसा इसलिए है क्योंकि लिंक की गई डेटा संरचनाएँ सन्निहित नहीं हैं। सरणियों के विपरीत, डेटा के उदाहरण पूरे मेमोरी में पाए जा सकते हैं। | लिंक्ड डेटा संरचनाएं पर्याप्त गतिशील मेमोरी आवंटन ओवरहेड (यदि नोड्स व्यक्तिगत रूप से आवंटित की जाती हैं) और [[ आभासी मेमोरी ]] और [[कैश (कंप्यूटिंग)]] एल्गोरिदम को निराश कर सकती हैं (क्योंकि उनके पास सामान्यतः संदर्भ की खराब इलाके होती है)। कुछ मामलों में, लिंक्ड डेटा संरचना प्रतिस्पर्धी सरणी संरचनाओं की तुलना में अधिक मेमोरी (लिंक फ़ील्ड के लिए) का उपयोग कर सकते हैं। ऐसा इसलिए है क्योंकि लिंक की गई डेटा संरचनाएँ सन्निहित नहीं हैं। सरणियों के विपरीत, डेटा के उदाहरण पूरे मेमोरी में पाए जा सकते हैं। | ||
सरणियों में, n वें तत्व को तुरंत एक्सेस किया जा सकता है, | सरणियों में, n वें तत्व को तुरंत एक्सेस किया जा सकता है, चूँकि लिंक्ड डेटा संरचना में हमें कई पॉइंटर्स का पालन करना पड़ता है, इसलिए एलिमेंट का एक्सेस टाइम अलग-अलग होता है, जहां एलिमेंट संरचना में होता है। | ||
कुछ [[सैद्धांतिक कंप्यूटर विज्ञान]] में जो लिंक्ड संरचनाओं की बाधाओं को लागू करते हैं, जैसे कि [[ सूचक मशीन ]], कई समस्याओं के लिए अनियंत्रित [[रैंडम एक्सेस मशीन]] मॉडल की तुलना में अधिक चरणों की आवश्यकता होती है। | कुछ [[सैद्धांतिक कंप्यूटर विज्ञान]] में जो लिंक्ड संरचनाओं की बाधाओं को लागू करते हैं, जैसे कि [[ सूचक मशीन ]], कई समस्याओं के लिए अनियंत्रित [[रैंडम एक्सेस मशीन]] मॉडल की तुलना में अधिक चरणों की आवश्यकता होती है। | ||
Revision as of 13:40, 28 February 2023
कंप्यूटर विज्ञान में, लिंक्ड डेटा संरचना एक डेटा संरचना है जिसमें एक साथ जुड़े डेटा रिकॉर्ड (कंप्यूटर विज्ञान) ("'नोड (कंप्यूटर विज्ञान)) का एक समूह होता है और संदर्भ (लिंक या पॉइंटर्स) द्वारा व्यवस्थित किया जाता है। डेटा के बीच के लिंक को योजक भी कहा जा सकता है।
लिंक की गई डेटा संरचनाओं में, लिंक को सामान्यतः विशेष डेटा प्रकार के रूप में माना जाता है जो केवल संदर्भ (कंप्यूटर विज्ञान) किया जा सकता है या समानता के लिए तुलना की जा सकती है। लिंक्ड डेटा संरचनाओं इस प्रकार सरणियों डेटा संरचना और अन्य डेटा संरचनाओं के विपरीत हैं, जिन्हें पॉइंटर्स पर अंकगणितीय ऑपरेशन करने की आवश्यकता होती है। यह अंतर तब भी होता है जब नोड्स वास्तव में एकल सरणी के तत्वों के रूप में प्रायुक्त होते हैं, और संदर्भ वास्तविक में सरणी डेटा सूचकांक होते हैं: जब तक कि उन सूचकांकों पर कोई अंकगणित नहीं किया जाता है, तब तक डेटा संरचना अनिवार्य रूप से जुड़ा होता है।
डायनेमिक आवंटन का उपयोग करके और सरणी सूचकांक लिंकिंग का उपयोग करके लिंकिंग दो विधियों से की जा सकती है।
लिंक्ड डेटा संरचना में लिंक्ड सूची , सर्च ट्री , एक्सप्रेशन ट्री और कई अन्य व्यापक रूप से उपयोग किए जाने वाले डेटा संरचना सम्मिलित हैं। वे कई कुशल एल्गोरिदम, जैसे टोपोलॉजिकल सॉर्ट[1] और सेट यूनियन-फाइंड के लिए महत्वपूर्ण बिल्डिंग ब्लॉक भी हैं।[2]
सामान्य प्रकार के लिंक्ड डेटा संरचनाओं
लिंक की गई सूचियां
लिंक की गई सूची संरचनाओं का एक संग्रह है जो स्मृति में उनके भौतिक प्लेसमेंट द्वारा नहीं किन्तु संरचना में डेटा के भाग के रूप में संग्रहीत तार्किक लिंक द्वारा आदेशित है। यह आवश्यक नहीं है कि इसे सन्निकट स्मृति स्थानों में संग्रहित किया जाए। प्रत्येक संरचना में डेटा फ़ील्ड और पता फ़ील्ड होता है। पता फ़ील्ड में इसके उत्तराधिकारी (ग्राफ़ सिद्धांत) का पता होता है।
लिंक्ड लिस्ट एकल, दोहरा या एकाधिक लिंक्ड हो सकती है और या तो रेखीय या वृत्तीय हो सकती है।
- मूल गुण
- वस्तुएं, जिन्हें नोड कहा जाता है, रेखीय क्रम में जुड़े होते हैं।
- सूची के पहले नोड का संदर्भ हमेशा रखा जाता है। इसे 'सिर' या 'सामने' कहा जाता है।[3]
तीन नोड्स वाली एक लिंक्ड सूची में दो फ़ील्ड होते हैं जिनमें से प्रत्येक एक पूर्णांक मान और अगले नोड के लिए एक लिंक होता है
जावा में उदाहरण
यह लिंक की गई सूची के जावा कार्यान्वयन में पूर्णांकों को संग्रहीत करने के लिए उपयोग किए जाने वाले नोड वर्ग का उदाहरण है:
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 वें तत्व को तुरंत एक्सेस किया जा सकता है, चूँकि लिंक्ड डेटा संरचना में हमें कई पॉइंटर्स का पालन करना पड़ता है, इसलिए एलिमेंट का एक्सेस टाइम अलग-अलग होता है, जहां एलिमेंट संरचना में होता है।
कुछ सैद्धांतिक कंप्यूटर विज्ञान में जो लिंक्ड संरचनाओं की बाधाओं को लागू करते हैं, जैसे कि सूचक मशीन , कई समस्याओं के लिए अनियंत्रित रैंडम एक्सेस मशीन मॉडल की तुलना में अधिक चरणों की आवश्यकता होती है।
यह भी देखें
संदर्भ
- ↑ Donald Knuth, The Art of Computer Programming
- ↑ 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
- ↑ http://www.cs.toronto.edu/~hojjat/148s07/lectures/week5/07linked.pdf[bare URL PDF]
