सूची (सार डेटा प्रकार)

This article is about sequential data structures. For random-access data structures, see Array data type.

कंप्यूटर विज्ञान में, एक सूची या अनुक्रम एक सार डेटा प्रकार है जो आदेश सिद्धांतड मूल्य (कंप्यूटर विज्ञान) की एक सीमित संख्या का प्रतिनिधित्व करता है, जहां एक ही मान एक से अधिक बार हो सकता है। एक सूची का एक उदाहरण टपल या परिमित अनुक्रम की गणित अवधारणा का एक कंप्यूटर प्रतिनिधित्व है; (संभावित रूप से) सूची का अनंत एनालॉग एक स्ट्रीम (कंप्यूटिंग) है। सूचियाँ कंटेनर (सार डेटा प्रकार) का एक मूल उदाहरण हैं, क्योंकि उनमें अन्य मान होते हैं। यदि एक ही मान कई बार आता है, तो प्रत्येक घटना को एक अलग आइटम माना जाता है।

एक सिंगल-लिंक्ड सूची संरचना, तीन पूर्णांक तत्वों के साथ एक सूची लागू करना।

नाम सूची का उपयोग कई ठोस डेटा संरचनाओं के लिए भी किया जाता है जिनका उपयोग अमूर्त प्रकार की सूचियों, विशेष रूप से लिंक की गई सूचियों और सरणी डेटा संरचनाओं को लागू करने के लिए किया जा सकता है। कुछ संदर्भों में, जैसे कि [[वर्ग आधारित प्रोग्रामिंग भाषा]] प्रोग्रामिंग में, शब्द सूची विशेष रूप से एक सरणी के बजाय एक लिंक की गई सूची को संदर्भित कर सकती है। वर्ग-आधारित प्रोग्रामिंग में, सूची आमतौर पर एक सामान्य सूची वर्ग के उपवर्गों के उदाहरण (कंप्यूटर विज्ञान) के रूप में प्रदान की जाती है, और अलग-अलग पुनरावृत्तियों के माध्यम से तय की जाती है।

कई प्रोग्रामिंग भाषाएं सूची डेटा प्रकारों के लिए समर्थन प्रदान करती हैं, और सूचियों और सूची संचालन के लिए विशेष सिंटैक्स और शब्दार्थ हैं। कोष्ठक '()', कोष्ठक '[]', ब्रेस (विराम चिह्न) जैसे परिसीमकों की एक जोड़ी के भीतर, अल्पविराम, अर्धविराम, और / या स्थान (विराम चिह्न) द्वारा अलग-अलग वस्तुओं को अनुक्रम में लिखकर एक सूची का निर्माण किया जा सकता है। )s '{}', या कोण कोष्ठक '<>'। कुछ भाषाएँ सूची प्रकारों को सरणी अनुक्रमित या सरणी डेटा प्रकारों की तरह सरणी टुकड़ा करना की अनुमति दे सकती हैं, इस स्थिति में डेटा प्रकार को सरणी के रूप में अधिक सटीक रूप से वर्णित किया जाता है।

प्रकार सिद्धांत और कार्यात्मक प्रोग्रामिंग में, अमूर्त सूचियों को आमतौर पर आगमनात्मक प्रकार को दो ऑपरेशनों द्वारा परिभाषित किया जाता है: शून्य जो खाली सूची देता है, और विपक्ष, जो सूची की शुरुआत में एक आइटम जोड़ता है।

संचालन

सूची डेटा संरचना का कार्यान्वयन निम्नलिखित में से कुछ ऑपरेशन (गणित) प्रदान कर सकता है:

• खाली सूची बनाने के लिए कंस्ट्रक्टर (कंप्यूटर विज्ञान);
• एक सूची खाली है या नहीं, यह जांचने के लिए एक ऑपरेशन;
• किसी इकाई को सूची में जोड़ने के लिए एक ऑपरेशन
• किसी इकाई को सूची में जोड़ने के लिए एक ऑपरेशन
• सूची के पहले घटक (या शीर्ष) को निर्धारित करने के लिए एक ऑपरेशन
• किसी सूची के सभी घटकों को शामिल करने वाली सूची को संदर्भित करने के लिए एक ऑपरेशन, इसके पहले को छोड़कर (इसे सूची की पूंछ कहा जाता है।)
• किसी दिए गए इंडेक्स पर तत्व तक पहुँचने के लिए एक ऑपरेशन।

कार्यान्वयन

सूचियाँ आमतौर पर या तो लिंक्ड सूचियों (या तो अकेले या दोगुनी लिंक्ड) के रूप में या सरणी डेटा संरचना के रूप में लागू की जाती हैं, आमतौर पर चर लंबाई या गतिशील सरणियाँ।

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

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

प्रोग्रामिंग भाषा समर्थन

कुछ भाषाएँ सूची डेटा संरचना प्रदान नहीं करती हैं, लेकिन सूचियों का अनुकरण करने के लिए साहचर्य सरणियों या किसी प्रकार की तालिका के उपयोग की पेशकश करती हैं। उदाहरण के लिए, लुआ प्रोग्रामिंग भाषा टेबल प्रदान करती है। हालाँकि लुआ उन सूचियों को संग्रहीत करता है जिनमें संख्यात्मक सूचकांक आंतरिक रूप से सरणियों के रूप में होते हैं, फिर भी वे शब्दकोशों के रूप में दिखाई देते हैं। लिस्प प्रोग्रामिंग भाषा में, सूचियाँ मौलिक डेटा प्रकार हैं और प्रोग्राम कोड और डेटा दोनों का प्रतिनिधित्व कर सकती हैं। अधिकांश बोलियों में, पहले तीन अभाज्य संख्याओं की सूची को इस रूप में लिखा जा सकता है (list 2 3 5). लिस्प की कई बोलियों में, योजना (प्रोग्रामिंग भाषा) सहित, एक सूची जोड़े का एक संग्रह है, जिसमें एक मूल्य और अगली जोड़ी (या शून्य मान) के लिए एक सूचक होता है, जो एक एकल लिंक्ड सूची बनाता है।

अनुप्रयोग

जैसा कि नाम से ही स्पष्ट है, सूचियों का उपयोग तत्वों की सूची को संग्रहीत करने के लिए किया जा सकता है। हालाँकि, पारंपरिक सरणी डेटा संरचना के विपरीत, सूचियाँ विस्तारित और सिकुड़ सकती हैं, और स्मृति में गतिशील रूप से संग्रहीत होती हैं।

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

सूचियाँ [[कतार (सार डेटा प्रकार)]], स्टैक (सार डेटा प्रकार), और उनकी विविधताओं सहित अन्य अमूर्त डेटा प्रकारों के लिए भी आधार बनाती हैं।

सार परिभाषा

सार सूची प्रकार एल कुछ प्रकार ई (एक प्रकार बहुरूपता सूची) के तत्वों के साथ निम्नलिखित कार्यों द्वारा परिभाषित किया गया है:

शून्य: () → एल

विपक्ष: ई × एल → एल

पहला: एल → ई

बाकी: एल → एल

सिद्धांतों के साथ

पहला (विपक्ष (ई, एल)) = ई

बाकी (विपक्ष (ई, एल)) = एल

किसी भी तत्व ई और किसी भी सूची एल के लिए। यह निहित है

विपक्ष (ई, एल) ≠ एल

विपक्ष (ई, एल) ≠ ई

विपक्ष (ई₁, एल₁) = विपक्ष (ई₂, एल₂) अगर ई₁ = और₂ और मैं₁ = एल₂

ध्यान दें कि पहले (शून्य ()) और बाकी (शून्य ()) परिभाषित नहीं हैं।

ये अभिगृहीत अमूर्त स्टैक (अमूर्त डेटा प्रकार) डेटा प्रकार के समतुल्य हैं।

टाइप थ्योरी में, उपरोक्त परिभाषा को कंस्ट्रक्टर के संदर्भ में परिभाषित एक आगमनात्मक प्रकार के रूप में अधिक माना जाता है: शून्य और विपक्ष। बीजगणितीय शब्दों में, इसे परिवर्तन 1 + E × L → L के रूप में दर्शाया जा सकता है। पहले और बाकी को कॉन्स कंस्ट्रक्टर पर पैटर्न मिलान और अलग से शून्य मामले को संभालने के द्वारा प्राप्त किया जाता है।

सूची मोनाद

सूची प्रकार निम्नलिखित कार्यों के साथ एक मोनाड (कार्यात्मक प्रोग्रामिंग) बनाता है (ई^* एल के बजाय टाइप ई के तत्वों के साथ मोनोमोर्फिक सूचियों का प्रतिनिधित्व करने के लिए):

${\text{return}}\colon A\to A^{*}=a\mapsto {\text{cons}}\,a\,{\text{nil}}$

${\text{bind}}\colon A^{*}\to (A\to B^{*})\to B^{*}=l\mapsto f\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,(f\,a)\,({\text{bind}}\,l'\,f)&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}$

जहां परिशिष्ट को इस प्रकार परिभाषित किया गया है:

${\text{append}}\colon A^{*}\to A^{*}\to A^{*}=l_{1}\mapsto l_{2}\mapsto {\begin{cases}l_{2}&{\text{if}}\ l_{1}={\text{nil}}\\{\text{cons}}\,a\,({\text{append}}\,l_{1}'\,l_{2})&{\text{if}}\ l_{1}={\text{cons}}\,a\,l_{1}'\end{cases}}$

वैकल्पिक रूप से, मोनैड को ऑपरेशन रिटर्न, एफएमएपी और जॉइन के संदर्भ में परिभाषित किया जा सकता है:

${\text{fmap}}\colon (A\to B)\to (A^{*}\to B^{*})=f\mapsto l\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{cons}}\,(f\,a)({\text{fmap}}f\,l')&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}$

${\text{join}}\colon {A^{*}}^{*}\to A^{*}=l\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,a\,({\text{join}}\,l')&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}$

ध्यान दें कि एफएमएपी, ज्वाइन, एपेंड और बाइंड अच्छी तरह से परिभाषित हैं, क्योंकि वे प्रत्येक पुनरावर्ती कॉल पर उत्तरोत्तर गहन तर्कों पर लागू होते हैं।

सूची प्रकार एक योज्य मोनाड है, शून्य के साथ शून्य के रूप में शून्य है और मोनाडिक योग के रूप में संलग्न है।

एपेंड ऑपरेशन के तहत सूचियाँ एक मोनॉइड बनाती हैं। मोनॉइड का पहचान तत्व खाली सूची है, शून्य। वास्तव में, यह सूची तत्वों के सेट पर [[मुक्त मोनोइड]] है।

यह भी देखें

• ऐरे डेटा प्रकार
• कतार (सार डेटा प्रकार)
• सेट (सार डेटा प्रकार)
• ढेर (सार डेटा प्रकार)
• स्ट्रीम (कंप्यूटिंग)