3.2.4
Ek circular linked list ek aisi chain hai jisme last node wapas first ki taraf point karta hai instead of null ki taraf. Isliye iska koi end nahi — tum hamesha chalte reh sakte ho, loop karte hue. Yeh ek akela property ise un cheezoon ke liye natural data structure banata hai jo real life mein cyclic, rotating, ya round-robin hoti hain.
Definition Circular Linked List (CLL)Ek linked list jisme last node ka next pointer head ki taraf point karta hai, ek closed loop banata hai. Koi null terminator nahi hota. Yeh ho sakta hai:
Singly circular : har node → next, last → head.Doubly circular : har node ke paas next aur prev dono hain; head ka prev = last, last ka next = head.
Intuition "No null" kyun sab badal deta haiNormal list mein tum null hit karne par rok jaate ho. CLL mein tum tab ruk jaate ho jab tum wapas wahan pahunch jaao jahan se shuru kiya tha . Iska matlab:
Koi privileged "end" nahi hai — har node symmetric hai.
Kisi bhi node se tum har node tak pahunch sakte ho. Poori structure traverse karne ke liye tumhe head ki zaroorat nahi.
Yeh do facts neeche ke saare applications ka beej hain.
Trick yeh hai: poocho "kya problem wrap around karti hai?" Agar haan → CLL fit hota hai.
Ek OS har process ko ek fixed time slice deta hai, phir next process par jaata hai, aur last process ke baad use first par wapas jaana hota hai. Woh "last-ke-baad-first-aata-hai" bilkul CLL ka loop hai.
KAISE: Ek pointer current rakho. current ko uske quantum ke liye run karo, phir current = current->next. Kyunki yeh circular hai, tum kabhi end se neeche nahi giroge — rotation automatic hai, koi special "go back to start" code nahi.
Log ek circle mein khade hain; counting wrap karti hai. Kisi ko eliminate karne ke baad tum next person se counting jaari rakhte ho, loop karte hue. CLL circle ko model karta hai, aur ek node ko delete karna O ( 1 )
Last player/song ke baad tum wapas first par jaate ho. Ek music player loop par literally current = current->next hamesha ke liye hai.
Ek fixed-size buffer jo purane data ko overwrite karta hai jab bhar jaata hai. Read aur write pointers loop ke around ek doosre ka peecha karte hain. (Aksar arrays ke saath hota hai, lekin conceptually ek CLL hai.)
CLLs sibling nodes ko ek circle mein link karta hai taaki tum splice (do circular lists merge) kar sako O ( 1 )
Humein traversal aur insertion chahiye. Chalte hain inhe definition se build karte hain.
Derivation Kyun tail-only design O(1) dono ends par deta haiHead = t ai l . n e x t tail = x). Normal list ke saath, back-insert O ( n ) force karta hai tail.next = head, isliye tumhe head free mein milta hai. Isliye: tail store karo, head derive karo.
Worked example Example 1 — Round-robin with quantum = 2Processes A(burst 4), B(burst 3), C(burst 1), quantum 2. CLL: A→B→C→A.
Round
current
runs
remaining
1
A
2
A=2, B=3, C=1
2
B
2
B=1, C=1
3
C
1 (done, remove)
C=0 ✗
4
A
2 (done, remove)
A=0 ✗
5
B
1 (done)
finished
Yeh step (round 3) kyun? C ko sirf 1 < quantum chahiye, isliye woh pehle khatam ho jaata hai aur hum uska node delete kar dete hain — circle automatically A→B→A ho jaata hai kyunki humne sirf prev.next = C.next relink kiya.
Worked example Example 2 — Josephus, n=5, k=2Log 1,2,3,4,5 ek circle mein. Har 2nd ko eliminate karo.
1 se shuru karo, count 1→2: 2 eliminate. Circle: 1,3,4,5.
3 se, count 3→4: 4 eliminate. Circle: 1,3,5.
5 se, count 5→1: 1 eliminate. Circle: 3,5.
3 se, count 3→5: 5 eliminate. Circle: 3.
Survivor = 3.
Deletion sasta kyun hai: CLL mein hum victim se just pehle node ka pointer rakhte hain, isliye prev.next = victim.next use O ( 1 ) prev.next se jaari rehti hai — koi array shifting nahi.
Worked example Example 3 — Ring buffer of size 3Slots [_,_,_] ek circle mein, write pointer w, read pointer r.
a,b,c likho → buffer full: [a,b,c], w wapas slot 0 par wrap ho gaya.
d likho → a overwrite (sabse purana): [d,b,c].
Read karo → b return karta hai (sabse purana bacha hua).
a ko overwrite kyun kiya? w loop hokar a ke slot par aa gaya; circle ka matlab hai "last ke baad next = first," isliye sabse purana unread data wahi hai jo replace hota hai. Exactly yahi tarah audio/network streaming buffers kaam karte hain.
Common mistake "Main traversalp == null par rok doonga."
Kyun sahi lagta hai: Har normal linked-list loop null par end hota hai; muscle memory.
Kyun galat hai: CLL mein koi null nahi — loop hamesha ke liye chalta hai (infinite loop / crash).
Fix: Jab p == start ho tab ruko (do-while use karo taaki head ek baar visit ho).
Common mistake "Insertion normal list jaise hi hai."Kyun sahi lagta hai: Nodes bilkul identical lagte hain.
Kyun galat hai: Tumhe loop preserve karna hai: naye last node ka next head ki taraf point karna chahiye. Yeh bhoolna circularity ko ek plain list mein tod deta hai.
Fix: Kisi bhi tail change ke baad, ensure karo ki tail.next = head.
Common mistake "Ek empty CLL bashead = null hai."
Kyun sahi lagta hai: Normal lists ke liye yahi empty case hai.
Kyun galat hai: Jab tum pehla node insert karte ho, use khud ki taraf point karna chahiye (node.next = node), warna koi loop nahi hai.
Fix: First insert special case: node.next = node; tail = node.
Common mistake "CLL sirf theoretical hai."Kyun sahi lagta hai: Yeh rarely textbook default hota hai.
Fix: Yeh har jagah hai: OS schedulers, music repeat, ring buffers, Josephus, multiplayer turns, Fibonacci heaps.
Recall Feynman: ek 12-saal ke bache ko samjhaoSocho bacche ek circle mein baith kar ball pass kar rahe hain. Last bache ke baad, ball pehle bache ko wapas jaati hai — koi "line ka end" nahi hai. Ek circular linked list computer ka woh circle hai. Yeh perfect hai jab koi cheez round and round chalti rehti hai: game mein baari lena, playlist jo repeat par set ho, ya sab mein ek toy fairly share karna shuru se dobara karne se pehle. Magic rule: tum jaante ho ki tum poora chakkar laga chuke ho jab tum wapas wahan pahunch jaate ho jahan se shuru kiya tha .
Mnemonic Applications yaad rakho"R-J-P-B-F" = R ound-robin, J osephus, P laylist-repeat, B uffer (ring), F ibonacci heap.
Phrase: "R ound J ourneys P lay B etter F orever" — sab cheezein jo loop karti hain.
Ek circular linked list ko kaunsi ek property define karti hai? Last node ka next wapas head ki taraf point karta hai (koi null terminator nahi), ek loop banata hai.
CLL traverse karte waqt sahi stop condition kya hai? Jab pointer starting node par wapas aaye tab ruko (p == start), do-while use karo taaki head ek baar visit ho.
CLL mein head ki jagah tail pointer kyun store karein? Kyunki tail.next HI head hai, ek pointer se DONO ends ka O(1) access milta hai.
Classic CLL application kaun sa scheduling algorithm hai aur kyun? Round-robin — last process ke baad yeh pehle par wapas jaata hai, loop se match karta hai.
Josephus problem mein CLL efficient kyun hai? Counting circle ke around wrap karti hai, aur ek person ko eliminate karna prev.next = victim.next se O(1) hai.
Ek empty CLL mein PEHLA node kaise insert karein? Use khud ki taraf point karao: node.next = node (aur tail = node set karo).
Agar tum CLL ko while(p != null) loop se traverse karo toh kya galat hoga? Infinite loop — koi null nahi hai, isliye yeh kabhi terminate nahi karta.
Ring buffer kya hai aur CLL se iska kya sambandh hai? Ek fixed-size buffer jahan read/write pointers ek loop ke around peecha karte hain, bhar jaane par purana data overwrite karta hai — CLL jaise hi wrap-around logic.
Josephus n=5, k=2 survivor? Person 3.
CLL se tum KISI bhi node se saare nodes tak kyun pahunch sakte ho? Kyunki loop closed hai; next follow karte rehne se eventually har node visit hota hai aur start par wapas aata hai.
Singly Linked List — base structure jise CLL extend karta hai.Doubly Linked List — combine hokar doubly-circular lists banata hai (Fibonacci heap, LRU).Round-Robin Scheduling — primary OS application.Josephus Problem — classic CLL puzzle.Queue — circular array queue usi wrap-around idea ko use karta hai.Ring Buffer — streaming/producer-consumer use case.Fibonacci Heap — circular sibling lists use karta hai O(1) merge ke liye.
Any node reaches all nodes
Turn-taking / playlist loop
