सरणी का उपयोग करके लिंक्ड सूची लागू करें - फायदे और नुकसान

Question

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

struct Node{ 
    int data; 
    int link; 
} 

"डाटा" भंडार की जानकारी और अगले नोड के सरणी में "लिंक" भंडार सूचकांक।

क्या कोई मुझे बता सकता है कि "सामान्य" लिंक्ड सूची की तुलना में सरणी का उपयोग करके एक लिंक्ड सूची को कार्यान्वित करने का लाभ और नुकसान क्या है? सभी सुझावों का स्वागत है।

Answer 1

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

कुछ तत्काल नुकसान:

1. आप सरणी में मृत स्थान होगा (प्रविष्टियों जो वर्तमान में आइटम के लिए इस्तेमाल नहीं कर रहे हैं) स्मृति
2. लेने आप मुफ्त का ट्रैक रखने करना होगा प्रविष्टियां - कुछ प्रविष्टियों और हटाने के बाद, ये निःशुल्क प्रविष्टियां कहीं भी हो सकती हैं।
3. एक सरणी का उपयोग लिंक की गई सूची के आकार पर ऊपरी सीमा लगाएगा।

मुझे लगता है कुछ फायदे हैं:

1. आप एक 64 बिट सिस्टम पर हैं, तो अपने "संकेत" ऊपर कम जगह ले जाएगा (हालांकि अतिरिक्त स्थान मुक्त प्रविष्टियों के लिए आवश्यक शायद यह लाभ outweighs)
2. आप सरणी को डिस्क पर क्रमबद्ध कर सकते हैं और आसानी से mmap() कॉल के साथ इसे वापस पढ़ सकते हैं। हालांकि, आप पोर्टेबिलिटी के लिए कुछ प्रकार के प्रोटोकॉल बफर का उपयोग करना बेहतर होगा।
3. आप सरणी में तत्वों के बारे में कुछ गारंटी दे सकते हैं स्मृति में एक-दूसरे के करीब।

Answer 2

किसी को भी मुझे बता सकते हैं क्या लाभ और सरणी का उपयोग कर लिंक्ड सूची के कार्यान्वयन के नुकसान है "साधारण" लिंक्ड सूची की तुलना में?

जुड़ा हुआ सूचियों निम्नलिखित जटिलता है:

• विपक्ष एक्स XS: हे (1)
• संलग्न एनएम: हे (एन)
• सूचकांक मैं XS: हे (एन)

यदि आपका प्रतिनिधि ntation एक सख्त, सन्निहित सरणी का उपयोग करता है, तो आप विभिन्न जटिलता होगा:

• विपक्ष वर्ष सरणी को कॉपी की आवश्यकता होगी: हे (एन)
• संलग्न एक नया सन्निहित अंतरिक्ष में दोनों सरणियों को कॉपी की आवश्यकता होगी: ओ (n + m)
• सूचकांक सरणी का उपयोग के रूप में लागू किया जा सकता: हे (1)

यही है, एक लिंक्ड सूची अवधि में लागू एपीआई सरणी के सर एक सरणी की तरह व्यवहार करेंगे।

आप एक लिंक्ड सूची या सख्त सरणी के पेड़ का उपयोग कर कुछ हद तक कम कर सकते हैं, जिससे रस्सी या उंगली के पेड़ या आलसी दृश्य होते हैं।

Answer 3

दो तरीकों से लागू करने में ढेर। पहले सरणी का उपयोग करने में और दूसरा लिंक की गई सूची का उपयोग कर रहा है।

सरणी का उपयोग करने में कुछ नुकसान तब प्रोग्रामर का अधिकांश स्टैक कार्यान्वयन में लिंक्ड सूची का उपयोग करें।

पहले लिंक की गई सूची का उपयोग करके ढेर है, पहले स्टैक आकार की घोषणा न करें और स्टैक में सीमित डेटा स्टोर न करें। दूसरा घोषित करने और इसका उपयोग करने के लिए सूचक निबंध में लिंक्ड सूची है।

लिंक की गई सूची में केवल एक सूचक उपयोग। इसे शीर्ष सूचक कहा जाता है।

ढेर लाइफ विधि उपयोग है। लेकिन लिंक्ड सूची कार्यक्रम कार्यान्वयन में कुछ नुकसान।

अधिकांश प्रोग्रामर पसंद की गई सूची का उपयोग करके स्टैक कार्यान्वयन का उपयोग करते हैं।

Answer 4

सरणी कार्यान्वयन का उपयोग करना, आप सूची का नोड्स अनुक्रमिक & तेज पहुँच दूसरे हाथ पर, हो सकता है, आप संकेत का उपयोग कर लिंक्ड सूची को लागू हैं, तो आप नोड्स रैंडम एक्सेस कर सकते हैं। जब आप निश्चित संख्या से निपट रहे हैं तो ऐरे कार्यान्वयन सहायक होता है। तत्वों में से एक सरणी का आकार बदलना महंगा है, जहां तक ​​प्रदर्शन का संबंध है क्योंकि यदि आपको सूची के मध्य से नोड्स डालने/हटाने की आवश्यकता है तो आपको प्रत्येक नोड को बाद में बदलना होगा। इसके विपरीत, आपको पॉइंटर कार्यान्वयन का उपयोग करना चाहिए जब आप नहीं जानते हैं। उन नोड्स के बारे में जिन्हें आप चाहते हैं, क्योंकि ऐसी सूची कुशलता से बढ़ सकती है/घटा सकती है & आपको किसी भी नोड्स को स्थानांतरित करने की आवश्यकता नहीं है, इसे & रेफरेंसिंग पॉइंटर्स को बस संदर्भित करके किया जा सकता है।