Theory
अलग Endings वाली दो Queues
BookBridge अब 2 waiting lines run करता है।
Issue-Request Queue: requests आती हैं, serve होती हैं, और line आख़िरकार EMPTY हो जाती है। इसका एक genuine end है।
Reading-Room Roster: 4 members 2 desks turns से share करते हैं, और आख़िरी member के बाद turn वापस FIRST पर जाती है। यह line कभी खत्म नहीं होती; यह cycle करती है।
Same nodes, same links, एक structural difference: last node का next क्या hold करता है। वह single slot unit के 2 list types को split करती है।
Theory
Singly Linked List, Formally
एक singly linked list nodes का एक set है जहाँ हर node अगले को 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 पर शुरू होता है और null पर रुकता है
- किसी भी node से आप इसके BAAD की हर चीज़ तक पहुँच सकते हैं, इससे पहले की कभी नहीं
Theory
इसे एक Circle में Bend कीजिए
अब exactly एक चीज़ बदलिए: last node का next null के बजाय head reference hold करता है।
head → [Riya] → [Aman] → [Zoya] ↩ (back to Riya)
यह singly circular linked list है। अभी भी singly: एक direction, per node एक link। पर:
- कहीं भी कोई null नहीं है: chain का कोई natural end नहीं है
- KISI BHI node से, walk करते रहिए और आप हर node तक पहुँचते हैं, आपसे "पहले" वालों सहित
- "last" और "first" neighbours हैं: turn-taking के लिए perfect
At a glance
Singly बनाम Singly Circular
| Aspect | Singly | Singly Circular |
|---|---|---|
| Last Node का Next | null | Head node |
| End Detection | cur == null | Starting node पर वापस |
| Traversal Loop | while (cur != null) | Start फिर से appear होने तक do-while |
| Last Node से Head | Impossible (कोई backward path नहीं) | एक step: last.next |
| Natural Fit | Queues और stacks जो empty होते हैं | Round-robin turns, repeating playlists |
Quiz
आप familiar loop से एक singly CIRCULAR list print करते हैं: while (cur != null) { print; cur = cur.next; } क्या होता है?
- यह हर member को एक बार print करता है और last node पर रुकता है
- यह हमेशा के लिए loop करता है: circle में कोई next कभी null नहीं होता
- यह last node पर एक NullPointerException throw करता है
- यह कुछ नहीं print करता: loop condition immediately fail होता है
Show the answer
यह हमेशा के लिए loop करता है: circle में कोई next कभी null नहीं होता
while एक ऐसे null का wait करता है जो exist नहीं करता: एक circular list में हर next एक real node की तरफ़ point करता है, तो loop Riya, Aman, Zoya, Riya, Aman... हमेशा के लिए cycle करता है। यह Unit 1 के looping lesson का infinite-loop killer है एक data-structure costume पहने हुए। Option A SINGLY list का behaviour describe करता है। Option C इसे backwards रखता है: null dereference करने का crash वहाँ नहीं हो सकता जहाँ null कभी appear नहीं होता। Circular traversal को एक अलग stop signal चाहिए: क्या मैं वापस वहाँ हूँ जहाँ से मैंने शुरू किया?
Think first
सही Stop Signal Design कीजिए
अगर null कभी नहीं आता, आप एक circular list को exactly एक बार कैसे traverse करते हैं? सोचिए Unit 1 का कौन सा loop fit होता है, और क्यों while fixed condition के साथ भी काम नहीं कर सकता।
Show the answer
Start याद रखिए, walk कीजिए, और इसे फिर से देखने पर रुकिए: head पर start कीजिए, और loop while (cur != head)। पर test-at-the-top while step 0 पर fail होता है: कुछ भी print करने से पहले cur HEAD HAI, तो body कभी run नहीं होता। वह loop जो check करने से पहले अपनी body run करता है do-while है: do { print; cur = cur.next; } while (cur != head); हर node को exactly एक बार print करता है। Unit 1 का confident host आख़िरकार उस structure से मिलता है जिसे genuinely इसकी ज़रूरत है।
Watch out
Concept Traps जो Exam पसंद करता है
"Circular का मतलब है आप backwards जा सकते हैं": नहीं। यह अभी भी SINGLY linked है: per node एक forward link। आप earlier nodes तक सिर्फ़ पूरी तरह घूमकर पहुँच सकते हैं; एक doubly linked list (एक बाद का course) वह है जिसके पास real backward links हैं।
"Circular list का कोई head नहीं है": इसे usable होने के लिए अभी भी एक entry reference चाहिए; implementations अक्सर LAST node का एक reference रखते हैं, क्योंकि last.next HEAD HAI: 1 की कीमत में 2 ends।
Theory
हर Shape कहाँ World Run करती है
Singly list default chain है: अगले lesson की BookBridge की request queue, undo histories, hash-table buckets। Circular वाला turn-taking owns करता है: BCA203 की round-robin CPU scheduling ने हर process को exactly इस shape से एक time slice दिया, एक music player की repeat-all एक circular walk है, और reading-room roster same तरीके से cycle करती है। अगले 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, सिवाय इसके कि last node का next head hold करता है: कहीं भी कोई null नहीं।
- Traversal: singly के लिए while (cur != null); circular के लिए start फिर से appear होने तक do-while।
- एक circular list पर while (cur != null) हमेशा के लिए loop करता है: classic trap।
- Circular अभी भी one-directional है; "back" जाने का मतलब है पूरी तरह घूमना।
- एक circle के LAST node का एक reference रखना head free देता है: last.next।
- Memory hook: singly null पर खत्म होती है, circular वहाँ खत्म होती है जहाँ शुरू हुई।