Theory
Four verbs, એક working queue
Concepts place પર છે; હવે BookBridge ની request list એ actually WORK કરવું જોઈએ. ચાર operations તેના આખા life ને cover કરે છે:
- create/append: નવી request end પર join થાય છે
- insert in front: urgent staff request queue ને jump કરે છે
- traverse: librarian માટે current line ને print કરો
- delete: member cancel કરે છે; તેનું node chain ને leave કરે છે
દરેક operation 2 થી 6 lines છે, અને દરેક line એ reference update છે જે તમારે TRACE કરવા સક્ષમ હોવું જોઈએ. Exams exactly એ પૂછે છે: links ને before અને after show કરો.
Practical
Complete IssueList
class Node {
String title;
Node next;
Node(String t) { title = t; }
}
class IssueList {
Node head; // null means empty list
void addLast(String t) { // end પર append
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; // tail પર walk
cur.next = n; // new tail ને link
}
void addFirst(String t) { // beginning પર insert
Node n = new Node(t);
n.next = head; // step 1: n old chain ને grab કરે છે
head = n; // step 2: head n પર move થાય છે
}
void delete(String t) { // value દ્વારા delete
if (head == null) return;
if (head.title.equals(t)) { head = head.next; return; }
Node cur = head; // target ના BEFORE ના node ને find કરો
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 ને તમારા mind માં 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 એને wrong કરવા વિશે છે.
Quiz
વિદ્યાર્થી addFirst ની 2 lines ને swap કરે છે: head = n; n.next = head; A → B chain પર addFirst("C") call કર્યા પછી list કેવું દેખાય છે?
- C → A → B, correct version જેવું જ
- C પોતાની તરફ pointing; A અને B lost છે
- A → B → C, inserted ને બદલે appended
- Compile error: n.next પહેલા head ને assign નથી કરી શકાતું
Show the answer
C પોતાની તરફ pointing; A અને B lost છે
Walk કરો: head = n એ head ને C પર point કરાવે છે જ્યારે C.next હજુ null છે; પછી n.next = head એ NEW head ને read કરે છે, જે C itself છે, એટલે C.next = C, self-loop. A પર હવે કંઈ point નથી કરતું: old chain unreachable છે અને garbage collector એને claim કરે છે. આ classic order-of-updates disaster છે: હંમેશા new node ને structure માં connect કરો (n.next = head) entry reference ને move કરતા પહેલા. 2 steps ને arrows તરીકે draw કરો અને correct order obvious બને છે.
Theory
Delete: node BEFORE ને find કરો
head → [C] → [A] → [B] માંથી [A] ને delete કરવાનું A itself થી start નથી કરી શકતું: singly list માં, કોઈ પાછળ જોઈ શકતું નથી, અને node જેનું next change થવું જોઈએ એ C છે.
એટલે delete એ test ને એક step ahead સાથે walk કરે છે: cur.next.title.equals(t). A next સાથે C પર standing, તે bypass ને fire કરે છે:
cur.next = cur.next.next; (C હવે B પર points કરે છે)
head → [C] → [B]. Node A પાસે કોઈ references બાકી નથી અને garbage-collected થાય છે. HEAD ને delete કરવું એ special case છે જેની પાસે કોઈ node before નથી: head = head.next;
Think first
Full trace, start થી finish
Fresh list. addLast("A"); addLast("B"); addFirst("C"); delete("A"); traverse(); દરેક call પછી chain ને draw કરો, પછી tap કરીને check કરો.
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 પર standing, cur.next એ A છે, match: C.next = A.next = B. Final chain head → C → B, એટલે traverse C પછી B print કરે છે. જો તમારું drawing દરેક step પર matched થયું હોય, તમે આના કોઈપણ exam variant ને answer કરી શકો છો; operations ક્યારેય change નથી થતા, ફક્ત sequence.
Watch out
3 classic list bugs
Chain ને Losing: new node ને connect કરતા પહેલા head (અથવા કોઈ link) ને move કરવું: quiz disaster.
Special cases ને Forget કરવું: addLast માં empty list, delete માં head-deletion. દરેક operation પૂછે છે: શું જો list empty હોય? શું જો તે first node હોય?
titles પર ==: head.title == t એ references ને compare કરે છે (string-pool lesson!); real input ને .equals() જોઈએ છે. જે delete ક્યારેય match નથી કરતું એ usually આ છે.
Formula
exam recipe
Linked-list questions એ code પહેરેલા diagram questions છે. હંમેશા score કરતી method:
1. nodes ને boxes તરીકે draw કરો arrows સાથે, head અને null ને include કરીને.
2. code માં દરેક reference update ને number કરો (1, 2, 3...).
3. દરેક numbered step પછી arrows ને redraw કરો, ફક્ત end પર નહીં.
4. special cases (empty list, head node) ને એક line each માં state કરો.
Examiners steps ને award કરે છે, ફક્ત final picture નહીં.
Summary
Key takeaways
- addLast: next == null ધરાવતા node પર walk કરો અને ત્યાં link કરો; empty list એટલે head = n.
- addFirst: n.next = head THEN head = n; order old chain ને protect કરે છે.
- delete: target ના BEFORE ના node પર walk કરો અને cur.next = cur.next.next સાથે bypass કરો; head deletion એ its own case છે.
- traverse: head થી while cur != null; bypassed node garbage-collected થાય છે.
- titles ને .equals() સાથે compare કરો, ક્યારેય == નહીં.
- દરેક operation 2 questions ને પહેલા handle કરે છે: empty list? first node?
- Memory hook: head ને move કરતા પહેલા new node ને connect કરો.