Theory
Request Number 101
BookBridge issue requests को एक array में queue करता है:
String[] queue = new String[100];
Exam week आती है। Request 101 आती है, और array full है: Java में, एक array की size birth पर fixed है। Worse, जब पहला request serve होता है, 99 entries को forward shift करना real work है, हर बार।
Queue क्या चाहती है एक बार में एक request grow करना और served वालों को instantly shed करना। Arrays यह नहीं कर सकते। यह unit वह बनाता है जो कर सकता है, बस Java classes से।
Theory
एक Treasure Hunt, Shelf नहीं
एक array numbered slots वाली एक shelf है: slot 47 ढूँढने के लिए आप सीधे वहाँ jump करते हैं, पर shelf की length welded है।
एक linked structure एक treasure hunt है: हर clue एक prize (data) hold करता है और अगले clue के directions। एक direction को rewrite करके कहीं भी एक clue add कीजिए; same तरीके से एक हटाइए। कोई shelf नहीं, कोई welding नहीं, बस clues जो जानते हैं hunt कहाँ जारी रहती है। आख़िरी clue कहता है: hunt खत्म।
Theory
Self-Referential Class
Java में, clue एक class है जो अपनी खुद की type को refer करती है:
class Node {
String title; // the data (one request)
Node next; // reference to the NEXT node
}
Node next को carefully पढ़िए: यह एक reference है, एक address slot, एक Node के अंदर stuffed एक Node नहीं। यही वजह है यह एक infinite Russian doll बनाए बिना compile होता है: object एक दूसरे object के directions hold करता है, object खुद नहीं।
next == null का मतलब है: hunt खत्म, chain का end।
Practical
पहली Chain हाथ से Forge करना
class Node {
String title;
Node next;
Node(String t) { title = t; } // next starts as null (field default)
}
public class IssueQueue {
public static void main(String[] args) {
Node first = new Node("Let Us C");
Node second = new Node("Java Complete Reference");
first.next = second; // one assignment: the chain forms
// second.next is already null: end of the chain
System.out.println(first.title);
System.out.println(first.next.title); // reached VIA the link
}
}
At a glance
Array बनाम Linked Chain
| Aspect | Array | Linked Chain |
|---|---|---|
| Size | Creation पर fixed | एक बार में एक node grow और shrink करती है |
| Front में Insert/Delete | सब कुछ shift कीजिए | 1 या 2 references re-link कीजिए |
| i-th Item तक पहुँचना | Instant: queue[i] | Start से chain walk कीजिए |
| Memory | एक solid block, possibly half empty | Per item exactly एक node, plus link slots |
Think first
Russian-Doll Worry
एक classmate object करता है: "class Node एक Node contain करता है, जो एक Node contain करता है... surely एक new Node("x") एक infinite tower allocate करता है?" Tap करने से पहले: उस picture में क्या ग़लत है?
Show the answer
Field एक reference है, एक embedded object नहीं। new Node("x") ONE node allocate करता है: इसका title slot और एक address-sized next slot, जो null की तरह शुरू होता है (Unit 2 का एक field default)। जब तक आप explicitly एक create और link नहीं करते बाकी कुछ नहीं बनता। BCA304 के C++ में यह struct Node { Node* next; } था: asterisk indirection को visible बनाता था। Java references वही indirection है syntax hidden के साथ, और कोई pointer arithmetic allowed नहीं।
Quiz
Nodes की एक chain में, program को कैसे पता चलता है यह last node पर पहुँच गया?
- इसका next reference null है
- इसकी title field empty है
- Java last node पर एक exception throw करता है
- Node class chain की total length store करती है
Show the answer
इसका next reference null है
next slot में null agreed full stop है: आगे कोई clue नहीं। वह convention आने वाले lessons के हर loop को drive करती है: while (cur != null) एक chain walk करता है, और cur.next == null इसकी tail ढूँढता है। Option B data को structure से confuse करता है; एक request की title position के बारे में कुछ नहीं कहती। Option C वह है जो होता है जब आप null को IGNORE करते हैं और cur.next.title को एक step ज़्यादा दूर call करते हैं: NullPointerException। Option D bookkeeping describe करता है जो एक plain node deliberately carry नहीं करता।
Watch out
एक Chain को Hurt करने के दो तरीके
End से आगे Walk करना: cur.next.title जब cur पहले से last node है null dereference करता है: NullPointerException, chain-builder का signature crash। Step करने से पहले check कीजिए।
अकेले Reference को Drop करना: इस listing में, first पूरी chain का sole handle है। इसे overwrite कीजिए (first = null) और दोनों nodes unreachable हो जाती हैं; garbage collector उन्हें reclaim करता है। Java में कोई delete नहीं, पर आप फिर भी अपनी head को छोड़कर एक structure LOSE कर सकते हैं।
Theory
एक Class, कई Structures
इस unit में सब कुछ, और इसके बाद हर data-structures course का आधा हिस्सा, यही एक idea है अलग तरीके से dressed: nodes plus links। Nodes को एक line में string कीजिए और आपके पास singly linked list है (अगला lesson); आख़िरी link को वापस start की तरफ़ bend कीजिए और यह circular बन जाता है (unit का finale)। BCA304 के stacks और queues सब इस पर rebuild हो सकते हैं। Node को एक बार सीखिए, deeply; बाकी clues arrange करना है।
Summary
Key takeaways
- Data structures एक self-referential class से बनी हैं: data fields plus same type का एक next reference।
- next एक reference है (एक address), embedded object नहीं: कोई infinite nesting नहीं, per new एक node।
- Chains assignment से बनती हैं (first.next = second); next में null end mark करता है।
- Arrays fixed और shift-heavy हैं; chains per node grow करती हैं और cheaply re-link होती हैं, पर search के लिए walk होनी चाहिए।
- Null dereference करना (end से एक step आगे) NullPointerException throw करता है।
- Head reference खोना पूरी chain को garbage collection में खो देता है।
- Memory hook: हर node एक clue है: एक prize, अगले की तरफ़ एक direction।