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

यह लेख अनुक्रमिक डेटा संरचनाओं के बारे में है। रैंडम-एक्सेस डेटा संरचनाओं के लिए, सरणी डेटा प्रकार देखें।

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

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

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

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

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

संचालन

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

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

कार्यान्वयन

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

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

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

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

कुछ भाषाएँ सूची डेटा संरचना प्रदान नहीं करती हैं, लेकिन सूचियों का अनुकरण करने के लिए साहचर्य सरणियों या किसी प्रकार की तालिका के उपयोग की पेशकश करती हैं। उदाहरण के लिए, लुआ प्रोग्रामिंग भाषा सारणी प्रदान करती है। हालाँकि लुआ उन सूचियों को संग्रहीत करता है जिनमें संख्यात्मक सूचकांक आंतरिक रूप से सरणियों के रूप में होते हैं, फिर भी वे शब्दकोशों के रूप में दिखाई देते हैं।

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

अनुप्रयोग

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

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

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

अमूर्त परिभाषा

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

nil: () → L

cons: E × L → L

first: L → E

rest: L → L

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

first (cons (e, l)) = e

rest (cons (e, l)) = l

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

cons (e, l) ≠ l

cons (e, l) ≠ e

cons (e₁, l₁) = cons (e₂, l₂) if e₁ = e₂ and l₁ = l₂

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

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

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

सूची मोनाड

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

${\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}}$

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

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

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

यह भी देखें

• सरणी डेटा प्रकार
• क्यू (अमूर्त डेटा प्रकार)
• समुच्चय (अमूर्त डेटा प्रकार)
• स्टैक (अमूर्त डेटा प्रकार)
• स्ट्रीम (कंप्यूटिंग)