Theory
roster circle ને close કરે છે
Final BookBridge build: reading-room roster. ચાર members 2 desks ને share કરે છે; Zoya ની turn પછી roster desk ને Riya પાસે પાછું આપે છે. Forever.
Last lesson નું IssueList આને express નથી કરી શકતું: તેનું tail null કહે છે, full stop. આજે tail કહે છે "go back to the start", અને દરેક operation એ એક new reality ને respect કરવું જોઈએ: lean કરવા માટે કોઈ null નથી. Create, traverse, insert, delete: same 4 verbs, end વગરના world માટે rewired.
Theory
કોઈ code પહેલાં એક clever choice
class કયા node ને remember કરવું જોઈએ? Instinct head કહે છે. Professionals last node ને instead keep કરે છે, અને એ 1 ની કિંમતે 2 ends buy કરે છે:
- head હંમેશા instantly reachable છે:
last.next - tail એ
lastitself છે
એટલે FRONT અને END બંને પર inserting ને કોઈ walking ની જરૂર નથી: બંને ત્યાં happen થાય છે જ્યાં last already stands કરે છે. singly list જે તે offer કરતું હોત તે દરેક append માટે તેની આખી chain ને walk કરવી પડતી.
Practical
roster, circle તરીકે wired
class CNode {
String name;
CNode next;
CNode(String n) { name = n; }
}
class Roster {
CNode last; // last.next IS the head
void addLast(String name) { // circle ના end પર join કરો
CNode n = new CNode(name);
if (last == null) {
last = n;
n.next = n; // પોતાની તરફ points કરે છે: smallest circle
} else {
n.next = last.next; // 1: n head ને grab કરે છે
last.next = n; // 2: old last n તરફ points કરે છે
last = n; // 3: n new last બને છે
}
}
void traverse() { // દરેક member ને exactly once print કરો
if (last == null) return;
CNode cur = last.next; // head પર start કરો
do {
System.out.println(cur.name);
cur = cur.next;
} while (cur != last.next); // head reappear થાય ત્યારે stop
}
void deleteFirst() { // head circle ને leave કરે છે
if (last == null) return;
if (last.next == last) { last = null; return; } // only node
last.next = last.next.next; // head ને bypass કરો
}
}
Theory
Trace: circle grows થાય છે
ખાલી પર addLast("Riya"): last = Riya, અને Riya.next = Riya. એક node, પોતાની તરફ pointing: complete, legal circle.
addLast("Aman"): step 1, Aman.next = last.next (= Riya, the head); step 2, Riya.next = Aman; step 3, last = Aman.
Circle: Riya → Aman → Riya...
addLast("Zoya"): Zoya.next = Riya; Aman.next = Zoya; last = Zoya.
Circle: Riya → Aman → Zoya → પાછા Riya. traverse() last.next (Riya) પર start થાય છે અને Riya, Aman, Zoya print કરે છે, પછી Riya ને ફરી meet કરે છે અને stop થાય છે.
Quiz
Roster class માં, ખાલી roster પર addLast("Riya") તરત જ પછી, very FIRST node નો next ક્યાં points કરે છે?
- null, જ્યાં સુધી બીજો member join ન થાય
- Node itself: Riya.next == Riya
- Roster object નો last reference
- એ unassigned છોડવામાં આવે છે, એટલે એને read કરવું compile error છે
Show the answer
Node itself: Riya.next == Riya
Circular list એ ALWAYS તેનું circle close કરવું જોઈએ, even with one member: n.next = n smallest possible loop બનાવે છે, એટલે traverse અને દરેક બીજું operation "circle of 1" ને special-case કર્યા વગર work કરે. Option A એ singly list બનાવતું અને instantly do-while ને break કરતું (તે null માં walk કરતું). Option C Roster ના field ને chain ના node સાથે confuse કરે છે. Option D Unit 2 ને forget કરે છે: fields default રીતે null થાય છે, અને constructor અહીં anyway next ને explicitly assign કરે છે.
Think first
exit ને trace કરો
Roster: Riya → Aman → Zoya (last = Zoya). deleteFirst() call કરો, પછી traverse(). દરેક reference ને tap કરતા પહેલા walk કરો: કોણ print થાય છે, અને Zoya.next હવે શું hold કરે છે?
Show the answer
deleteFirst એ last.next = last.next.next run કરે છે: Zoya.next એ Riya હતું, Riya.next એ Aman છે, એટલે Zoya.next = Aman. Riya પાસે કોઈ incoming reference બાકી નથી: garbage-collected. Circle એ Aman → Zoya → Aman છે, અને traverse Aman, Zoya print કરે છે. Note શું ક્યારેય થયું નહીં: કોઈ walking નહીં, કોઈ null checks નહીં, એક reassignment. અને જો roster માં ફક્ત Riya હોત, તો guard last.next == last fire થાત અને last = null set કરતું: 1 નું circle nothing માં empty થાત.
Watch out
Circle-specific traps
while (cur != null): loops forever; healthy circle માં કોઈ next ક્યારેય null નથી હોતો. Stop test positional છે: start પર પાછા.
Plain while instead of do-while: while (cur != last.next) એ first print પહેલાં false છે (cur IS head છે), એટલે કંઈ print નથી થતું. Body-first loop અહીં optional નથી.
Deleting last itself: bypassing enough નથી; last એ તેના BEFORE ના node પર move થવું જોઈએ, અને singly circle માં તે node ને find કરવાનો અર્થ છે almost આખી circle ને walk કરવું.
Theory
BookBridge, complete
પાછળ જુઓ અને જુઓ કે semester એ શું build કર્યું: એક console app જે variables ને Book class માં grow કર્યું, polymorphism સાથે Person family, guarded Strings અને custom exception, background reminder thread, shelved packages, અને હવે 2 hand-built lists જે તેની queues ને run કરે છે. એ BCA403 નો આખો syllabus છે જે એક program માં living છે. circular pattern itself ત્યાં returns થાય છે જ્યાં turns repeat થાય છે: BCA203 નું round-robin scheduler, repeat પર playlists, અને multiplayer game loops.
Summary
Key takeaways
- LAST node નો reference રાખો: last.next એ head છે, એટલે બંને ends walking વગર reachable છે.
- Circle નો first node પોતાની તરફ points કરે છે: n.next = n.
- End પર insert: n.next = last.next, last.next = n, last = n (front insert: same 2 rewires, last ને move કરવાનું skip).
- last.next થી do-while સાથે traverse કરો, head reappear થાય ત્યારે stop; while-null ક્યારેય terminate નથી થતું.
- deleteFirst: last.next = last.next.next; single-node circle last = null માં empty થાય છે.
- last itself ને delete કરવાનો અર્થ છે તેના predecessor પર walk કરવું અને last ને ત્યાં move કરવું.
- Memory hook: one નું circle પોતાની તરફ points કરે છે; null ની wait કરતો loop forever wait કરે છે.