लिंक्ड डेटा संरचना: Difference between revisions
No edit summary |
No edit summary |
||
| 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> | ||
== सामान्य प्रकार के लिंक्ड डेटा | == सामान्य प्रकार के लिंक्ड डेटा संरचनाओं == | ||
===लिंक की गई सूचियां=== | ===लिंक की गई सूचियां=== | ||
| Line 73: | Line 73: | ||
=== पेड़ खोजें === | === पेड़ खोजें === | ||
सर्च ट्री ट्री डेटा | सर्च ट्री ट्री डेटा संरचना है जिसके नोड्स में डेटा वैल्यू को कुछ ऑर्डर किए गए समूह से स्टोर किया जा सकता है, जो ऐसा है कि ट्री के [[इन-ऑर्डर ट्रैवर्सल]] में स्टोर किए गए वैल्यू के आरोही क्रम में नोड्स का दौरा किया जाता है। | ||
; बुनियादी गुण | ; बुनियादी गुण | ||
* ऑब्जेक्ट्स, जिन्हें नोड्स कहा जाता है, ऑर्डर किए गए | * ऑब्जेक्ट्स, जिन्हें नोड्स कहा जाता है, ऑर्डर किए गए समूह में स्टोर किए जाते हैं। | ||
* इन-ऑर्डर ट्रैवर्सल ट्री में डेटा का आरोही रीडआउट प्रदान करता है। | * इन-ऑर्डर ट्रैवर्सल ट्री में डेटा का आरोही रीडआउट प्रदान करता है। | ||
| Line 89: | Line 89: | ||
दूसरी ओर, लिंक किए गए डेटा संरचना में किसी विशेष नोड तक पहुंच के लिए प्रत्येक नोड में संग्रहीत संदर्भों की श्रृंखला का पालन करना आवश्यक है। यदि संरचना में n नोड हैं, और प्रत्येक नोड में अधिकांश b लिंक हैं, तो कुछ ऐसे नोड होंगे जिन तक लॉग से कम में नहीं पहुँचा जा सकता है<sub>''b''</sub> n चरण, इन नोड्स तक पहुँचने की प्रक्रिया को धीमा करना - यह कभी-कभी काफी मंदी का प्रतिनिधित्व करता है, विशेष रूप से बड़ी संख्या में नोड्स वाली संरचनाओं के मामले में। कई संरचनाओं के लिए, कुछ नोड्स को n−1 चरणों तक सर्वोत्तम, सबसे खराब और औसत मामले की आवश्यकता हो सकती है। इसके विपरीत, कई सरणी डेटा संरचनाएं प्रविष्टियों की संख्या से स्वतंत्र संचालन की निरंतर संख्या के साथ किसी भी तत्व तक पहुंच की अनुमति देती हैं। | दूसरी ओर, लिंक किए गए डेटा संरचना में किसी विशेष नोड तक पहुंच के लिए प्रत्येक नोड में संग्रहीत संदर्भों की श्रृंखला का पालन करना आवश्यक है। यदि संरचना में n नोड हैं, और प्रत्येक नोड में अधिकांश b लिंक हैं, तो कुछ ऐसे नोड होंगे जिन तक लॉग से कम में नहीं पहुँचा जा सकता है<sub>''b''</sub> n चरण, इन नोड्स तक पहुँचने की प्रक्रिया को धीमा करना - यह कभी-कभी काफी मंदी का प्रतिनिधित्व करता है, विशेष रूप से बड़ी संख्या में नोड्स वाली संरचनाओं के मामले में। कई संरचनाओं के लिए, कुछ नोड्स को n−1 चरणों तक सर्वोत्तम, सबसे खराब और औसत मामले की आवश्यकता हो सकती है। इसके विपरीत, कई सरणी डेटा संरचनाएं प्रविष्टियों की संख्या से स्वतंत्र संचालन की निरंतर संख्या के साथ किसी भी तत्व तक पहुंच की अनुमति देती हैं। | ||
मोटे तौर पर इन लिंक्ड डेटा | मोटे तौर पर इन लिंक्ड डेटा संरचना का कार्यान्वयन [[गतिशील डेटा संरचनाएं]] के माध्यम से होता है। यह हमें फिर से विशेष स्थान का उपयोग करने का मौका देता है। इन डेटा संरचनाओं का उपयोग करके मेमोरी का अधिक कुशलता से उपयोग किया जा सकता है। मेमोरी को जरूरत के हिसाब से आवंटित किया जाता है और जब मेमोरी की और जरूरत नहीं होती है, तो डीलोकेशन किया जाता है। | ||
=== सामान्य नुकसान === | === सामान्य नुकसान === | ||
लिंक्ड डेटा संरचनाएं पर्याप्त गतिशील मेमोरी आवंटन ओवरहेड (यदि नोड्स व्यक्तिगत रूप से आवंटित की जाती हैं) और [[ आभासी मेमोरी ]] और [[कैश (कंप्यूटिंग)]] एल्गोरिदम को निराश कर सकती हैं (क्योंकि उनके पास | लिंक्ड डेटा संरचनाएं पर्याप्त गतिशील मेमोरी आवंटन ओवरहेड (यदि नोड्स व्यक्तिगत रूप से आवंटित की जाती हैं) और [[ आभासी मेमोरी ]] और [[कैश (कंप्यूटिंग)]] एल्गोरिदम को निराश कर सकती हैं (क्योंकि उनके पास सामान्यतः संदर्भ की खराब इलाके होती है)। कुछ मामलों में, लिंक्ड डेटा संरचना प्रतिस्पर्धी सरणी संरचनाओं की तुलना में अधिक मेमोरी (लिंक फ़ील्ड के लिए) का उपयोग कर सकते हैं। ऐसा इसलिए है क्योंकि लिंक की गई डेटा संरचनाएँ सन्निहित नहीं हैं। सरणियों के विपरीत, डेटा के उदाहरण पूरे मेमोरी में पाए जा सकते हैं। | ||
सरणियों में, n वें तत्व को तुरंत एक्सेस किया जा सकता है, जबकि लिंक्ड डेटा | सरणियों में, n वें तत्व को तुरंत एक्सेस किया जा सकता है, जबकि लिंक्ड डेटा संरचना में हमें कई पॉइंटर्स का पालन करना पड़ता है, इसलिए एलिमेंट का एक्सेस टाइम अलग-अलग होता है, जहां एलिमेंट संरचना में होता है। | ||
कुछ [[सैद्धांतिक कंप्यूटर विज्ञान]] में जो लिंक्ड संरचनाओं की बाधाओं को लागू करते हैं, जैसे कि [[ सूचक मशीन ]], कई समस्याओं के लिए अनियंत्रित [[रैंडम एक्सेस मशीन]] मॉडल की तुलना में अधिक चरणों की आवश्यकता होती है। | कुछ [[सैद्धांतिक कंप्यूटर विज्ञान]] में जो लिंक्ड संरचनाओं की बाधाओं को लागू करते हैं, जैसे कि [[ सूचक मशीन ]], कई समस्याओं के लिए अनियंत्रित [[रैंडम एक्सेस मशीन]] मॉडल की तुलना में अधिक चरणों की आवश्यकता होती है। | ||
Revision as of 13:21, 28 February 2023
कंप्यूटर विज्ञान में, लिंक्ड डेटा संरचना एक डेटा संरचना है जिसमें एक साथ जुड़े डेटा रिकॉर्ड (कंप्यूटर विज्ञान) ("'नोड (कंप्यूटर विज्ञान)) का एक समूह होता है और संदर्भ (लिंक या पॉइंटर्स) द्वारा व्यवस्थित किया जाता है। डेटा के बीच के लिंक को योजक भी कहा जा सकता है।
लिंक की गई डेटा संरचनाओं में, लिंक को सामान्यतः विशेष डेटा प्रकार के रूप में माना जाता है जो केवल संदर्भ (कंप्यूटर विज्ञान) किया जा सकता है या समानता के लिए तुलना की जा सकती है। लिंक्ड डेटा संरचनाओं इस प्रकार सरणियों डेटा संरचना और अन्य डेटा संरचनाओं के विपरीत हैं, जिन्हें पॉइंटर्स पर अंकगणितीय ऑपरेशन करने की आवश्यकता होती है। यह अंतर तब भी होता है जब नोड्स वास्तव में एकल सरणी के तत्वों के रूप में प्रायुक्त होते हैं, और संदर्भ वास्तविक में सरणी डेटा सूचकांक होते हैं: जब तक कि उन सूचकांकों पर कोई अंकगणित नहीं किया जाता है, तब तक डेटा संरचना अनिवार्य रूप से जुड़ा होता है।
डायनेमिक आवंटन का उपयोग करके और सरणी सूचकांक लिंकिंग का उपयोग करके लिंकिंग दो विधियों से की जा सकती है।
लिंक्ड डेटा संरचना में लिंक्ड सूची , सर्च ट्री , एक्सप्रेशन ट्री और कई अन्य व्यापक रूप से उपयोग किए जाने वाले डेटा संरचना सम्मिलित हैं। वे कई कुशल एल्गोरिदम, जैसे टोपोलॉजिकल सॉर्ट[1] और सेट यूनियन-फाइंड के लिए महत्वपूर्ण बिल्डिंग ब्लॉक भी हैं।[2]
सामान्य प्रकार के लिंक्ड डेटा संरचनाओं
लिंक की गई सूचियां
लिंक की गई सूची संरचनाओं का संग्रह है जो स्मृति में उनके भौतिक प्लेसमेंट द्वारा नहीं बल्कि संरचना में डेटा के हिस्से के रूप में संग्रहीत तार्किक लिंक द्वारा आदेशित है। यह आवश्यक नहीं है कि इसे सन्निकट स्मृति स्थानों में संग्रहित किया जाए। प्रत्येक संरचना में डेटा फ़ील्ड और पता फ़ील्ड होता है। पता फ़ील्ड में इसके उत्तराधिकारी (ग्राफ़ सिद्धांत) का पता होता है।
लिंक्ड लिस्ट सिंगल, डबल या मल्टीप्ल लिंक्ड हो सकती है और या तो लीनियर या सर्कुलर हो सकती है।
- मूल गुण
- ऑब्जेक्ट्स, जिन्हें नोड कहा जाता है, रेखीय क्रम में जुड़े होते हैं।
- सूची के पहले नोड का संदर्भ हमेशा रखा जाता है। इसे 'सिर' या 'सामने' कहा जाता है।[3]
<डिव वर्ग = केंद्र>
A linked list with three nodes contain two fields each: an integer value and a link to the next node
जावा में उदाहरण
यह लिंक की गई सूची के जावा कार्यान्वयन में पूर्णांकों को संग्रहीत करने के लिए उपयोग किए जाने वाले नोड वर्ग का उदाहरण है:
public class IntNode {
public int value;
public IntNode link;
public IntNode(int v) { value = v; }
}
==== सी ==== में उदाहरण
यह C में लिंक की गई सूची के कार्यान्वयन के लिए उपयोग की जाने वाली संरचना का उदाहरण है:
struct node
{
int val;
struct node *next;
};
यह टाइपपीफ का उपयोग करने वाला उदाहरण है:
typedef struct node node;
struct node
{
int val;
node *next;
};
नोट: इस तरह की संरचना जिसमें सदस्य होता है जो समान संरचना की ओर इशारा करता है, स्व-संदर्भित संरचना कहलाती है।
==== सी ++ ==== में उदाहरण यह C++ में लिंक की गई सूची के कार्यान्वयन के लिए उपयोग की जाने वाली नोड वर्ग संरचना का उदाहरण है:
class Node
{
int val;
Node *next;
};
पेड़ खोजें
सर्च ट्री ट्री डेटा संरचना है जिसके नोड्स में डेटा वैल्यू को कुछ ऑर्डर किए गए समूह से स्टोर किया जा सकता है, जो ऐसा है कि ट्री के इन-ऑर्डर ट्रैवर्सल में स्टोर किए गए वैल्यू के आरोही क्रम में नोड्स का दौरा किया जाता है।
- बुनियादी गुण
- ऑब्जेक्ट्स, जिन्हें नोड्स कहा जाता है, ऑर्डर किए गए समूह में स्टोर किए जाते हैं।
- इन-ऑर्डर ट्रैवर्सल ट्री में डेटा का आरोही रीडआउट प्रदान करता है।
फायदे और नुकसान
लिंक्ड सूची बनाम सरणियाँ
सरणियों की तुलना में, लिंक्ड डेटा संरचनाएँ डेटा को व्यवस्थित करने और इसके लिए स्थान आवंटित करने में अधिक लचीलेपन की अनुमति देती हैं। सरणियों में, सरणी के आकार को शुरुआत में सटीक रूप से निर्दिष्ट किया जाना चाहिए, जो स्मृति की संभावित बर्बादी हो सकती है, या मनमाना सीमा हो सकती है जो बाद में किसी तरह से कार्यक्षमता को बाधित करेगी। लिंक की गई डेटा संरचना गतिशील रूप से बनाई गई है और इसे कभी भी प्रोग्राम की आवश्यकता से बड़ा नहीं होना चाहिए। कितनी जगह आवंटित की जानी चाहिए, इसके संदर्भ में इसे निर्माण समय पर अनुमान लगाने की भी आवश्यकता नहीं है। यह ऐसी विशेषता है जो स्मृति के अपव्यय से बचने के लिए महत्वपूर्ण है।
सरणी में, सरणी तत्वों को मेमोरी के कॉन्टिगुटी (कंप्यूटर विज्ञान) (जुड़े और अनुक्रमिक) भाग में होना चाहिए। लेकिन लिंक्ड डेटा संरचना में, प्रत्येक नोड का संदर्भ उपयोगकर्ताओं को अगले को खोजने के लिए आवश्यक जानकारी देता है। सरणियों के विपरीत, लिंक्ड डेटा संरचना के नोड्स को उनके बीच तार्किक कनेक्शन को प्रभावित किए बिना व्यक्तिगत रूप से भौतिक मेमोरी के भीतर अलग-अलग स्थानों पर ले जाया जा सकता है। उचित देखभाल के साथ, निश्चित प्रक्रिया (कंप्यूटिंग) या थ्रेड (कंप्यूटिंग) डेटा संरचना के हिस्से में नोड्स को जोड़ या हटा सकता है, जबकि अन्य प्रक्रियाएं या थ्रेड्स अन्य भागों पर काम कर रहे हैं।
दूसरी ओर, लिंक किए गए डेटा संरचना में किसी विशेष नोड तक पहुंच के लिए प्रत्येक नोड में संग्रहीत संदर्भों की श्रृंखला का पालन करना आवश्यक है। यदि संरचना में n नोड हैं, और प्रत्येक नोड में अधिकांश b लिंक हैं, तो कुछ ऐसे नोड होंगे जिन तक लॉग से कम में नहीं पहुँचा जा सकता हैb 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]
