Theory
एक सवाल, दो shapes
Canteen जो दो records रखता है:
- आज की token list: 1, 2, 3, 4... हर token के exactly इसके पहले एक और बाद एक है।
- Menu board: Menu Snacks, Meals, Drinks में split होता है; Meals तीन thalis में split होता है।
"इसके बाद क्या आता है?" पूछिए। Token list एक जवाब देती है। Menu तीन देता है।
यही अकेला फ़र्क़, एक successor या कई, सभी non-primitive data structures की official dividing line है।
Theory
एक queue बनाम एक family tree
Serving line में, आपके exactly एक व्यक्ति आगे और एक पीछे है: pure sequence।
आपके family tree में, आपके grandfather कई children से जुड़ते हैं, हर एक कई और से जुड़ता है: pure branching।
कोई भी family को queue की तरह नहीं draw करता, और कोई भी customers को family tree से serve नहीं करता। Structures shapes हैं, और shapes को उन relationships से match होना चाहिए जो वे रखते हैं।
Theory
दोनों families, formally
Linear data structure: elements एक single sequence बनाते हैं। हर element (पहले और आख़िरी को छोड़कर) के exactly एक predecessor और एक successor है। आप सब कुछ एक straight pass में traverse कर सकते हैं।
Examples: array, stack, queue, linked list।
Non-linear data structure: elements hierarchically या एक network के रूप में जुड़ते हैं; एक element कई दूसरों से जुड़ सकता है। Traversal को एक strategy चाहिए (कौन सी branch पहले?)।
Examples: tree, graph।
At a glance
Exam table
| Aspect | Linear | Non-linear |
|---|---|---|
| Arrangement | Single sequence | Hierarchy या network |
| Neighbours | एक predecessor, एक successor | एक element, कई connections |
| Traversal | एक straight pass | एक strategy चाहिए (DFS, BFS) |
| Implementation | Simpler | ज़्यादा complex |
| Examples | Array, stack, queue, linked list | Tree, graph |
| Typical use | Token lists, undo, schedules | File systems, maps, networks |
Quiz
कौन सा group सिर्फ़ linear data structures रखता है?
- Array, linked list, stack, queue
- Array, tree, stack, queue
- Stack, queue, graph, array
- Tree, graph, linked list, array
Show the answer
Array, linked list, stack, queue
चारों linear structures exactly array, linked list, stack और queue हैं: हर एक एक sequence रखता है। बाक़ी हर option एक tree या एक graph smuggle करता है, दोनों non-linear members। Examiners इस सवाल को एक branching structure को एक linear list के अंदर छुपाकर बनाते हैं; tree/graph scan कीजिए और ग़लत options ख़ुद eliminate हो जाते हैं।
Think first
Tricky case
एक student एक tree को एक array के अंदर store करता है (parent index i पर, children 2i और 2i+1 पर, classic heap layout)। Data अब एक linear array में बैठा है। tap करने से पहले: structure linear है या non-linear, और क्यों?
Show the answer
Non-linear। Classification logical relationships follow करता है, storage medium नहीं: हर parent के अभी भी दो तक children हैं, तो elements के अभी भी कई successors हैं। Array बस वह shelf है जिस पर यह रखा है। यह distinction (logical structure बनाम physical storage) बिल्कुल वह trap है जो exams इस सवाल से set करते हैं, और बाद के semesters में heaps इस पर टिकते हैं।
Watch out
दो classification slips
Linked list branchy लगती है diagrams में arrows की वजह से, पर हर node exactly ONE next node को point करता है: linear।
एक array में stored एक tree non-linear ही रहता है (ऊपर देखिए)। वह test जो कभी fail नहीं होता: एक element के हो सकते successors गिनिए। ज़्यादा से ज़्यादा एक: linear। शायद कई: non-linear। Lists memorize करने के बजाय test apply कीजिए और कोई भी rephrased exam सवाल आपको हिला नहीं सकता।
Theory
आगे यह split क्यों matter करता है
BCA304 में बाक़ी बचा सब कुछ (stack applications, तीन flavours में queues) linear side पर रहता है: अभी sequences master कीजिए। Non-linear side (trees, graphs) बाद के semesters में databases, file systems और Google-Maps-style routing लेकर आता है। जो one-successor test आपने आज सीखा वह वहाँ भी काम करता रहता है।
Summary
Key takeaways
- Linear: एक sequence, हर element के ज़्यादा से ज़्यादा एक predecessor और एक successor।
- Non-linear: hierarchy या network, एक element कई से जुड़ सकता है।
- Linear members: array, stack, queue, linked list। Non-linear: tree, graph।
- Traversal: एक straight pass बनाम strategy-based (DFS/BFS)।
- Classification logical relationships follow करता है, data physically कैसे stored है वह नहीं।
- Memory hook: serving line बनाम family tree।