लिंक्ड डेटा संरचना

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

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

लिंकिंग दो तरह से की जा सकती है – डायनेमिक आवंटन का उपयोग करना और एरे इंडेक्स लिंकिंग का उपयोग करना।

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

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

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

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

लिंक्ड लिस्ट सिंगल, डबल या मल्टीप्ल लिंक्ड हो सकती है और या तो लीनियर या सर्कुलर हो सकती है।

मूल गुण

• ऑब्जेक्ट्स, जिन्हें नोड कहा जाता है, एक रेखीय क्रम में जुड़े होते हैं।
• सूची के पहले नोड का संदर्भ हमेशा रखा जाता है। इसे 'सिर' या 'सामने' कहा जाता है।

<डिव वर्ग = केंद्र>
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 वें तत्व को तुरंत एक्सेस किया जा सकता है, जबकि एक लिंक्ड डेटा स्ट्रक्चर में हमें कई पॉइंटर्स का पालन करना पड़ता है, इसलिए एलिमेंट का एक्सेस टाइम अलग-अलग होता है, जहां एलिमेंट संरचना में होता है।

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

यह भी देखें

• डेटा संरचनाओं की सूची