Theory
चार Verbs, एक Working Queue
Concepts जगह पर हैं; अब BookBridge की request list को असल में काम करना है। चार operations इसकी पूरी life cover करते हैं:
- create/append: एक नई request end में join होती है
- front में insert: एक urgent staff request queue jump करती है
- traverse: librarian के लिए current line print कीजिए
- delete: एक member cancel करता है; उनकी node chain से निकल जाती है
हर operation 2 से 6 lines की है, और हर line एक reference update है जिसे आप TRACE कर पाने चाहिए। Exams exactly यही पूछते हैं: पहले और बाद के links दिखाइए।
Practical
पूरी IssueList
class Node {
String title;
Node next;
Node(String t) { title = t; }
}
class IssueList {
Node head; // null means empty list
void addLast(String t) { // append at the end
Node n = new Node(t);
if (head == null) { head = n; return; } // empty: n IS the list
Node cur = head;
while (cur.next != null) cur = cur.next; // walk to the tail
cur.next = n; // link the new tail
}
void addFirst(String t) { // insert at the beginning
Node n = new Node(t);
n.next = head; // step 1: n grabs the old chain
head = n; // step 2: head moves to n
}
void delete(String t) { // delete by value
if (head == null) return;
if (head.title.equals(t)) { head = head.next; return; }
Node cur = head; // find the node BEFORE the target
while (cur.next != null && !cur.next.title.equals(t))
cur = cur.next;
if (cur.next != null) cur.next = cur.next.next; // bypass
}
void traverse() {
for (Node cur = head; cur != null; cur = cur.next)
System.out.println(cur.title);
}
}
Theory
Trace: List Shape लेती है
इस sequence को अपने दिमाग़ में run कीजिए, boxes और arrows draw करते हुए:
addLast("A"): empty, तो head → [A|null]
addLast("B"): A से walk कीजिए (इसका next null है), link कीजिए: head → [A] → [B|null]
addFirst("C"): step 1, C.next = head (C, A grab करता है); step 2, head = C:
head → [C] → [A] → [B|null]
addFirst के 2 steps का order इस lesson का heart है, और नीचे का quiz इसे ग़लत करने के बारे में है।
Quiz
एक student addFirst की 2 lines swap कर देता है: head = n; n.next = head; Chain A → B पर addFirst("C") call करने के बाद list कैसी दिखती है?
- C → A → B, correct version जैसा same
- C खुद को point कर रहा है; A और B lost हैं
- A → B → C, insert के बजाय appended
- Compile error: n.next से पहले head assign नहीं हो सकता
Show the answer
C खुद को point कर रहा है; A और B lost हैं
इसे walk कीजिए: head = n head को C की तरफ़ point कराता है जबकि C.next अभी भी null है; फिर n.next = head NEW head पढ़ता है, जो C खुद है, तो C.next = C, एक self-loop। अब A की तरफ़ कुछ point नहीं करता: old chain unreachable है और garbage collector इसे claim करता है। यह classic order-of-updates disaster है: नए node को हमेशा entry reference move करने से पहले structure में CONNECT कीजिए (n.next = head)। 2 steps को arrows की तरह draw कीजिए और correct order obvious हो जाता है।
Theory
Delete: BEFORE वाली Node ढूँढिए
head → [C] → [A] → [B] से [A] delete करना खुद A से शुरू नहीं हो सकता: एक singly list में, कोई भी backwards नहीं देख सकता, और जिस node का next बदलना चाहिए वह C है।
तो delete एक step ahead वाले test से walk करता है: cur.next.title.equals(t)। A next वाले C पर खड़े होकर, यह bypass fire करता है:
cur.next = cur.next.next; (C अब B की तरफ़ point करता है)
head → [C] → [B]। Node A के पास कोई references नहीं बचे और यह garbage-collected है। HEAD delete करना वह special case है जिसके पहले कोई node नहीं है: head = head.next;
Think first
Full Trace, शुरू से आख़िर तक
Fresh list। addLast("A"); addLast("B"); addFirst("C"); delete("A"); traverse(); हर call के बाद chain draw कीजिए, फिर check करने के लिए tap कीजिए।
Show the answer
addLast("A"): head → A। addLast("B"): head → A → B। addFirst("C"): C, A grab करता है, head move होता है: head → C → A → B। delete("A"): head C है, target नहीं; C पर खड़े होकर, cur.next A है, match: C.next = A.next = B। Final chain head → C → B, तो traverse C फिर B print करता है। अगर आपकी drawing हर step पर match हुई, आप इस exam variant का कोई भी version answer कर सकते हैं; operations कभी नहीं बदलतीं, सिर्फ़ sequence।
Watch out
3 Classic List Bugs
Chain खोना: नए node को connect करने से पहले head (या कोई link) move करना: quiz वाला disaster।
Special Cases भूलना: addLast में empty list, delete में head-deletion। हर operation पूछता है: अगर list empty है तो? अगर यह पहली node है तो?
Titles पर ==: head.title == t references compare करता है (string-pool lesson!); real input को .equals() चाहिए। एक delete जो कभी match नहीं करता आमतौर पर यही है।
Formula
Exam Recipe
Linked-list questions code पहने diagram questions हैं। वह method जो हमेशा score करता है:
1. Nodes को boxes और arrows की तरह draw कीजिए, head और null सहित।
2. Code में हर reference update number कीजिए (1, 2, 3...)।
3. हर numbered step के BAAD arrows redraw कीजिए, सिर्फ़ आख़िर में नहीं।
4. Special cases (empty list, head node) एक-एक line में state कीजिए।
Examiners steps के लिए marks देते हैं, सिर्फ़ final picture के लिए नहीं।
Summary
Key takeaways
- addLast: next == null वाली node तक walk कीजिए और वहाँ link कीजिए; empty list का मतलब है head = n।
- addFirst: n.next = head फिर head = n; order old chain को protect करता है।
- delete: target से PEHLE वाली node तक walk कीजिए और cur.next = cur.next.next से bypass कीजिए; head deletion अपना खुद का case है।
- traverse: head से जब तक cur != null; bypassed node garbage-collected है।
- Titles को .equals() से compare कीजिए, कभी == से नहीं।
- हर operation पहले 2 questions handle करता है: empty list? first node?
- Memory hook: head move करने से पहले नए node को connect कीजिए।