डेटा स्ट्रक्चर्स: पायथन उदाहरणों के साथ एक व्यापक गाइड

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

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

हम शुरुआत करेंगे रैखिक (linear) डेटा स्ट्रक्चर्स से, जैसे arrays, lists, queues, और stacks। इसके बाद हम linear और non-linear स्ट्रक्चर्स के बीच का अंतर समझेंगे, और फिर hash tables, trees, तथा graphs में गहराई से जाएँगे।

यदि आप और सीखना चाहते हैं, तो पायथन में डेटा स्ट्रक्चर्स और एल्गोरिदम पर यह कोर्स देखें।

Arrays

Arrays मूलभूत डेटा स्ट्रक्चर्स हैं जो अधिकतर प्रोग्रामिंग भाषाओं में उपलब्ध हैं। ये मेमोरी में निश्चित संख्या (N) के मानों को क्रमिक रूप से संग्रहीत करने में सक्षम बनाते हैं।

Array के तत्त्वों की अनुक्रमणिका (index) पहले तत्त्व के लिए 0 से लेकर अंतिम तत्त्व के लिए (N-1) तक होती है।

ये निम्नलिखित ऑपरेशंस की अनुमति देते हैं:

1. किसी दिए गए इंडेक्स पर मान पढ़ना।
2. किसी दिए गए इंडेक्स पर मान अपडेट करना।
3. संग्रहीत सभी मानों पर इटरेट करना।
4. Array का आकार प्राप्त करना।

Arrays उन स्थितियों में अत्यंत प्रभावी होते हैं जहाँ संग्रहीत किए जाने वाले मानों की संख्या पहले से ज्ञात हो और मुख्य ऑपरेशंस विशिष्ट इंडेक्सों पर डेटा पढ़ने-लिखने से संबंधित हों।

मान लीजिए आपको दिसंबर माह के दैनिक तापमान रीडिंग्स संग्रहीत करनी हैं। आप चाहेंगे कि उपयोगकर्ता किसी विशिष्ट दिन का तापमान निकाल सकें और महीने भर के तापमान पर विभिन्न सांख्यिकीय विश्लेषण कर सकें।

चूँकि दिसंबर में दिनों की संख्या पहले से 31 ज्ञात है, तापमान रीडिंग्स संग्रहीत करने के लिए arrays उत्कृष्ट विकल्प हैं। प्रारंभ में 31 खाली स्थानों वाला एक array बनाया जाएगा। फिर, प्रत्येक रीडिंग प्राप्त होने पर, दिए गए दिन का तापमान संबंधित array इंडेक्स पर असाइन किया जाएगा: दिन 1 इंडेक्स 0 पर, दिन 2 इंडेक्स 1 पर, और इसी तरह, दिन 31 इंडेक्स 30 पर।

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

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

हम [None] * 31 का उपयोग करके 31 तत्त्वों का एक list बना सकते हैं जो array का सिमुलेशन करे, जिसमें हर तत्त्व प्रारंभ में None हो। यहाँ None यह इंगित करता है कि अभी तक कोई तापमान रीडिंग दर्ज नहीं हुई है।

december_temperatures = [None] * 31संचालित द्वारा

किसी विशिष्ट इंडेक्स पर मान सेट करने के लिए हम december_temperatures[index] का उपयोग करते हैं, जहाँ index 0 से 30 के बीच की संख्या है। उदाहरण के तौर पर, पहले दिन का तापमान (जो इंडेक्स 0 पर संग्रहीत है) दर्ज करने के लिए हम ऐसे करेंगे:

december_temperatures[0] = 15संचालित द्वारा

किसी तापमान तक पहुँचना भी इसी तरह सरल है, december_temperatures[index] का उपयोग करके।

print(december_temperatures[0])संचालित द्वारा

15संचालित द्वारा

Lists

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

इस परिदृश्य में एक अधिक उपयुक्त डेटा स्ट्रक्चर list होगा। लिस्ट दो प्रकार की होती हैं:

• Array lists
• Linked lists

Array lists

Array lists को arrays के अधिक लचीले संस्करण के रूप में देखा जा सकता है। ये arrays के सभी काम कर सकती हैं, साथ ही नए मान जोड़ भी सकती हैं, इसलिए इनका आकार बनाते समय स्थिर नहीं रहता। Python में array list list() के अनुरूप है।

इनका इम्प्लीमेंटेशन एक ऐसे array पर निर्भर करता है जिसे जगह समाप्त होने पर बढ़ाया जाता है, इसलिए नाम रखा गया है array list। लेकिन जैसा हमने पहले सीखा, arrays बढ़ नहीं सकते—तो यह कैसे संभव है?

जब array list का आंतरिक array भर जाता है और हमें नया मान जोड़ना होता है, तो पर्दे के पीछे एक बड़ा array बनाया जाता है। पहले के सभी मान इस नए, बड़े array में कॉपी किए जाते हैं। तब, नया मान नए array में उपलब्ध पहली स्थिति पर जोड़ दिया जाता है।

मान लीजिए हम इस array में 71 जोड़ना चाहते हैं:

इसे इस प्रकार पूरा किया जा सकता है:

हर बार इस ऑपरेशन में जितनी नई जगह आवंटित की जाती है, वह array list के प्रदर्शन के लिए अत्यंत महत्वपूर्ण है। यदि हर append पर हम केवल एक अतिरिक्त स्थान वाला array बनाते, तो हर append में पूर्ववर्ती सभी डेटा को कॉपी करना पड़ता। यह अत्यंत अकार्यकुशल होता—सोचिए, सिर्फ एक नया रिकॉर्ड जोड़ने के लिए लाखों रिकॉर्ड्स कॉपी करने पड़ें।

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

Python लिस्ट में तत्त्व जोड़ने के लिए हम .append() मेथड का उपयोग करते हैं। यहाँ एक खाली लिस्ट बनाने और उसमें एक तापमान रीडिंग जोड़ने का उदाहरण है:

temperatures = []
temperatures.append(35)संचालित द्वारा

Linked lists

कंप्यूटर में डेटा को संरचित करने के लिए हमें मानों को एक-दूसरे से संबंधित करने की आवश्यकता होती है। Arrays यह काम सन्निकट (contiguous) मेमोरी लोकेशंस—अर्थात एक-दूसरे के बिलकुल पास स्थित लोकेशंस—आवंटित करके और मानों को क्रम से संग्रहीत करके करते हैं। इसे सड़क पर घरों की कतार की तरह समझें: हर घर का एक अद्वितीय पता (इंडेक्स) होता है, और वे भौतिक रूप से एक-दूसरे के पास होते हैं।

हालाँकि, डेटा को व्यवस्थित करने का यह एकमात्र तरीका नहीं है। एक विकल्प नोड-आधारित संरचना का उपयोग करना है।

एक नोड ऐसा ऑब्जेक्ट होता है जो एक मान और अन्य नोड्स के रेफरेंसेज़ रखता है। उदाहरण के लिए, नोड्स का उपयोग करके list जैसे स्ट्रक्चर बनाने के लिए, हम ऐसा नोड बना सकते हैं जो एक मान के साथ सूची के अगले तत्त्व का रेफरेंस भी रखे। Python में इसे एक क्लास से इम्प्लीमेंट किया जा सकता है:

class Node:
    def __init__(self, value, next_node):
        self.value = value
        self.next_node = next_nodeसंचालित द्वारा

इस तरीके से, next_node रेफरेंस के माध्यम से मानों को जोड़कर एक लिस्ट बनाई जा सकती है। यहाँ एक कोड स्निपेट है जो 42, 17, और 37 मानों वाली सूची बनाता है:

node_37 = Node(37, None) # There's no node after 37 so next_node is None
node_17 = Node(17, node_37)
node_42 = Node(42, node_17)संचालित द्वारा

नोड्स को इस तरह हाथ से जोड़ना व्यावहारिक नहीं है। वास्तविक इम्प्लीमेंटेशन में एक और क्लास बनानी पड़ती है जो सूची के पहले और अंतिम नोड दोनों के रेफरेंस बनाए रखे। नया मान जोड़ने के लिए हम:

1. वांछित मान के साथ एक नोड बनाते हैं।
2. वर्तमान अंतिम नोड के अगले नोड के रूप में इस नए नोड को सेट करते हैं।
3. अंतिम नोड के रेफरेंस को नव-जोड़े गए नोड पर अपडेट करते हैं।

कल्पना कीजिए हम अपने उदाहरण array में 71 जोड़ना चाहते हैं:

इसे इस प्रकार पूरा किया जा सकता है:

class LinkedList:
    def __init__(self):
        self.first_node = None
        self.last_node = None

    def append(self, value):
        node = Node(value, None)
        if self.first_node is None:
            self.first_node = node
            self.last_node = node
        else:
            self.last_node.next_node = node
            self.last_node = nodeसंचालित द्वारा

Array lists के विपरीत, हम इंडेक्स के माध्यम से सीधे मानों तक नहीं पहुँच सकते। किसी इंडेक्स पर विशिष्ट मान पढ़ने के लिए हमें पहले नोड से शुरू कर एक-एक कर अगले नोड तक बढ़ते हुए वांछित इंडेक्स तक पहुँचने की आवश्यकता होती है। यह प्रत्यक्ष पहुँच की तुलना में काफी धीमा है। यदि सूची में लाखों मान संग्रहीत हों, तो किसी विशिष्ट इंडेक्स तक पहुँचने के लिए मेमोरी में लाखों मान पढ़ने पड़ेंगे।

Linked list का लाभ यह है कि हम सूची के आगे या पीछे से तत्त्व तुरंत जोड़ और हटा सकते हैं। इसी क्षमता से हम दो नए डेटा स्ट्रक्चर्स—queues और stacks—इम्प्लीमेंट कर सकते हैं, जिन पर हम अगले भाग में चर्चा करेंगे।

Queues

मान लीजिए आप एक रेस्टोरेंट ऐप विकसित कर रहे हैं जो ग्राहक ऑर्डर्स लॉग करता है और उन्हें किचन तक पहुँचाता है। जब ग्राहक रेस्टोरेंट में आते हैं, तो वे ऑर्डर देने के लिए कतार में लगेंगे, और उम्मीद करेंगे कि उन्हें उनके आने के क्रम में सर्व किया जाए। यानी लाइन में पहला ग्राहक पहले ऑर्डर पाएगा और आखिरी ग्राहक सबसे अंत में।

किचन में शेफ एक समय में केवल एक ऑर्डर पर ध्यान देना पसंद करता है, इसलिए ऐप को केवल वर्तमान ऑर्डर ही दिखाना चाहिए। जैसे ही कोई ऑर्डर तैयार हो और भेज दिया जाए, कतार में अगला ऑर्डर दिखना चाहिए।

हम उपर्युक्त आवश्यकताओं को ऐसे डेटा स्ट्रक्चर की ज़रूरत के रूप में समझ सकते हैं जो निम्नलिखित ऑपरेशंस को सपोर्ट करे:

1. तत्त्व जोड़ना।
2. सबसे पहले जोड़े गए तत्त्व को देखना।
3. सबसे पहले जोड़े गए तत्त्व को हटाना।

ये ऑपरेशंस ठीक वही हैं जो queue उपलब्ध कराती है। Queue को linked list से इम्प्लीमेंट किया जा सकता है, जहाँ तत्त्वों को सूची में append करके जोड़ा जाता है। चूँकि तत्त्व आगमन समय के आधार पर क्रम में होते हैं, पहला नोड हमेशा वह होता है जिसे अगला सर्व किया जाना चाहिए।

ऊपर दिए गए ऑर्डर्स को queue में इस तरह संग्रहीत किया जाएगा:

जब कोई ऑर्डर तैयार हो जाए, तो पहले तत्त्व को उसके next_node पर अपडेट करके हटाया जा सकता है, बशर्ते अगला नोड मौजूद हो। नया पहला नोड, दूसरा नोड बन जाता है:

Queues को पहले आया, पहले गया (FIFO) डेटा स्ट्रक्चर कहा जाता है क्योंकि जो तत्त्व सबसे पहले जोड़ा गया, वही सबसे पहले हटाया जाता है। हमारे रेस्टोरेंट के उदाहरण में, जो ग्राहक सबसे पहले आता है, वही सबसे पहले सर्व होता है (और शेफ की सूची से हट जाता है)।

Python में queue उपयोग करने के लिए हम collections मॉड्यूल से deque कलेक्शन का उपयोग कर सकते हैं। इस मॉड्यूल को इम्पोर्ट करें और नीचे दिखाए अनुसार एक खाली queue बनाएँ:

from collections import deque
orders = deque()संचालित द्वारा

Queue के पीछे नया तत्त्व जोड़ने के लिए .append() मेथड का उपयोग करें:

orders.append("burger")
orders.append("sunday")
orders.append("fries")संचालित द्वारा

Queue के सामने से अगला ऑर्डर निकालने और हटाने के लिए हम .popleft() मेथड का उपयोग करते हैं:

orders.append("burger")
orders.append("sunday")
orders.append("fries")संचालित द्वारा

burger
sunday
friesसंचालित द्वारा

Stacks

कुछ स्थितियों में, हमें queue के विपरीत व्यवहार चाहिए—यानी हम सबसे हाल ही में जोड़े गए तत्त्व पर नज़र रखना चाहते हैं।

उदाहरण के लिए, मान लीजिए आपको एक इमेज एडिटर में undo फीचर जोड़ने का काम दिया गया है। इसके लिए उपयोगकर्ता की क्रियाओं को ट्रैक करने की विधि चाहिए, ताकि सबसे हाल की ऑपरेशंस तक पहुँच मिल सके। ऐसा इसलिए क्योंकि undo आमतौर पर आखिरी की गई क्रिया से शुरू होकर पहली तक उलटता जाता है।

Stack ठीक वही डेटा स्ट्रक्चर है जो इन ऑपरेशंस को सपोर्ट करता है:

1. तत्त्व जोड़ना।
2. सबसे आखिरी जोड़े गए तत्त्व को देखना।
3. सबसे आखिरी जोड़े गए तत्त्व को हटाना।

Queues की तरह, stacks को भी linked list से इम्प्लीमेंट किया जा सकता है। तत्त्व जोड़ना अब भी सूची में append करके होता है। लेकिन हमारी रुचि पहले के बजाय सूची के आखिरी तत्त्व में होती है। सबसे हाल का तत्त्व प्राप्त करने के लिए हम सूची के आखिरी तत्त्व को देखते हैं। आखिरी तत्त्व हटाने के लिए हमें वही तत्त्व हटाना होता है।

हमारी नोड संरचना में अभी तक केवल अगले नोड का ट्रैक था। आखिरी तत्त्व हटाने के लिए हमें उससे पहले वाले तत्त्व तक पहुँचना, उसके next_node को हटाना, और उसे नया आखिरी बनाना होगा। इसे संभव करने के लिए हम नोड संरचना में प्रत्येक नोड के पिछले नोड को भी ट्रैक करने का प्रावधान कर सकते हैं। ऐसी linked list को doubly linked list कहा जाता है।

Stacks को last-in, first-out (LIFO) डेटा स्ट्रक्चर कहा जाता है क्योंकि जो तत्त्व सबसे बाद में जोड़ा गया, वही सबसे पहले हटाया जाता है।

Python में stack उपयोग करने के लिए हम वही deque कलेक्शन इस्तेमाल कर सकते हैं। नए तत्त्व जोड़ने के लिए .append() मेथड का उपयोग करें:

from collections import deque
actions = deque()

actions.append("crop")
actions.append("desaturate")
actions.append("resize")संचालित द्वारा

Stack के शीर्ष से अगला तत्त्व प्राप्त करने और हटाने के लिए हम .pop() मेथड का उपयोग करते हैं:

print(actions.pop())
print(actions.pop())
print(actions.pop())संचालित द्वारा

resize
desaturate
cropसंचालित द्वारा

रैखिक बनाम गैर-रैखिक डेटा स्ट्रक्चर्स

अब तक, हमने पाँच डेटा स्ट्रक्चर्स देखे: arrays, array lists, linked lists, queues, और stacks। ये सभी रैखिक डेटा स्ट्रक्चर्स हैं क्योंकि उनके तत्त्व एक क्रम में व्यवस्थित होते हैं, जहाँ प्रत्येक तत्त्व का एक स्पष्ट पूर्ववर्ती और अनुवर्ती तत्त्व होता है।

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

यह विशेषता उन्हें डेटा पर विशेष क्वेरियों को उच्च दक्षता से निष्पादित करने के लिए उपयुक्त बनाती है, न कि केवल मेमोरी में डेटा संग्रहीत करने के साधन के रूप में।

Hash tables

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

इस डेटा स्ट्रक्चर को समझने के लिए, देखें कि हम एक वर्चुअल डिक्शनरी कैसे बना सकते हैं—अर्थात ऐसा डेटा स्ट्रक्चर जहाँ हम:

1. किसी शब्द पर उसकी परिभाषा जोड़ सकें।
2. दिए गए शब्द पर उसकी परिभाषा देख सकें।

दिसंबर भर के तापमान रिकॉर्ड करने के उदाहरण को याद करें। हमने महीने के प्रत्येक दिन के अनुरूप 31 तत्त्वों वाला एक array उपयोग किया, ताकि तापमान संबंधित इंडेक्स पर संग्रहीत हो सकें। यह तरीका किसी भी दिन का तापमान कुशलता से देखने की अनुमति देता है।

यह परिदृश्य डेटा युग्मों (day, temperature) से निपटने जैसा है, जहाँ उद्देश्य day देकर temperature प्राप्त करना है। इसी तरह, डिक्शनरी के मामले में, हम (word, definition) युग्मों के साथ काम करते हैं और word दिए जाने पर definition ढूँढ़ना चाहते हैं।

ऐसे युग्मों को key-value pairs या entries कहा जाता है। key वह पैरामीटर है जिसका उपयोग लुकअप क्वेरी में होता है, और value उस क्वेरी का परिणाम होता है।

हमें डिक्शनरी समस्या के लिए array उपयोग करने से जो बाधा आती है, वह यह है कि हमारी keys संख्याएँ न होकर स्ट्रिंग्स हैं। संख्यात्मक keys होने पर हम सीधे array का उपयोग करके keys और values को उनके संबंधित इंडेक्स पर रख सकते थे।

इस समस्या को हल करने के लिए, पहले हमें शब्दों को संख्याओं में बदलना होगा। जो फ़ंक्शन यह रूपांतरण करता है उसे hash function कहा जाता है। ऐसे फ़ंक्शन बनाने के कई तरीके हैं। उदाहरण के लिए, हम अक्षरों को संख्यात्मक मान दे सकते हैं—a को 1, b को 2, c को 3, और इसी तरह—फिर इन मानों का योग लें।

उदाहरण के लिए, data शब्द के लिए 4 + 1 + 20 + 1 = 26 होगा। हालाँकि, इस फ़ंक्शन की कमियाँ हैं, जिन पर हम आगे चर्चा करेंगे। एक प्रभावी hash function कैसे बनाया जाए, यह इस लेख के दायरे से बाहर है, पर Python सुविधाजनक रूप से hash() फ़ंक्शन देता है जो यह काम कुशलता से करता है।

hash("data")संचालित द्वारा

-6138587229816301269संचालित द्वारा

ऊपर के उदाहरण में, आपने देखा होगा कि hash फ़ंक्शन ने ऋणात्मक संख्या दी। यह ध्यान देने योग्य है कि array के धनात्मक इंडेक्स 0 से N - 1 तक होते हैं। जब हमने keys को संख्याओं में बदल लिया, तो हम modulo ऑपरेटर % का उपयोग करके उन्हें 0 से N - 1 की रेंज में मैप कर सकते हैं (जो भागफल का शेष देता है—उदाहरण के लिए, 10 % 3 का परिणाम 1 होता है)।

ध्यान रहे, Python का hash() फ़ंक्शन विभिन्न प्रोग्राम निष्पादनों में अलग-अलग मान दे सकता है। यह केवल एक ही प्रोग्राम रन के भीतर निर्धारक (deterministic) होता है, यानी प्रोग्राम को कई बार चलाने पर आप एक ही ऑब्जेक्ट के लिए अलग-अलग hash मान देख सकते हैं।

मान लीजिए एक array में 100 तत्त्व हैं। स्ट्रिंग "data" के अनुरूप इंडेक्स खोजने के लिए हम ऐसे आगे बढ़ेंगे:

hash("data") % 100संचालित द्वारा

31संचालित द्वारा

Hash table डेटा स्ट्रक्चर मूलतः एक बड़ा array है जो key-value pairs को उन इंडेक्सों पर संग्रहीत करता है जो keys पर hash फ़ंक्शन लगाने से निर्धारित होते हैं।

स्थान की कमी के कारण, ऊपर के डायग्राम में परिभाषा को दर्शाने के लिए केवल "def" संक्षेप का उपयोग किया गया है। व्यवहार में, प्रत्येक एंट्री का दूसरा तत्त्व उस शब्द की पूरी परिभाषा होगा।

एक और महत्वपूर्ण पहलू पर विचार करना ज़रूरी है। चूँकि 100 से कहीं अधिक शब्द हैं, यदि हम शब्द जोड़ते चले जाएँ, तो अलग-अलग शब्द अंततः एक ही hash मान देंगे। इसे हल करने के लिए, प्रत्येक array तत्त्व को एक ही key-value pair तक सीमित करने के बजाय, हम उसी hash मान को साझा करने वाली सभी एंट्रीज़ संग्रहीत करने के लिए linked list का उपयोग करते हैं।

जब दो एंट्रीज़ एक ही hash उत्पन्न करती हैं, तो इसे collision कहा जाता है। यह स्थिति लुकअप प्रक्रिया को थोड़ा बदल देती है। Hash कोड की गणना के बाद, सही एंट्री ढूँढ़ने के लिए सूची को ट्रैवर्स करना पड़ता है। यद्यपि इससे लुकअप थोड़ा धीमा हो जाता है, लेकिन यह दिखाया जा सकता है कि पर्याप्त बड़े प्रारंभिक array आकार (100 से बड़ा) और एक अच्छे hash फ़ंक्शन के साथ collisions के प्रभाव को काफी हद तक कम किया जा सकता है। परिणामस्वरूप, दक्षता लगभग array के समान रहती है।

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

Hash tables arguably सबसे महत्वपूर्ण डेटा स्ट्रक्चर हैं। ये अत्यंत कुशल और बहुपयोगी हैं। Python में इन्हें dict() क्लास के माध्यम से इम्प्लीमेंट किया गया है। डिक्शनरी जैसी समानता के कारण, Python में इस डेटा स्ट्रक्चर को hash table के बजाय dictionary ही कहा जाता है।

सरलता के लिए, हमारे उदाहरण में जोड़ना और लुकअप करना केंद्र में है। सामान्यतः, डिक्शनरी अधिक लचीलापन देती हैं और deletion सहित अतिरिक्त ऑपरेशंस सपोर्ट करती हैं। Python में खाली डिक्शनरी (hash table) बनाने के लिए आप {} का उपयोग ऐसे कर सकते हैं:

word_definitions = {}
word_definitions["data"] = "Facts or information."संचालित द्वारा

आप किसी शब्द की परिभाषा तक शब्द को key के रूप में देकर पहुँच सकते हैं, जैसे:

print(word_definitions["data"])संचालित द्वारा

Facts or information.संचालित द्वारा

Trees

कल्पना कीजिए कि आप किसी रियल एस्टेट एजेंसी की वेबसाइट विकसित कर रहे हैं। आपका काम एक ऐसा फीचर बनाना है जो उपयोगकर्ताओं को कीमत के आधार पर लिस्टिंग फ़िल्टर करने दे। इस फीचर को उपयोगकर्ताओं को ये करने देना चाहिए:

1. सबसे सस्ती लिस्टिंग ढूँढ़ना।
2. सबसे महँगी लिस्टिंग ढूँढ़ना।
3. किसी दी गई कीमत से कम वाली सभी लिस्टिंग ढूँढ़ना।

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

Trees भी नोड-आधारित डेटा स्ट्रक्चर हैं, जैसे linked lists। परंतु पिछले और अगले रेफरेंस के बजाय, प्रत्येक नोड एक मान और दो रेफरेंस रखेगा: एक बाएँ नोड का और एक दाएँ नोड का।

हमारे रियल एस्टेट वेबसाइट के उदाहरण में, प्रत्येक नोड एक प्रॉपर्टी लिस्टिंग का प्रतिनिधित्व करेगा। कीमत-संबंधी क्वेरियों को अनुकूलित करने के लिए, हम एक नियम स्थापित करेंगे: कम कीमत वाली लिस्टिंग हमेशा किसी नोड के बाएँ रखी जाएँगी, और अधिक कीमत वाली दाएँ।

एक ठोस उदाहरण के लिए, निम्नलिखित tree पर विचार करें जिसमें 42, 17, 73, 4, 22, और 89 मान हैं।

प्रत्येक नोड के लिए, बाएँ के सभी नोड्स के मान छोटे हैं और दाएँ के सभी नोड्स के मान बड़े हैं। ऐसा tree जो इस गुण को संतुष्ट करता है, binary search tree (BST) कहलाता है। इसे binary इसलिए कहते हैं क्योंकि प्रत्येक नोड अधिकतम दो अन्य नोड्स (children) को संदर्भित करता है। search भाग इस तथ्य से आता है कि बाएँ और दाएँ बच्चों पर यह क्रमबद्धता tree में कुशलतापूर्वक खोज करने में संभव बनाती है।

हम पहले ही देख सकते हैं कि BST सबसे सस्ती और सबसे महँगी लिस्टिंग्स जल्दी ढूँढ़ने में कैसे मदद करता है। मानों के क्रम के कारण, सबसे सस्ती हमेशा सबसे बाएँ नोड और सबसे महँगी हमेशा सबसे दाएँ नोड होती है।

इसका अर्थ है कि हम अधिकांश डेटा की जाँच किए बिना उन्हें ढूँढ़ सकते हैं। शीर्ष नोड, जिसे root नोड भी कहा जाता है, से शुरू करके, हम न्यूनतम के लिए लगातार बाएँ लिंक्स और अधिकतम के लिए दाएँ लिंक्स का पालन करते हैं। यानी केवल वे नोड्स देखे जाने चाहिए जो root से क्रमशः न्यूनतम और अधिकतम नोड तक के पथ पर हों।

मान लीजिए हम उन सभी नोड्स को ढूँढ़ना चाहते हैं जिनका मान कम से कम 50 है। इसे पूरा करने के लिए ये कदम उठाए जा सकते हैं:

• root से शुरू करते हुए, हम अपने लक्ष्य 50 की तुलना root के मान 42 से करते हैं।
• चूँकि 50 बड़ा है, हम समझते हैं कि root और उसके बाएँ के सभी नोड्स के मान छोटे हैं। इसलिए, हम उन्हें नज़रअंदाज़ कर सकते हैं।
• फिर हम root के दाएँ नोड 73 पर बढ़ते हैं। तुलना करने पर पाते हैं कि 50 73 से छोटा है। यह इंगित करता है कि नोड 73 के दाएँ के सभी नोड्स हमारी शर्त पूरी करते हैं।
• हालाँकि, चूँकि 73 का कोई बायाँ child नहीं है, हमारी खोज वहीं समाप्त होती है।

हम देख सकते हैं कि BSTs क्वेरियों को काफी तेज कर सकते हैं। इस छोटे से उदाहरण में भी हमने आधे डेटा की जाँच से बचाव किया।

आम तौर पर, किसी दी गई रेंज में फिट होने वाले BST के सभी नोड्स की पहचान करने के लिए उतने ही नोड्स की जाँच करनी पड़ती है जो क्वेरी परिणामों की संख्या के क़रीब होते हैं। यह हर डेटा पॉइंट की जाँच करने की तुलना में बहुत बड़ा लाभ है। मान लीजिए 1,000,000 लिस्टिंग्स हैं और क्वेरी केवल 10 परिणाम देती है। एक लिस्ट का उपयोग करते हुए, रेंज से बाहर वाली लिस्टिंग्स को फ़िल्टर करने के लिए दस लाख लिस्टिंग्स की जाँच करनी पड़ेगी। BST के साथ, लगभग 10 लिस्टिंग्स की ही जाँच करनी पड़ेगी। यह 100,000 गुना की स्पीडअप दर्शाता है।

BST की दक्षता tree के संतुलन (balance) पर बहुत निर्भर करती है। यदि हम पहले जैसे ही मान छोटे से बड़े क्रम में जोड़ें—4, 17, 22, 42, 73, और फिर 89—तो हमें नीचे दिखाए अनुसार एक असंतुलित tree मिल सकता है:

याद करें, BST में अधिकतम मान ढूँढ़ने के लिए हम root से शुरू कर दाएँ लिंक्स का अनुसरण तब तक करते हैं जब तक कोई ऐसा नोड न मिल जाए जिसका दायाँ child न हो। ऊपर दिखाए असंतुलित tree के मामले में, यह प्रक्रिया हर एक नोड की जाँच करने को बाध्य करती है। आदर्श रूप से, हम चाहते हैं कि नोड्स बाएँ और दाएँ तरफ बराबरी से वितरित हों। यह संतुलन कैसे लगातार बनाए रखा जाए, इसकी बारीकियों का विवरण इस लेख के दायरे से बाहर है। ऐसा एक binary search tree जो ऐसा संतुलन बनाए रखता है, उसे AVL tree कहते हैं।

avltree पैकेज AVL tree का इम्प्लीमेंटेशन देता है। नीचे दिया कोड स्निपेट दिखाता है कि हम इसे इस हाउस लिस्टिंग डेटासेट—जो USA Real Estate Dataset का एक साफ़ subset है—पर कैसे उपयोग कर सकते हैं।

import csv
from avltree import AvlTree as Tree

# Load the listings CSV data
with open("listings.csv", "rt") as f:
    reader = csv.reader(f)
    listings = list(reader)

# Create the tree based on the price column (column index 2)
tree = Tree()
for listing in listings[1:]:
    price = float(listing[2])
    tree[price] = listing

# Display the cheapest listing price
print("Cheapest:", tree.minimum())

# Display the most expensive listing price
print("Most expensive:", tree.maximum())

# Display the number of listings whose price is between 100,000 and 110,000
listings_in_range = list(tree.between(100000, 110000))
print("Num listings between 100000 and 110000:", len(listings_in_range))संचालित द्वारा

Cheapest: 50017.0
Most expensive: 19999900.0
Num listings between 100000 and 110000: 403संचालित द्वारा

पहले हम csv मॉड्यूल का उपयोग करके listings.csv डेटासेट पढ़ते हैं। इसके बाद हम कीमत वाले कॉलम के आधार पर एक AVL tree बनाते हैं। फिर minimum(), maximum() और between() मेथड्स का उपयोग कर न्यूनतम कीमत, अधिकतम कीमत, और $100,000 से $110,000 के बीच कीमत वाली लिस्टिंग्स की संख्या निकालते हैं।

Graphs

अंतिम डेटा स्ट्रक्चर जिसके बारे में हम इस लेख में चर्चा करेंगे, वह graph है।

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

जब हमारे पास एंटिटीज़ और उनकी जोड़ीदार (pairwise) रिलेशनशिप्स हों, तो graphs डेटा को निरूपित करने के लिए आदर्श डेटा स्ट्रक्चर होते हैं। हमारे उदाहरण में, एंटिटीज़ उपयोगकर्ता हैं और रिश्ते उनकी दोस्तियाँ हैं।

Graphs नोड-आधारित संरचनाएँ हैं। लेकिन linked lists और trees के विपरीत, जो नोड्स के बीच रैखिक या पदानुक्रमित कनेक्शन दर्शाते हैं, एक graph में कोई भी नोड कई अन्य नोड्स से जुड़ सकता है। नोड्स के बीच ये कनेक्शन, जिन्हें edges कहा जाता है, उनके बीच के रिश्ते दर्शाते हैं।

हमारे सोशल नेटवर्क उदाहरण में, प्रत्येक उपयोगकर्ता को एक नोड के रूप में देखा जा सकता है। दो नोड्स के बीच एक edge खींचकर संबंधित उपयोगकर्ताओं के बीच दोस्ती को इंगित किया जा सकता है।

ऊपर का डायग्राम एक छोटे सोशल नेटवर्क के भीतर दोस्तियों का प्रतिनिधित्व करने वाला graph दिखाता है। नोड्स उपयोगकर्ताओं का प्रतिनिधित्व करते हैं और उनके नामों से लेबल्ड हैं, जबकि edges दोस्तियों को दर्शाते हैं। उदाहरण के लिए, Anna की Steve, Claire, और Jack से दोस्ती है, जिसका अर्थ है कि उसके नोड से इन व्यक्तियों के नोड्स तक edges जुड़े हैं।

Graph डेटा स्ट्रक्चर को जिन ऑपरेशंस को सपोर्ट करना चाहिए, उनमें शामिल हैं:

1. नया नोड जोड़ना।
2. दो नोड्स को एक edge से जोड़ना।
3. किसी विशिष्ट नोड से जुड़े सभी नोड्स प्राप्त करना।

Graph को इम्प्लीमेंट करने का एक आम तरीका hash table और lists का उपयोग करना है। प्रत्येक नोड के लिए एक एंट्री के साथ एक hash table बनाया जाता है। प्रत्येक एंट्री की key नोड होता है, और value उस नोड से जुड़े सभी नोड्स की सूची होती है।

networkx पैकेज graphs बनाने और उन्हें प्रबंधित करने के लिए Python इम्प्लीमेंटेशन प्रदान करता है। इसके अतिरिक्त, networkx लाइब्रेरी में ग्राफ एल्गोरिद्म्स की एक विस्तृत श्रृंखला शामिल है, जिनमें कम्युनिटी डिटेक्शन के एल्गोरिद्म भी आते हैं। आइए ऊपर बताए गए graph का निर्माण करें और एक प्रचलित कम्युनिटी डिटेक्शन एल्गोरिद्म लागू कर परिणाम देखें।

Graph बनाना शुरू करने के लिए, पहले हम networkx लाइब्रेरी इम्पोर्ट कर एक खाली graph इनिशियलाइज़ करेंगे:

import networkx as nx
G = nx.Graph()संचालित द्वारा

नोड्स को add_node() मेथड से जोड़ा जा सकता है।

G.add_node("Anna")
G.add_node("Steve")
G.add_node("Jack")
G.add_node("Claire")
G.add_node("Bob")
G.add_node("Jane")
G.add_node("John")
G.add_node("Rute")
G.add_node("Alex")संचालित द्वारा

Edges को add_edge() मेथड से जोड़ा जा सकता है।

G.add_edge("Anna", "Steve")
G.add_edge("Anna", "Jack")
G.add_edge("Anna", "Claire")
G.add_edge("Steve", "Claire")
G.add_edge("Claire", "Jack")
G.add_edge("Jack", "Bob")
G.add_edge("Bob", "John")
G.add_edge("Bob", "Jane")
G.add_edge("John", "Jane")
G.add_edge("Rute", "Alex")संचालित द्वारा

Graph बन जाने के बाद, हम उसके भीतर की communities की गणना कर सकते हैं। कम्युनिटी डिटेक्शन के कई एल्गोरिद्म्स हैं, और इस उदाहरण में हम Louvain मेथड का उपयोग करेंगे। कम्युनिटी डिटेक्शन एल्गोरिद्म्स networkx के community सबपैकेज में मिलते हैं। विशेष रूप से, हम louvain_communities() फ़ंक्शन पर ध्यान देंगे।

इसे उपयोग करने का तरीका इस प्रकार है:

communities = nx.community.louvain_communities(G)
print(communities)संचालित द्वारा

[{'Jack', 'Claire', 'Anna', 'Steve'}, {'Bob', 'John', 'Jane'}, {'Rute', 'Alex'}]संचालित द्वारा

आउटपुट sets की एक सूची है, जहाँ प्रत्येक set एक कम्युनिटी का प्रतिनिधित्व करता है। हम देखते हैं कि एल्गोरिद्म ने तीन कम्युनिटीज़ का पता लगाया है, जो graph की संरचना के अनुसार हमारी अपेक्षाओं से मेल खाता है।

Graphs के बारे में और जानने के लिए, पायथन में डायक्सट्रा (Dijkstra) एल्गोरिद्म इम्प्लीमेंट करना सीखें।

उचित डेटा स्ट्रक्चर कैसे चुनें

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

उदाहरण के लिए, Python की list() अतिरिक्त ऑपरेशंस, जैसे तत्त्व हटाना, भी सपोर्ट करती है। हालाँकि, ये अतिरिक्त ऑपरेशंस array list की विशेषता नहीं हैं। विशेष रूप से, सूची के बीच से तत्त्व हटाने पर पूरे डेटा (हटाए गए तत्त्व को छोड़कर) को एक नई सूची में कॉपी करना पड़ता है, जो समय लेने वाला हो सकता है।

जब डेटा स्वाभाविक रूप से संख्याओं द्वारा इंडेक्स्ड हो और एंट्रीज़ की संख्या ज्ञात हो (जैसे, महीने के दिन), तो आम तौर पर array पसंदीदा विकल्प होता है। अधिक सामान्य इंडेक्सिंग या गतिशील डेटा सेट के लिए, dictionaries एक अच्छा वैकल्पिक समाधान हैं।

डेटा को अनुक्रमिक रूप से, एक बार में एक एंट्री प्रोसेस करने के लिए, इच्छित प्रोसेसिंग क्रम के अनुसार queues या stacks का उपयोग किया जाता है।

जब हम डेटा पर अधिक जटिल क्वेरियाँ करना चाहें—जैसे किसी रेंज में आने वाली सभी एंट्रीज़ या चरम (extremes) ढूँढ़ना—तो trees आमतौर पर उत्तर होते हैं।

अंत में, जब डेटा पॉइंट्स की जोड़ी के बीच संबंध हों, तो उन संबंधों को संग्रहीत और निरूपित करने का प्रभावी तरीका graph है। ऐसे pairwise संबंधों वाले डेटासेट्स पर सामान्य प्रश्नों के उत्तर देने के लिए कई ग्राफ एल्गोरिद्म्स उपलब्ध हैं।

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

निष्कर्ष

इस लेख में, हमने सीखा कि डेटा स्ट्रक्चर्स डेटा को विशिष्ट प्रारूपों में व्यवस्थित करने की विधियाँ हैं, जिससे सूचना पुनर्प्राप्ति कुशलता से हो सके।

डेटा स्ट्रक्चर्स के दो मौलिक प्रकार होते हैं: array-आधारित (उदाहरण के लिए, hash tables) और node-आधारित (उदाहरण के लिए, graphs) संरचनाएँ।

रैखिक संरचनाएँ, जैसे arrays, queues, और stacks, तत्त्वों को अनुक्रम में, एक के बाद एक व्यवस्थित करती हैं। इसके विपरीत, गैर-रैखिक संरचनाएँ, जैसे hash tables, trees, और graphs, डेटा के भीतर मौजूद संबंधों के आधार पर डेटा को व्यवस्थित करती हैं।

उचित डेटा स्ट्रक्चर का चुनाव इस बात पर निर्भर करता है कि कौन-सी क्वेरियाँ की जानी हैं।

यदि आप Python में विभिन्न डेटा स्ट्रक्चर्स के बारे में सीखना चाहते हैं, तो Python डेटा स्ट्रक्चर्स पर यह ट्यूटोरियल देखें।