डेटा संरचना क्या है?
डेटा संरचना डेटा को रखने और व्यवस्थित करने का तरीका है ताकि उसे खोजना, जोड़ना, हटाना और क्रम में लगाना आसान हो।
- आदिम (primitive) डेटा प्रकार एक मान रखते हैं: पूर्णांक, दशमलव, अक्षर, बूलियन।
- अनादिम (non-primitive) संरचनाएँ कई मान रखती हैं: ऐरे, लिस्ट, स्टैक, क्यू, ट्री, ग्राफ़।
- रेखीय (linear) संरचनाएँ चीज़ों को एक क्रम में रखती हैं (ऐरे, लिस्ट, स्टैक, क्यू)। अरेखीय संरचनाएँ शाखाओं में बँटती हैं (ट्री, ग्राफ़)।
- स्थिर (static) संरचना का आकार तय होता है (साधारण ऐरे)। गतिशील (dynamic) संरचना प्रोग्राम चलते हुए बढ़-घट सकती है (लिंक्ड लिस्ट, Python लिस्ट)।
अमूर्त डेटा प्रकार (ADT) बताता है कि संरचना क्या करती है (उसके ऑपरेशन), यह नहीं कि कैसे बनी है। स्टैक ADT push, pop, peek और isEmpty का वादा करता है; उसे ऐरे से भी बना सकते हैं और लिंक्ड लिस्ट से भी।
ऐरे, रिकॉर्ड, टपल और लिस्ट
ऐरे एक ही प्रकार की चीज़ों को मेमोरी के पास-पास डिब्बों में रखता है। हर डिब्बे का सूचकांक (index) होता है, जो प्रायः 0 से शुरू होता है। डिब्बे साथ-साथ हैं, इसलिए कंप्यूटर A[i] पर एक कदम में पहुँचता है। पर बीच में डालने के लिए बाद की सब चीज़ें खिसकानी पड़ती हैं।
2D ऐरे एक ग्रिड है, जैसे तालिका या शतरंज: M[row][col]। स्ट्रिंग अक्षरों का ऐरे है।
रिकॉर्ड एक चीज़ के अलग-अलग प्रकार के डेटा को साथ रखता है, जैसे विद्यार्थी: नाम (टेक्स्ट), रोल नंबर (पूर्णांक), अंक (दशमलव)। हर हिस्सा एक फ़ील्ड है। फ़ाइल कई रिकॉर्ड डिस्क पर स्थायी रूप से रखती है।
Python में लिस्ट [3, 8, 5] बढ़ने वाला ऐरे है; टपल (3, 8, 5) बनने के बाद बदला नहीं जा सकता।
लिंक्ड लिस्ट नोड्स की ज़ंजीर है। हर नोड में एक मान और अगले नोड का पॉइंटर होता है; आख़िरी null की ओर। पहला नोड head है। डालने या हटाने में सिर्फ़ पॉइंटर बदलते हैं, कुछ खिसकता नहीं; पर 100वीं चीज़ तक पहुँचने के लिए 99 नोड से गुज़रना पड़ता है।
स्टैक और क्यू
स्टैक LIFO है: अंतिम आया, पहले गया। सिर्फ़ top को छूते हैं।
push(x)x को ऊपर रखता है;pop()ऊपर वाला हटाकर लौटाता है;peek()बिना हटाए ऊपर वाला देखता है।- ख़ाली स्टैक से pop = अंडरफ़्लो; भरे हुए तय आकार वाले स्टैक में push = ओवरफ़्लो।
- उपयोग: undo, बैक बटन, कोष्ठक की जाँच, और कॉल स्टैक जो याद रखता है किस फ़ंक्शन में लौटना है।
रिवर्स पोलिश नोटेशन (RPN) में ऑपरेटर संख्याओं के बाद लिखते हैं: 3 4 + यानी 3 + 4। स्टैक से हल करते हैं: संख्या आए तो push; ऑपरेटर आए तो दो pop करो, हिसाब करो, नतीजा push करो। RPN में कोष्ठक नहीं चाहिए।
क्यू FIFO है: पहले आया, पहले गया। चीज़ें rear (पीछे) से जुड़ती हैं (enqueue) और front (आगे) से निकलती हैं (dequeue)। उपयोग: प्रिंटर के काम, कीबोर्ड बफ़र, ग्राहक सेवा की लाइन, CPU के इंतज़ार वाले काम। वृत्ताकार क्यू तय ऐरे की शुरू की ख़ाली जगह फिर इस्तेमाल करता है, और प्राथमिकता क्यू ज़रूरी चीज़ों को पहले जाने देता है।
डिक्शनरी, ट्री और ग्राफ़
डिक्शनरी (मैप, हैश टेबल) कुंजी → मान जोड़े रखती है, जैसे {"Asha": 9876, "Ravi": 9123}। मान उसकी कुंजी से मिलता है, स्थान से नहीं। हैश फ़ंक्शन कुंजी को डिब्बा नंबर में बदलता है, इसलिए खोज बहुत तेज़ है।
ट्री डेटा को स्तरों में रखता है। सबसे ऊपर का नोड root, नीचे वाले child, जिनके बच्चे नहीं वे leaf। बाइनरी ट्री में हर नोड के अधिकतम दो बच्चे होते हैं।
बाइनरी सर्च ट्री (BST) में बाएँ उप-ट्री के सब मान नोड से छोटे और दाएँ के सब बड़े होते हैं। खोजने के लिए तुलना करो और बाएँ या दाएँ जाओ; हर कदम बचे हुए लगभग आधे मान छोड़ देता है, इसलिए संतुलित दस लाख चीज़ों में भी करीब 20 तुलनाएँ काफ़ी हैं।
ग्राफ़ शीर्षों (vertices) का समूह है जो किनारों (edges) से जुड़े हैं, कोई तय ऊपर नहीं। नक्शे के रास्ते, सोशल नेटवर्क और इंटरनेट ग्राफ़ हैं।
संरचना चुनना: स्थान से तुरंत पहुँच → ऐरे; बीच में बहुत डालना → लिंक्ड लिस्ट; undo या उलटना → स्टैक; निष्पक्ष इंतज़ार → क्यू; नाम से खोज → डिक्शनरी; तेज़ क्रमबद्ध खोज → BST।
मुख्य सूत्र और परिभाषाएँ
- ऐरे: A[i] सीधे; पहला सूचकांक = 0, आख़िरी = n − 1
- A[i] का पता = आधार पता + i × (एक चीज़ का आकार)
- स्टैक (LIFO): push, pop, peek, isEmpty; ख़ाली से pop = अंडरफ़्लो
- क्यू (FIFO): rear पर enqueue, front से dequeue
- BST नियम: बायाँ < नोड < दायाँ
- RPN: संख्या पर push; ऑपरेटर पर दो pop, हिसाब, नतीजा push
हल किए गए उदाहरण
1. A = [12, 7, 30, 45, 9, 18]। A[3] क्या है और आख़िरी सूचकांक क्या है?
सूचकांक 0 से शुरू, तो A[3] = 45। 6 चीज़ें हैं, तो आख़िरी सूचकांक 6 − 1 = 5।
2. ख़ाली स्टैक। push(4), push(9), push(2), pop(), push(7), pop(), pop()। क्या बचा और क्रम से क्या निकला?
push के बाद [4, 9, 2]। pop → 2। push 7 → [4, 9, 7]। pop → 7। pop → 9। बचा [4]। निकले: 2, 7, 9।
3. ख़ाली क्यू। enqueue(4), enqueue(9), enqueue(2), dequeue(), enqueue(7), dequeue()। क्या बचा?
[4, 9, 2] → dequeue से 4 गया → [9, 2] → enqueue 7 → [9, 2, 7] → dequeue से 9 गया → [2, 7]।
4. स्टैक से RPN व्यंजक 5 3 + 2 × हल करो।
push 5, push 3 → '+' पर 3 और 5 pop, 8 push → push 2 → '×' पर 2 और 8 pop, 16 push। उत्तर 16 (यानी (5 + 3) × 2)।
5. BST (root 50, बायाँ 30 जिसके बच्चे 20, 40; दायाँ 70) में 35 डालो। कहाँ जाएगा?
35 < 50 → बाएँ 30 पर। 35 > 30 → दाएँ 40 पर। 35 < 40 → 40 का बायाँ बच्चा बनेगा।
6. पूर्णांक ऐरे पता 1000 से शुरू होता है और हर पूर्णांक 4 बाइट लेता है। A[5] कहाँ है?
पता = 1000 + 5 × 4 = 1020।
आम गलतियाँ
- ऐरे का सूचकांक 1 से शुरू करना। ज़्यादातर भाषाओं में पहला 0 है, इसलिए आख़िरी n − 1।
- LIFO और FIFO में उलझना। स्टैक = अंतिम आया पहले गया; क्यू = पहले आया पहले गया।
- सोचना कि लिंक्ड लिस्ट में ऐरे जैसी तुरंत पहुँच है। head से नोड-दर-नोड चलना पड़ता है।
- RPN में − और ÷ के लिए pop का क्रम उलटना। पहले pop हुई संख्या दाईं ओर की है: '8 2 −' = 8 − 2 = 6।