एरे और लिंक्ड लिस्ट
एरे और लिंक्ड लिस्ट तत्वों के एक क्रमबद्ध अनुक्रम को संग्रहीत करने के दो मूल तरीके हैं: एरे उन्हें निरंतर मेमोरी में रखते हैं ताकि स्थिर-समय अनुक्रमित पहुँच मिल सके, जबकि लिंक्ड लिस्ट उन्हें पॉइंटर के माध्यम से जोड़ते हैं ताकि सस्ते सम्मिलन और विलोपन हो सके।
Definition
एक एरे तत्वों को स्थिति द्वारा अनुक्रमित निरंतर मेमोरी स्थानों में संग्रहीत करता है, जिससे स्थिर-समय यादृच्छिक पहुँच की अनुमति मिलती है; एक लिंक्ड लिस्ट तत्वों को अलग-अलग नोड्स में संग्रहीत करती है, प्रत्येक में अगले (और संभवतः पिछले) नोड का संदर्भ होता है, जिससे नोड संदर्भ दिए जाने पर स्थिर-समय सम्मिलन या हटाना संभव होता है।
Scope
यह विषय रैखिक, अनुक्रम-आधारित संरचनाओं और उन पर निर्मित अमूर्त डेटा प्रकारों को शामिल करता है — स्थैतिक और गतिशील एरे, एकल और दोहरी लिंक्ड लिस्ट, और स्टैक और क्यू ADT। यह उनकी पहुँच, सम्मिलन और विलोपन लागतों की तुलना करता है, गतिशील-एरे के आकार बदलने और उसके परिशोधित विश्लेषण को शामिल करता है, और मेमोरी-लेआउट के परिणामों जैसे कैश लोकैलिटी की व्याख्या करता है। इसमें हैश टेबल और सर्च ट्री के तहत कवर की गई सहयोगी और पदानुक्रमित संरचनाएं शामिल नहीं हैं।
Core questions
- निरंतर (एरे) भंडारण पॉइंटर-लिंक्ड (लिस्ट) भंडारण से बेहतर प्रदर्शन कब करता है?
- एक गतिशील एरे कभी-कभी आकार बदलने के बावजूद परिशोधित स्थिर-समय अपेंड कैसे प्राप्त करता है?
- सम्मिलन, विलोपन और पहुँच के लिए एरे बनाम लिंक्ड लिस्ट की लागत में क्या अंतर हैं?
- इन संरचनाओं के शीर्ष पर स्टैक और क्यू कैसे लागू किए जाते हैं?
- कैश व्यवहार के माध्यम से मेमोरी लेआउट वास्तविक दुनिया के प्रदर्शन को कैसे प्रभावित करता है?
Key concepts
- निरंतर मेमोरी
- अनुक्रमित पहुँच
- गतिशील एरे का आकार बदलना
- एकल और दोहरी लिंक्ड लिस्ट
- स्टैक (LIFO)
- क्यू (FIFO)
- परिशोधित लागत
- कैश लोकैलिटी
Key theories
- यादृच्छिक पहुँच बनाम अनुक्रमिक लिंकेज
- एरे O(1) अनुक्रमित पहुँच का समर्थन करते हैं लेकिन बीच में O(n) सम्मिलन या विलोपन का, जबकि लिंक्ड लिस्ट एक नोड दिए जाने पर O(1) स्प्लिसिंग का समर्थन करते हैं लेकिन स्थिति के अनुसार O(n) पहुँच का; सही चुनाव ऑपरेशन मिश्रण पर निर्भर करता है।
- गतिशील एरे का परिशोधित विकास
- एक गतिशील एरे जो पूर्ण होने पर अपनी क्षमता को दोगुना कर देता है, कभी-कभी O(n) प्रतियां करता है लेकिन किसी भी ऑपरेशन के अनुक्रम पर प्रति अपेंड O(1) तक परिशोधित होता है, कुल या संभावित विधि द्वारा।
Clinical relevance
एरे और लिस्ट लगभग हर प्रोग्राम का आधार हैं: गतिशील एरे अधिकांश भाषाओं में डिफ़ॉल्ट लिस्ट/वेक्टर प्रकारों को लागू करते हैं, क्यू शेड्यूलिंग और ब्रेथ-फर्स्ट सर्च का आधार हैं, स्टैक फ़ंक्शन-कॉल प्रबंधन और अभिव्यक्ति मूल्यांकन का आधार हैं, और एरे-बनाम-लिस्ट ट्रेड-ऑफ प्रदर्शन को प्रभावित करने वाला एक नियमित व्यावहारिक डिज़ाइन निर्णय है।
History
एरे सबसे शुरुआती डेटा संरचनाओं में से हैं, जो पहली प्रोग्रामिंग भाषाओं में मौजूद थे, और लिंक्ड लिस्ट को 1950 के दशक के अंत में प्रतीकात्मक और लिस्ट प्रोसेसिंग (विशेष रूप से न्यूवेल, शॉ और साइमन के IPL और बाद में लिस्प में) के लिए पेश किया गया था। नुथ के 'द आर्ट ऑफ़ कंप्यूटर प्रोग्रामिंग' में व्यवस्थित उपचार ने उनके प्रामाणिक विश्लेषण को स्थापित किया।
Key figures
- Donald Knuth
- Robert Sedgewick
Related topics
Seminal works
- knuth1997vol1
- cormen2009
Frequently asked questions
- यदि एरे तेज़ यादृच्छिक पहुँच का समर्थन करते हैं तो लिंक्ड लिस्ट का उपयोग क्यों करें?
- लिंक्ड लिस्ट एक नोड के संदर्भ दिए जाने पर स्थिर समय में सम्मिलन या विलोपन की अनुमति देते हैं, अन्य तत्वों को स्थानांतरित किए बिना, जो एरे बीच में नहीं कर सकते। वे तब उपयोगी होते हैं जब अनुक्रम अक्सर बदलता है और स्थितिगत यादृच्छिक पहुँच की आवश्यकता नहीं होती है।
- यदि आकार बदलने से सब कुछ कॉपी हो जाता है तो एरे अपेंड को स्थिर समय क्यों माना जाता है?
- आकार बदलना शायद ही कभी होता है क्योंकि क्षमता आमतौर पर दोगुनी हो जाती है, इसलिए n अपेंड पर कुल कॉपी करने का काम n के अनुपात में होता है। सभी अपेंड में फैला हुआ, यह प्रति अपेंड एक परिशोधित स्थिर लागत देता है, भले ही व्यक्तिगत आकार बदलना O(n) हो।