Theory
બે queues જેના endings અલગ છે
BookBridge હવે 2 waiting lines ચલાવે છે.
issue-request queue: requests arrive, serve થાય છે, અને line eventually EMPTIES થાય છે. એની પાસે genuine end છે.
reading-room roster: 4 members 2 desks ને turns દ્વારા share કરે છે, અને last member પછી turn FIRST પર પાછી જાય છે. આ line ક્યારેય end થતી નથી; એ cycle કરે છે.
Same nodes, same links, એક structural difference: last node નું next શું hold કરે છે. એ single slot unit ના 2 list types ને split કરે છે.
Theory
Singly linked list, ઔપચારિક રીતે
Singly linked list એ nodes નો set છે જ્યાં દરેક node next ને reference કરે છે, એક entry reference થી reachable જેને head કહેવાય છે:
head → [Riya] → [Aman] → [Zoya] → null
Properties જે exams quote કરે છે:
- links એક direction માં જ point કરે છે: forward (એ "singly" છે)
- last node નું next null છે: end marker
- traversal head થી start થાય છે અને null પર stop થાય છે
- કોઈપણ node થી તમે AFTER ની everything ને reach કરી શકો છો, before ની કંઈ નહીં
Theory
એને circle માં bend કરો
હવે exactly એક thing change કરો: last node નું next null ને બદલે head reference hold કરે છે.
head → [Riya] → [Aman] → [Zoya] ↩ (પાછું Riya પર)
આ singly circular linked list છે. હજુ singly: એક direction, દરેક node માં એક link. પણ:
- ક્યાંય null નથી: chain ને natural end નથી
- કોઈપણ node થી, walk કરતા રહો અને તમે દરેક node ને reach કરશો, including those "before" તમને
- "last" અને "first" neighbours છે: turn-taking માટે perfect
At a glance
Singly vs singly circular
| Aspect | Singly | Singly circular |
|---|---|---|
| Last node નું next | null | The head node |
| End detection | cur == null | Starting node પર પાછા |
| Traversal loop | while (cur != null) | do-while until start reappears |
| last node થી Head | Impossible (કોઈ backward path નથી) | એક step: last.next |
| Natural fit | Queues અને stacks જે empty થાય | Round-robin turns, repeating playlists |
Quiz
તમે singly CIRCULAR list ને familiar loop સાથે print કરો છો: while (cur != null) { print; cur = cur.next; } શું થાય છે?
- એ દરેક member ને once print કરે છે અને last node પર stop થાય છે
- એ forever loop કરે છે: circle માં કોઈ next null નથી હોતું
- એ last node પર NullPointerException throw કરે છે
- એ કંઈ print નથી કરતું: loop condition immediately fail થાય છે
Show the answer
એ forever loop કરે છે: circle માં કોઈ next null નથી હોતું
while null ની wait કરે છે જે exist નથી કરતું: circular list માં દરેક next real node તરફ point કરે છે, એટલે loop Riya, Aman, Zoya, Riya, Aman... forever cycle કરે છે. આ Unit 1 ના looping lesson નો infinite-loop killer છે જે data-structure costume પહેરે છે. Option A SINGLY list નું behaviour describe કરે છે. Option C એને backwards કરે છે: null ને dereference કરવાનો crash ત્યાં happen નથી કરી શકતો જ્યાં null ક્યારેય appear નથી થતું. circular traversal ને different stop signal જોઈએ છે: શું હું જ્યાં start થયો હતો ત્યાં પાછો આવ્યો?
Think first
right stop signal design કરો
જો null ક્યારેય આવતું નથી, તો circular list ને exactly once traverse કેવી રીતે કરશો? think કરો કે Unit 1 નો કયો loop fit થાય છે, અને શા માટે while fixed condition સાથે પણ work નથી કરી શકતું.
Show the answer
start ને remember કરો, walk કરો, અને જ્યારે એને જુઓ ત્યારે stop કરો: head થી start કરો, અને loop while (cur != head). પણ test-at-the-top while step 0 પર fail થાય છે: cur IS head છે કંઈ print કર્યા પહેલા, એટલે body ક્યારેય run નથી થતી. loop જે તેની body ને check કરતા પહેલા run કરે છે એ do-while છે: do { print; cur = cur.next; } while (cur != head); દરેક node ને exactly once print કરે છે. Unit 1 નો confident host finally એ structure ને meet કરે છે જેને genuinely એની જરૂર છે.
Watch out
Concept traps જે exam loves કરે છે
"Circular એટલે તમે backwards જઈ શકો છો": no. એ હજુ SINGLY linked છે: દરેક node માં એક forward link. તમે earlier nodes ને reach કરી શકો છો માત્ર all the way around going દ્વારા; doubly linked list (પછીનો course) એ છે જેની પાસે real backward links છે.
"Circular list ની પાસે head નથી": એને usable હોવા માટે હજુ entry reference ની જરૂર છે; implementations ઘણીવાર LAST node નો reference રાખે છે, કારણ કે last.next IS head: 2 ends for the price of 1.
Theory
દરેક shape ક્યાં world ચલાવે છે
Singly list default chain છે: BookBridge ની request queue next lesson, undo histories, hash-table buckets. circular one turn-taking ને own કરે છે: BCA203 નું round-robin CPU scheduling દરેક process ને time slice આપતું હતું exactly આ shape માંથી, music player નું repeat-all circular walk છે, અને reading-room roster same રીતે cycle કરે છે. next 2 lessons બંને ને build કરે છે, operation by operation, દરેક reference update ને trace કરીને.
Summary
Key takeaways
- Singly linked list: head થી last સુધી, one-directional links, last node નું next null છે.
- Singly circular: identical, except last node નું next head hold કરે છે: ક્યાંય null નથી.
- Traversal: singly માટે while (cur != null); circular માટે do-while until start reappears.
- circular list પર while (cur != null) forever loop કરે છે: classic trap.
- Circular હજુ one-directional છે; "back" જવાનો અર્થ છે all the way around જવું.
- circle ના LAST node નો reference રાખવાથી head free મળે છે: last.next.
- Memory hook: singly null પર end થાય છે, circular જ્યાં begin થયું ત્યાં end થાય છે.