सूची (सार डेटा प्रकार): Difference between revisions

Revision as of 17:53, 27 February 2023

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

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

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

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

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

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

संचालन

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

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

कार्यान्वयन

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

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

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

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

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

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

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

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

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

यह भी देखें

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

संदर्भ

↑ Abelson, Harold; Sussman, Gerald Jay (1996). Structure and Interpretation of Computer Programs. MIT Press.
↑ Reingold, Edward; Nievergelt, Jurg; Narsingh, Deo (1977). Combinatorial Algorithms: Theory and Practice. Englewood Cliffs, New Jersey: Prentice Hall. pp. 38–41. ISBN 0-13-152447-X.
↑ Barnett, Granville; Del tonga, Luca (2008). "Data Structures and Algorithms" (PDF). mta.ca. Retrieved 12 November 2014.
↑ Lerusalimschy, Roberto (December 2003). Programming in Lua (first edition) (First ed.). Lua.org. ISBN 8590379817. Retrieved 12 November 2014.
↑ Steele, Guy (1990). Common Lisp (Second ed.). Digital Press. pp. 29–31. ISBN 1-55558-041-6.

[1] Abelson, Harold; Sussman, Gerald Jay (1996). Structure and Interpretation of Computer Programs. MIT Press.

[2] Reingold, Edward; Nievergelt, Jurg; Narsingh, Deo (1977). Combinatorial Algorithms: Theory and Practice. Englewood Cliffs, New Jersey: Prentice Hall. pp. 38–41. ISBN 0-13-152447-X.

[3] Barnett, Granville; Del tonga, Luca (2008). "Data Structures and Algorithms" (PDF). mta.ca. Retrieved 12 November 2014.

[4] Lerusalimschy, Roberto (December 2003). Programming in Lua (first edition) (First ed.). Lua.org. ISBN 8590379817. Retrieved 12 November 2014.

[5] Steele, Guy (1990). Common Lisp (Second ed.). Digital Press. pp. 29–31. ISBN 1-55558-041-6.

[1]

[2]

[3]

[4]

[5]

@@ Line 1: / Line 1: @@
 {{Short description|Abstract data type used in computer science}}
-{{About|sequential data structures|random-access data structures|Array data type}}
+''यह लेख अनुक्रमिक डेटा संरचनाओं के बारे में है। रैंडम-एक्सेस डेटा संरचनाओं के लिए, सरणी डेटा प्रकार देखें।''
-[[कंप्यूटर विज्ञान]] में, एक सूची या [[अनुक्रम]] एक [[सार डेटा प्रकार]] है जो [[आदेश सिद्धांत]]ड [[मूल्य (कंप्यूटर विज्ञान)]] की एक सीमित संख्या का प्रतिनिधित्व करता है, जहां एक ही मान एक से अधिक बार हो सकता है। एक सूची का एक उदाहरण [[टपल]] या परिमित अनुक्रम की गणित अवधारणा का एक कंप्यूटर प्रतिनिधित्व है; (संभावित रूप से) सूची का अनंत एनालॉग एक [[स्ट्रीम (कंप्यूटिंग)]] है।<ref>{{cite book |title=[[Structure and Interpretation of Computer Programs]] |first1=Harold |last1=Abelson |first2=Gerald Jay |last2=Sussman |year=1996 |publisher=MIT Press}}</ref>{{rp|§3.5}} सूचियाँ [[कंटेनर (सार डेटा प्रकार)]] का एक मूल उदाहरण हैं, क्योंकि उनमें अन्य मान होते हैं। यदि एक ही मान कई बार आता है, तो प्रत्येक घटना को एक अलग आइटम माना जाता है।
-[[File:Singly-linked-list.svg|thumb|right|एक सिंगल-लिंक्ड सूची संरचना, तीन पूर्णांक तत्वों के साथ एक सूची लागू करना।]]नाम सूची का उपयोग कई ठोस [[डेटा संरचना]]ओं के लिए भी किया जाता है जिनका उपयोग अमूर्त प्रकार की सूचियों, विशेष रूप से लिंक की गई सूचियों और [[सरणी डेटा संरचना]]ओं को लागू करने के लिए किया जा सकता है। कुछ संदर्भों में, जैसे कि [[[[वर्ग आधारित प्रोग्रामिंग]] भाषा]] प्रोग्रामिंग में, शब्द सूची विशेष रूप से एक सरणी के बजाय एक लिंक की गई सूची को संदर्भित कर सकती है। वर्ग-आधारित प्रोग्रामिंग में, सूची आमतौर पर एक सामान्य सूची वर्ग के उपवर्गों के [[उदाहरण (कंप्यूटर विज्ञान)]] के रूप में प्रदान की जाती है, और अलग-अलग पुनरावृत्तियों के माध्यम से तय की जाती है।
+कंप्यूटर विज्ञान में, '''सूची या अनुक्रम एक अमूर्त डेटा प्रकार''' है जो क्रमबद्ध मूल्यों की एक सीमित संख्या का प्रतिनिधित्व करता है, जहां एक ही मान एक से अधिक बार हो सकता है। एक सूची का एक उदाहरण टपल या परिमित अनुक्रम की गणितीय अवधारणा का एक कंप्यूटर प्रस्तुतिकरण है; (संभावित रूप से) एक सूची का अनंत एनालॉग [[स्ट्रीम (कंप्यूटिंग)]] है।<ref>{{cite book |title=[[Structure and Interpretation of Computer Programs]] |first1=Harold |last1=Abelson |first2=Gerald Jay |last2=Sussman |year=1996 |publisher=MIT Press}}</ref>{{rp|§3.5}} सूचियाँ [[कंटेनर (सार डेटा प्रकार)|कंटेनर (अमूर्त डेटा प्रकार)]] का एक मूल उदाहरण हैं, क्योंकि उनमें अन्य मान होते हैं। यदि एक ही मान कई बार आता है, तो प्रत्येक घटना को एक विशिष्ट वस्तु माना जाता है।
-कई [[प्रोग्रामिंग भाषा]]एं सूची डेटा प्रकारों के लिए समर्थन प्रदान करती हैं, और सूचियों और सूची संचालन के लिए विशेष सिंटैक्स और शब्दार्थ हैं। [[कोष्ठक]] '()', कोष्ठक '[]', [[ब्रेस (विराम चिह्न)]] जैसे परिसीमकों की एक जोड़ी के भीतर, [[अल्पविराम]], अर्धविराम, और / या स्थान (विराम चिह्न) द्वारा अलग-अलग वस्तुओं को अनुक्रम में लिखकर एक सूची का निर्माण किया जा सकता है। )s '{}', या कोण कोष्ठक '<>'। कुछ भाषाएँ सूची प्रकारों को सरणी अनुक्रमित या [[सरणी डेटा प्रकार]]ों की तरह [[सरणी टुकड़ा करना]] की अनुमति दे सकती हैं, इस स्थिति में डेटा प्रकार को सरणी के रूप में अधिक सटीक रूप से वर्णित किया जाता है।
+[[File:Singly-linked-list.svg|thumb|right|एकल-लिंक्ड सूची संरचना, तीन पूर्णांक तत्वों के साथ एक सूची प्रयुक्त करना।]]नाम सूची का उपयोग कई मूर्त [[डेटा संरचना]]ओं के लिए भी किया जाता है जिनका उपयोग अमूर्त प्रकार की सूचियों, विशेष रूप से लिंक की गई सूचियों और [[सरणी डेटा संरचना]]ओं को प्रयुक्त करने के लिए किया जा सकता है। कुछ संदर्भों में, जैसे कि [[वर्ग आधारित प्रोग्रामिंग|क्लास-आधारित प्रोग्रामिंग]] में, शब्द सूची विशेष रूप से एक सरणी के अतिरिक्त एक लिंक की गई सूची को संदर्भित कर सकती है। क्लास-आधारित प्रोग्रामिंग में, सूची सामान्य रूप से एक सामान्य सूची क्लास के सबक्लासेस के [[उदाहरण (कंप्यूटर विज्ञान)]] के रूप में प्रदान की जाती है, और अलग-अलग पुनरावृत्तियों के माध्यम से निर्धारित की जाती है।
+कई [[प्रोग्रामिंग भाषा]]एं सूची डेटा प्रकारों के लिए समर्थन प्रदान करती हैं, और सूचियों और सूची संचालन के लिए विशेष सिंटैक्स और सिमैन्टिक हैं। [[कोष्ठक|लघुकोष्ठक]] '()', कोष्ठक '[]', [[ब्रेस (विराम चिह्न)|ब्रेसिज़ (धनुकोष्ठक)]] {}', या कोण कोष्ठक '<>' जैसे परिसीमकों की एक युग्म के अंदर, [[अल्पविराम]], अर्धविराम, और / या स्थान (विराम चिह्न) द्वारा अलग-अलग वस्तुओं को अनुक्रम में लिखकर एक सूची का निर्माण किया जा सकता है। कुछ भाषाएँ सरणी प्रकारों की तरह सूची प्रकारों को अनुक्रमित या विभाजन करने की स्वीकृति दे सकती हैं, इस स्थिति में डेटा प्रकार को एक सरणी के रूप में अधिक परिशुद्ध रूप से रूप से वर्णित किया जाता है।
+प्रारूप [[प्रकार सिद्धांत|सिद्धांत]] और [[कार्यात्मक प्रोग्रामिंग]] में, अमूर्त सूचियों को सामान्य रूप से [[आगमनात्मक प्रकार]] को दो संचालनों द्वारा परिभाषित किया जाता है: ''शून्य'' जो रिक्त सूची देता है, और ''चर'', जो सूची के प्रारंभ में एक वस्तु जोड़ता है।<ref>{{cite book|last1=Reingold|first1=Edward|last2=Nievergelt|first2=Jurg|last3=Narsingh|first3=Deo|title=Combinatorial Algorithms: Theory and Practice|date=1977|publisher=Prentice Hall|location=Englewood Cliffs, New Jersey|isbn=0-13-152447-X|pages=38–41}}</ref>
-[[प्रकार सिद्धांत]] और [[कार्यात्मक प्रोग्रामिंग]] में, अमूर्त सूचियों को आमतौर पर [[आगमनात्मक प्रकार]] को दो ऑपरेशनों द्वारा परिभाषित किया जाता है: ''शून्य'' जो खाली सूची देता है, और ''विपक्ष'', जो सूची की शुरुआत में एक आइटम जोड़ता है।<ref>{{cite book|last1=Reingold|first1=Edward|last2=Nievergelt|first2=Jurg|last3=Narsingh|first3=Deo|title=Combinatorial Algorithms: Theory and Practice|date=1977|publisher=Prentice Hall|location=Englewood Cliffs, New Jersey|isbn=0-13-152447-X|pages=38–41}}</ref>
 == संचालन ==
-सूची डेटा संरचना का कार्यान्वयन निम्नलिखित में से कुछ ऑपरेशन (गणित) प्रदान कर सकता है:
+सूची डेटा संरचना का कार्यान्वयन निम्नलिखित में से कुछ संक्रिया (गणित) प्रदान कर सकता है:
-* खाली सूची बनाने के लिए कंस्ट्रक्टर (कंप्यूटर विज्ञान);
+* रिक्त सूची बनाने के लिए निर्माता (कंप्यूटर विज्ञान);
-* एक सूची खाली है या नहीं, यह जांचने के लिए एक ऑपरेशन;
+* एक सूची रिक्त है या नहीं, यह जांचने के लिए एक संक्रिया;
-* किसी इकाई को सूची में जोड़ने के लिए एक ऑपरेशन
+* किसी इकाई को सूची में जोड़ने के लिए एक संक्रिया
-* किसी इकाई को सूची में जोड़ने के लिए एक ऑपरेशन
+* किसी इकाई को सूची में जोड़ने के लिए एक संक्रिया
-* सूची के पहले घटक (या शीर्ष) को निर्धारित करने के लिए एक ऑपरेशन
+* सूची के पहले घटक (या शीर्ष) को निर्धारित करने के लिए एक संक्रिया
-* किसी सूची के सभी घटकों को शामिल करने वाली सूची को संदर्भित करने के लिए एक ऑपरेशन, इसके पहले को छोड़कर (इसे सूची की पूंछ कहा जाता है।)
+* किसी सूची के सभी घटकों को सम्मिलित करने वाली सूची को संदर्भित करने के लिए एक संक्रिया, इसके पहले को छोड़कर (इसे सूची की "टैल" कहा जाता है।)
-* किसी दिए गए इंडेक्स पर तत्व तक पहुँचने के लिए एक ऑपरेशन।
+* किसी दिए गए इंडेक्स (सूचकांक) पर तत्व तक पहुँचने के लिए एक संक्रिया।
 == कार्यान्वयन ==
-सूचियाँ आमतौर पर या तो लिंक्ड सूचियों (या तो अकेले या दोगुनी लिंक्ड) के रूप में या सरणी डेटा संरचना के रूप में लागू की जाती हैं, आमतौर पर चर लंबाई या गतिशील सरणियाँ।
+सूचियाँ सामान्य रूप से या तो लिंक्ड सूचियों (या तो एकल या दोगुनी लिंक्ड) के रूप में या सरणियों के रूप में सामान्य रूप से चर लंबाई या गतिशील सरणियों के रूप में प्रयुक्त की जाती हैं।
-प्रोग्रामिंग लैंग्वेज [[लिस्प (प्रोग्रामिंग भाषा)]] से शुरू होने वाली सूचियों को लागू करने का मानक तरीका यह है कि सूची के प्रत्येक तत्व में इसके मूल्य और सूची में अगले तत्व के स्थान को इंगित करने वाला सूचक हो। इसका परिणाम या तो लिंक की गई सूची या ट्री डेटा संरचना में होता है, यह इस बात पर निर्भर करता है कि सूची में नेस्टेड सबलिस्ट हैं या नहीं। कुछ पुराने लिस्प कार्यान्वयन (जैसे कि [[प्रतीकवाद]] 3600 का लिस्प कार्यान्वयन) भी संकुचित सूचियों ([[सीडीआर कोडिंग]] का उपयोग करके) का समर्थन करता है जिसमें एक विशेष आंतरिक प्रतिनिधित्व (उपयोगकर्ता के लिए अदृश्य) था। पुनरावृति या पुनरावर्तन का उपयोग करके सूचियों में हेरफेर किया जा सकता है। [[अनिवार्य प्रोग्रामिंग]] में पूर्व को अक्सर पसंद किया जाता है, जबकि बाद वाला [[कार्यात्मक भाषा]]ओं में आदर्श है।
+प्रोग्रामिंग भाषा [[लिस्प (प्रोग्रामिंग भाषा)|सूची प्रसंस्करण (प्रोग्रामिंग भाषा)]] से प्रारंभ होने वाली सूचियों को प्रयुक्त करने का मानक तरीका यह है कि सूची के प्रत्येक तत्व में इसके मूल्य और सूची में अगले तत्व के स्थान को इंगित करने वाला पॉइन्टर हो। इसका परिणाम या तो एक लिंक्ड सूची या एक ट्री में होता है, यह इस बात पर निर्भर करता है कि सूची में नेस्टेड (स्थिर) उपसूची हैं। कुछ पुराने सूची प्रसंस्करण कार्यान्वयन (जैसे कि [[प्रतीकवाद]] 3600 का सूची प्रसंस्करण कार्यान्वयन) भी संकुचित सूचियों ([[सीडीआर कोडिंग|कॉम्पैक्ट डिस्क - रिकॉर्ड करने योग्य कोडिंग]] का उपयोग करके) का समर्थन करता है जिसमें एक विशेष आंतरिक प्रतिनिधित्व (उपयोगकर्ता के लिए अदृश्य) था। पुनरावृति या पुनरावर्तन का उपयोग करके सूचियों में कुशलतापूर्वक प्रयोग किया जा सकता है। [[अनिवार्य प्रोग्रामिंग]] में पूर्व को प्रायः चयन किया जाता है, जबकि बाद वाला [[कार्यात्मक भाषा]]ओं में मानक है।
-सूचियों को स्व-संतुलन वाले बाइनरी सर्च ट्री के रूप में लागू किया जा सकता है, जो इंडेक्स-वैल्यू जोड़े रखते हैं, किसी भी तत्व के लिए समान समय की पहुंच प्रदान करते हैं (उदाहरण के लिए सभी फ्रिंज में रहते हैं, और सबसे सही बच्चे के इंडेक्स को संग्रहीत करने वाले आंतरिक नोड, खोज को निर्देशित करने के लिए उपयोग किए जाते हैं) , सूची के आकार में समय लघुगणक ले रहा है, लेकिन जब तक यह बहुत अधिक नहीं बदलता है, यादृच्छिक अभिगम का भ्रम प्रदान करेगा और लॉगरिदमिक समय में भी स्वैप, उपसर्ग और संलग्न संचालन को सक्षम करेगा।<ref>{{cite web|last1=Barnett|first1=Granville|last2=Del tonga|first2=Luca|title=Data Structures and Algorithms|url=http://www.mta.ca/~rrosebru/oldcourse/263114/Dsa.pdf|website=mta.ca|access-date=12 November 2014|date=2008}}</ref>
+सूचियों को स्व-संतुलन वाले बाइनरी अन्वेषण ट्री के रूप में प्रयुक्त किया जा सकता है, जो इंडेक्स-मान जोड़े रखते हैं, किसी भी तत्व के लिए समान समय की अभिगम्य प्रदान करते हैं (उदाहरण के लिए सभी फ्रिन्ज में रहते हैं, और सबसे सही बच्चे के इंडेक्स को संग्रहीत करने वाले आंतरिक नोड, जांच को निर्देशित करने के लिए उपयोग किए जाते हैं), सूची के आकार में समय लॉगरिद्मिक ले रहा है, लेकिन जब तक यह बहुत अधिक नहीं परिवर्तित करता है, यादृच्छिक अभिगम का भ्रम प्रदान करेगा और लॉगरिदमिक समय में भी स्वैप, उपसर्ग और संलग्न संचालन को सक्षम करेगा।<ref>{{cite web|last1=Barnett|first1=Granville|last2=Del tonga|first2=Luca|title=Data Structures and Algorithms|url=http://www.mta.ca/~rrosebru/oldcourse/263114/Dsa.pdf|website=mta.ca|access-date=12 November 2014|date=2008}}</ref>
 == प्रोग्रामिंग भाषा समर्थन ==
-कुछ भाषाएँ सूची डेटा संरचना प्रदान नहीं करती हैं, लेकिन सूचियों का अनुकरण करने के लिए साहचर्य सरणियों या किसी प्रकार की तालिका के उपयोग की पेशकश करती हैं। उदाहरण के लिए, [[लुआ प्रोग्रामिंग भाषा]] टेबल प्रदान करती है। हालाँकि लुआ उन सूचियों को संग्रहीत करता है जिनमें संख्यात्मक सूचकांक आंतरिक रूप से सरणियों के रूप में होते हैं, फिर भी वे शब्दकोशों के रूप में दिखाई देते हैं।<ref>{{cite book|last1=Lerusalimschy|first1=Roberto|title=Programming in Lua (first edition)|date=December 2003|publisher=Lua.org|isbn=8590379817|edition=First|url=http://www.lua.org/pil/11.3.html|access-date=12 November 2014}}</ref>
+कुछ भाषाएँ सूची डेटा संरचना प्रदान नहीं करती हैं, लेकिन सूचियों का अनुकरण करने के लिए साहचर्य सरणियों या किसी प्रकार की तालिका के उपयोग की पेशकश करती हैं। उदाहरण के लिए, [[लुआ प्रोग्रामिंग भाषा]] सारणी प्रदान करती है। हालाँकि लुआ उन सूचियों को संग्रहीत करता है जिनमें संख्यात्मक सूचकांक आंतरिक रूप से सरणियों के रूप में होते हैं, फिर भी वे शब्दकोशों के रूप में दिखाई देते हैं।<ref>{{cite book|last1=Lerusalimschy|first1=Roberto|title=Programming in Lua (first edition)|date=December 2003|publisher=Lua.org|isbn=8590379817|edition=First|url=http://www.lua.org/pil/11.3.html|access-date=12 November 2014}}</ref>
-लिस्प प्रोग्रामिंग भाषा में, सूचियाँ मौलिक डेटा प्रकार हैं और प्रोग्राम कोड और डेटा दोनों का प्रतिनिधित्व कर सकती हैं। अधिकांश बोलियों में, पहले तीन अभाज्य संख्याओं की सूची को इस रूप में लिखा जा सकता है <code>(list 2 3 5)</code>. लिस्प की कई बोलियों में, [[योजना (प्रोग्रामिंग भाषा)]] सहित, एक सूची जोड़े का एक संग्रह है, जिसमें एक मूल्य और अगली जोड़ी (या शून्य मान) के लिए एक सूचक होता है, जो एक एकल लिंक्ड सूची बनाता है।<ref>{{cite book|last1=Steele|first1=Guy|title=Common Lisp|date=1990|publisher=Digital Press|isbn=1-55558-041-6|pages=29–31|edition=Second}}</ref>
+सूची प्रसंस्करण प्रोग्रामिंग भाषा में, सूचियाँ मौलिक डेटा प्रकार हैं और प्रोग्राम कोड और डेटा दोनों का प्रतिनिधित्व कर सकती हैं। अधिकांश भाषाओ में, पहले तीन अभाज्य संख्याओं की सूची को इस रूप में लिखा <code>(list 2 3 5)</code> जा सकता है। सूची प्रसंस्करण की कई भाषाओ में, [[योजना (प्रोग्रामिंग भाषा)]] सहित, एक सूची जोड़े का एक संग्रह है, जिसमें एक मान और अगली युग्म (या शून्य मान) के लिए एक पॉइन्टर होता है, जो एक एकल लिंक्ड सूची बनाता है।<ref>{{cite book|last1=Steele|first1=Guy|title=Common Lisp|date=1990|publisher=Digital Press|isbn=1-55558-041-6|pages=29–31|edition=Second}}</ref>
 == अनुप्रयोग ==
-जैसा कि नाम से ही स्पष्ट है, सूचियों का उपयोग तत्वों की सूची को संग्रहीत करने के लिए किया जा सकता है। हालाँकि, पारंपरिक सरणी डेटा संरचना के विपरीत, सूचियाँ विस्तारित और सिकुड़ सकती हैं, और स्मृति में गतिशील रूप से संग्रहीत होती हैं।
+जैसा कि नाम से ही स्पष्ट है, सूचियों का उपयोग तत्वों की सूची को संग्रहीत करने के लिए किया जा सकता है। हालाँकि, पारंपरिक सरणी डेटा संरचना के विपरीत, सूचियाँ विस्तारित और संकुचित हो सकती हैं, और स्मृति में गतिशील रूप से संग्रहीत होती हैं।
-कंप्यूटिंग में, सेट की तुलना में सूचियों को लागू करना आसान होता है। गणितीय अर्थ में एक परिमित [[सेट (गणित)]] को अतिरिक्त प्रतिबंधों के साथ एक सूची के रूप में महसूस किया जा सकता है; अर्थात्, डुप्लिकेट तत्वों की अनुमति नहीं है और आदेश अप्रासंगिक है। सूची को क्रमबद्ध करने से यह निर्धारित करने में तेजी आती है कि कोई दिया गया आइटम पहले से ही सेट में है, लेकिन ऑर्डर सुनिश्चित करने के लिए, सूची में नई प्रविष्टि जोड़ने के लिए अधिक समय की आवश्यकता होती है। कुशल कार्यान्वयन में, हालांकि, सूची के बजाय स्व-संतुलन बाइनरी सर्च ट्री या [[हैश तालिका]] का उपयोग करके सेट लागू किए जाते हैं।
+कंप्यूटिंग में, समूह की तुलना में सूचियों को प्रयुक्त करना आसान होता है। गणितीय अर्थ में एक परिमित [[सेट (गणित)|समुच्चय (गणित)]] को अतिरिक्त प्रतिबंधों के साथ एक सूची के रूप में संपादित किया जा सकता है; अर्थात्, प्रतिलिपि तत्वों की स्वीकृति नहीं है और क्रम अप्रासंगिक है। सूची को क्रमबद्ध करने से यह निर्धारित करने में तीव्रता आती है कि कोई दी गई वस्तु पहले से ही समुच्चय में है, लेकिन क्रम सुनिश्चित करने के लिए, सूची में नई प्रविष्टि जोड़ने के लिए अधिक समय की आवश्यकता होती है। कुशल कार्यान्वयन में, हालांकि, सूची के अतिरिक्त स्व-संतुलन बाइनरी जांच ट्री या [[हैश तालिका]] का उपयोग करके समुच्चय प्रयुक्त किए जाते हैं।
-सूचियाँ [[कतार ([[सार डेटा प्रकार]])]], स्टैक (सार डेटा प्रकार), और उनकी विविधताओं सहित अन्य अमूर्त डेटा प्रकारों के लिए भी आधार बनाती हैं।
+सूचियाँ क्यू, स्टैक और उनकी विविधताओं सहित अन्य अमूर्त डेटा प्रकारों के लिए भी आधार बनाती हैं।
-== सार परिभाषा ==
+== अमूर्त परिभाषा ==
-सार सूची प्रकार एल कुछ प्रकार ई (एक प्रकार बहुरूपता सूची) के तत्वों के साथ निम्नलिखित कार्यों द्वारा परिभाषित किया गया है:
+अमूर्त सूची प्रकार 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''
-: विपक्ष (ई<sub>1</sub>, एल<sub>1</sub>) = विपक्ष (ई<sub>2</sub>, एल<sub>2</sub>) अगर ई<sub>1</sub> = और<sub>2</sub> और मैं<sub>1</sub> = एल<sub>2</sub>
+:: cons (''e''<sub>1</sub>, ''l''<sub>1</sub>) = cons (''e''<sub>2</sub>, ''l''<sub>2</sub>) if ''e''<sub>1</sub> = ''e''<sub>2</sub> and ''l''<sub>1</sub> = ''l''<sub>2</sub>
 ध्यान दें कि पहले (शून्य ()) और बाकी (शून्य ()) परिभाषित नहीं हैं।
 ये अभिगृहीत अमूर्त स्टैक (अमूर्त डेटा प्रकार) डेटा प्रकार के समतुल्य हैं।
-टाइप थ्योरी में, उपरोक्त परिभाषा को कंस्ट्रक्टर के संदर्भ में परिभाषित एक आगमनात्मक प्रकार के रूप में अधिक माना जाता है: शून्य और विपक्ष। बीजगणितीय शब्दों में, इसे परिवर्तन 1 + E × L → L के रूप में दर्शाया जा सकता है। पहले और बाकी को कॉन्स कंस्ट्रक्टर पर [[पैटर्न मिलान]] और अलग से शून्य मामले को संभालने के द्वारा प्राप्त किया जाता है।
+प्रारूप सिद्धांत में, उपरोक्त परिभाषा को निर्माता के संदर्भ में परिभाषित एक आगमनात्मक प्रकार के रूप में अधिक माना जाता है: शून्य और चर बीजगणितीय पदों में, इसे परिवर्तन 1 + E × L → L के रूप में दर्शाया जा सकता है। पहले और बाकी को कॉन्स निर्माता पर [[पैटर्न मिलान|पैटर्न का मेल]] और अलग से शून्य स्थिति को संभालने के द्वारा प्राप्त किया जाता है।
-=== सूची मोनाद ===
+=== सूची मोनाड ===
-सूची प्रकार निम्नलिखित कार्यों के साथ एक [[मोनाड (कार्यात्मक प्रोग्रामिंग)]] बनाता है (ई<sup>*</sup> एल के बजाय टाइप ई के तत्वों के साथ मोनोमोर्फिक सूचियों का प्रतिनिधित्व करने के लिए):
+सूची प्रकार निम्नलिखित फलनों के साथ एक [[मोनाड (कार्यात्मक प्रोग्रामिंग)]] बनाता है (E<sup>*L</sup> के अतिरिक्त प्रारूप E के तत्वों के साथ समरूप सूचियों का प्रतिनिधित्व करने के लिए):
 :<math>\text{return}\colon A \to A^{*} = a \mapsto \text{cons} \, a \, \text{nil}</math>
@@ Line 71: / Line 75: @@
 जहां परिशिष्ट को इस प्रकार परिभाषित किया गया है:
 :<math>\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}</math>
-वैकल्पिक रूप से, मोनैड को ऑपरेशन रिटर्न, एफएमएपी और जॉइन के संदर्भ में परिभाषित किया जा सकता है:
+वैकल्पिक रूप से, मोनैड को संक्रिया प्रतिकृति, एफएमएपी और जोड़ के संदर्भ में परिभाषित किया जा सकता है:
 :<math>\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}</math>
 :<math>\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}</math>
-ध्यान दें कि एफएमएपी, ज्वाइन, एपेंड और बाइंड अच्छी तरह से परिभाषित हैं, क्योंकि वे प्रत्येक पुनरावर्ती कॉल पर उत्तरोत्तर गहन तर्कों पर लागू होते हैं।
+ध्यान दें कि एफएमएपी, ज्वाइन, एपेंड और बाइंड अच्छी तरह से परिभाषित हैं, क्योंकि वे प्रत्येक पुनरावर्ती कॉल पर प्रगामीयतः गहन तर्कों पर प्रयुक्त होते हैं।
 सूची प्रकार एक योज्य मोनाड है, शून्य के साथ शून्य के रूप में शून्य है और मोनाडिक योग के रूप में संलग्न है।
-एपेंड ऑपरेशन के तहत सूचियाँ एक मोनॉइड बनाती हैं। मोनॉइड का पहचान तत्व खाली सूची है, शून्य। वास्तव में, यह सूची तत्वों के सेट पर [[मुक्त [[मोनोइड]]]] है।
+एपेंड संक्रिया के अंतर्गत सूचियाँ एक मोनॉइड बनाती हैं। मोनॉइड का पहचान तत्व रिक्त सूची शून्य है। वास्तव में, यह सूची तत्वों के समुच्चय पर [[मुक्त [[मोनोइड]]]] है।
 == यह भी देखें ==
 {{Wiktionary|list}}
-* ऐरे डेटा प्रकार
+* सरणी डेटा प्रकार
-* कतार (सार डेटा प्रकार)
+* क्यू (अमूर्त डेटा प्रकार)
-* [[सेट (सार डेटा प्रकार)]]
+* समुच्चय [[सेट (सार डेटा प्रकार)|(अमूर्त डेटा प्रकार)]]
-* ढेर (सार डेटा प्रकार)
+* स्टैक (अमूर्त डेटा प्रकार)
 *स्ट्रीम (कंप्यूटिंग)

v t e Well-known data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

v t e Data types
Uninterpreted	Bit Byte Trit Tryte Word Bit array
Numeric	Arbitrary-precision or bignum Complex Decimal Fixed point Floating point Reduced precision Minifloat Half precision bfloat16 Single precision Double precision Quadruple precision Octuple precision Extended precision Long double Integer signedness Interval Rational
Pointer	Address physical virtual Reference
Text	Character String null-terminated
Composite	Algebraic data type generalized Array Associative array Class Dependent Equality Inductive Intersection List Object metaobject Option type Product Record or Struct Refinement Set Union tagged
Other	Boolean Bottom type Collection Enumerated type Exception Function type Opaque data type Recursive data type Semaphore Stream Top type Type class Unit type Void
Related topics	Abstract data type Boxing Data structure Generic Kind metaclass Parametric polymorphism Primitive data type Interface Subtyping Type constructor Type conversion Type system Type theory Variable

Anonymous

Search

सूची (सार डेटा प्रकार): Difference between revisions

Namespaces

More

Page actions

Revision as of 17:53, 27 February 2023

Contents

संचालन

कार्यान्वयन

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

अनुप्रयोग

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

सूची मोनाड

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

सूची (सार डेटा प्रकार): Difference between revisions

Revision as of 17:53, 27 February 2023

संचालन

कार्यान्वयन

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

अनुप्रयोग

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

सूची मोनाड

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories