PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Circular Linked List: Singly Circular vs Doubly Circular Lists (सर्कुलर लिंक्ड लिस्ट: अंतिम नोड का पहले नोड से लिंक और उपयोग) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: A Circular Linked List connects the last node back to the first node instead of NULL, enabling continuous cyclic traversal from any node. Maintaining a tail (last) pointer in Singly Circular Lists gives O(1) insertions at both front and rear, while Doubly Circular Lists support O(1) bidirectional ring navigation with zero NULL pointers.
अध्याय सार: सर्कुलर लिंक्ड लिस्ट में अंतिम नोड NULL की जगह पहले नोड से जुड़ा होता है, जिससे किसी भी नोड से निरंतर चक्रीय ट्रैवर्सल संभव होता है। सिंगली सर्कुलर लिस्ट में tail पॉइंटर रखने पर आगे और पीछे दोनों सिरों पर O(1) इंसर्शन मिलता है, जबकि डबली सर्कुलर लिस्ट में कोई भी NULL पॉइंटर नहीं होता।
Circular Linked List: Singly Circular vs Doubly Circular Lists: Detailed Notes & Architecture (सर्कुलर लिंक्ड लिस्ट: अंतिम नोड का पहले नोड से लिंक और उपयोग)
1. Circular Linking Invariants & Empty vs Single-Node Cases (सर्कुलर लिंकिंग नियम: खाली और एकल-नोड स्थिति)
[EN] In a Circular Linked List (CLL), no data node stores NULL in its link field during normal chaining; instead, the final node wraps around to the entry node. An empty CLL still sets head = NULL (or last = NULL), whereas a single-node CLL satisfies node->next == node (and node->prev == node in a Doubly Circular List). Because there is no natural NULL terminator, traversing requires checking whether the walker pointer has returned to the starting node.
[HI] सर्कुलर लिंक्ड लिस्ट में सामान्य नोड्स के लिंक फील्ड में NULL नहीं होता, बल्कि अंतिम नोड पहले नोड की ओर संकेत करता है। खाली लिस्ट में head == NULL (या last == NULL) रहता है, जबकि एक नोड वाली लिस्ट में node->next == node होता है। चूँकि अंत में NULL नहीं मिलता, इसलिए ट्रैवर्सल रोकते समय शुरुआती नोड पर वापस पहुँचने की जांच की जाती है।
2. Singly Circular Linked List (SCLL) & The Tail-Pointer Advantage (सिंगली सर्कुलर लिस्ट (SCLL) और Tail पॉइंटर का लाभ)
[EN] An SCLL uses one next pointer per node with tail->next == head. Textbook implementations keep an external pointer to 'last' (the tail) rather than 'head' because last->next gives the head in O(1) time! As a result, inserting at the front (newNode->next = last->next; last->next = newNode;) and inserting at the rear (plus last = newNode;) BOTH run in O(1) time, whereas holding only head makes rear insertion O(n).
[HI] SCLL में प्रति नोड एक next पॉइंटर होता है और tail->next हमेशा head से जुड़ता है। यदि बाहरी पॉइंटर head की जगह 'last' (अंतिम नोड) पर रखा जाए, तो last->next से पहला नोड भी O(1) में मिल जाता है! इससे शुरुआत और अंत दोनों जगह नया नोड जोड़ना O(1) समय में संभव हो जाता है।
3. Doubly Circular Linked List (DCLL) Architecture (डबली सर्कुलर लिंक्ड लिस्ट (DCLL) की संरचना)
[EN] A Doubly Circular Linked List merges doubly-linked symmetry with circular wrap-around so that tail->next == head AND head->prev == tail simultaneously. A non-empty DCLL contains zero NULL pointers and allows O(1) insertion and deletion at both front and end using only head (since tail is immediately accessible via head->prev). Forward and backward rings can start at any node without losing access to the rest of the list.
[HI] DCLL में डबली और सर्कुलर दोनों के गुण होते हैं: tail->next == head तथा head->prev == tail। गैर-खाली DCLL में एक भी NULL पॉइंटर नहीं होता और केवल head पॉइंटर के सहारे tail (head->prev) को O(1) में प्राप्त कर दोनों सिरों पर O(1) इंसर्शन व डिलीशन किया जा सकता है।
4. Loop Termination Safety & Real-World Applications (ट्रैवर्सल सुरक्षा और वास्तविक उपयोग)
[EN] To avoid infinite loops during traversal, first guard against head == NULL and then use a do { process(p); p = p->next; } while (p != head); loop rather than a NULL-checking while loop. Circular lists are ideal for Operating System Round-Robin CPU scheduling (rotating time slices fairly), circular audio/network ring buffers, multiplayer turn rotation, Josephus problem simulation, and Fibonacci Heap sibling lists (DCLL).
[HI] अनंत लूप (Infinite Loop) से बचने के लिए पहले head != NULL जांचकर do-while लूप का उपयोग किया जाता है ताकि पहला नोड प्रोसेस होने के बाद p == head पर लूप रुके। इसका प्रमुख उपयोग OS के राउंड-रॉबिन CPU शेड्यूलिंग, रिंग बफर, मल्टीप्लेयर गेम टर्न, जोसेफस समस्या और फिबोनाची हीप में होता है।
Syntax, Formula & Technical Example (Circular Linked List: Singly Circular vs Doubly Circular Lists)
struct CNode { int data; struct CNode *next; };
struct CNode* insertEnd(struct CNode *last, int val) {
struct CNode *nw = malloc(sizeof(struct CNode));
nw->data = val;
if (last == NULL) { nw->next = nw; return nw; }
nw->next = last->next;
last->next = nw;
return nw; /* new node becomes last */
}
Circular Linked List: Singly Circular vs Doubly Circular Lists Quick Reference & Comparison Table
| Variant / Condition | Pointer Invariant & Overhead | Performance & Behavior |
|---|---|---|
| Singly Circular (SCLL) | tail->next == head with 1 pointer per node | O(1) front and end insert using last pointer |
| Doubly Circular (DCLL) | tail->next == head AND head->prev == tail | Zero NULL pointers; tail via head->prev in O(1) |
| Single-Node CLL State | node->next == node (self-loop) | Deleting sole node resets external pointer to NULL |
| Traversal Loop Guard | do-while loop stopping when ptr == start | Using while(ptr != NULL) triggers infinite loop |
Circular Linked List: Singly Circular vs Doubly Circular Lists Top 20 Bilingual MCQs with Answers
Q1. In a non-empty Singly Circular Linked List, what does the next pointer of the last node store?
(एक गैर-खाली सिंगली सर्कुलर लिंक्ड लिस्ट के अंतिम नोड का next पॉइंटर किसे इंगित करता है?)
(A) The address of the middle node
(B) The address of the last node itself always
(C) NULL
(D) The address of the first (head) node
Correct Answer: (D)
[EN] In an SCLL, the last node wraps back to the first node (tail->next == head) instead of storing NULL.
[HI] SCLL में अंतिम नोड का next पॉइंटर NULL न होकर पहले नोड (head) का पता रखता है।
Q2. Why do implementations of Singly Circular Linked Lists typically maintain a pointer to 'last' (tail) rather than 'head'?
(सिंगली सर्कुलर लिंक्ड लिस्ट में सामान्यतः 'head' की बजाय 'last' (tail) पॉइंटर रखना क्यों बेहतर माना जाता है?)
(A) It reduces memory per node from 2 pointers to 1
(B) It prevents self-loops in single-node lists
(C) It eliminates the need to allocate memory dynamically
(D) Both front and end insertions run in O(1) time since last->next is head
Correct Answer: (D)
[EN] With 'last', head is immediately last->next, so adding at either end updates two links in O(1) without scanning.
[HI] 'last' पॉइंटर होने पर head सीधे last->next से O(1) में मिल जाता है, जिससे शुरुआत और अंत दोनों जगह O(1) इंसर्शन होता है।
Q3. How many NULL pointers exist inside the nodes of a valid non-empty Doubly Circular Linked List with 5 nodes?
(5 नोड्स वाली एक सही गैर-खाली डबली सर्कुलर लिंक्ड लिस्ट (DCLL) के नोड्स में कितने NULL पॉइंटर्स होते हैं?)
(A) 0
(B) 2
(C) 5
(D) 1
Correct Answer: (A)
[EN] Every prev and next field in a DCLL points to a valid node because head->prev == tail and tail->next == head.
[HI] DCLL में head->prev == tail और tail->next == head होने से किसी भी नोड में कोई NULL पॉइंटर नहीं होता (कुल 0)।
Q4. What happens if you accidentally traverse a Circular Linked List using: while (ptr != NULL) { ptr = ptr->next; }?
(यदि कोई प्रोग्रामर सर्कुलर लिंक्ड लिस्ट में गलती से while (ptr != NULL) { ptr = ptr->next; } लूप चला दे, तो क्या होगा?)
(A) Infinite loop on any non-empty Circular Linked List
(B) It stops correctly after printing the last node
(C) It crashes with a divide-by-zero error
(D) It prints the list in reverse order
Correct Answer: (A)
[EN] Because no node's next pointer is NULL in a non-empty CLL, ptr != NULL remains forever true.
[HI] गैर-खाली सर्कुलर लिस्ट में किसी भी नोड का next कभी NULL नहीं होता, इसलिए यह अनंत लूप (Infinite Loop) में फँस जाएगा।
Q5. In a Doubly Circular Linked List containing a single node P, what are P->next and P->prev equal to?
(एकल नोड P वाली डबली सर्कुलर लिंक्ड लिस्ट में P->next और P->prev किसके बराबर होते हैं?)
(A) Both equal NULL
(B) Both equal P itself
(C) P->next is NULL and P->prev is P
(D) P->next is P and P->prev is NULL
Correct Answer: (B)
[EN] When n = 1, P is both head and tail, so both its forward and backward links point to P.
[HI] जब लिस्ट में केवल एक नोड P हो, तो वही head और वही tail होता है; अतः उसके दोनों लिंक वापस P पर जुड़ते हैं।
Q6. If you only maintain a 'head' pointer (and no 'last' pointer) in a Singly Circular Linked List of n nodes, what is the time complexity to insert at the end?
(यदि n नोड्स वाली SCLL में केवल 'head' पॉइंटर हो (last न हो), तो अंत में नोड जोड़ने की टाइम कॉम्प्लेक्सिटी क्या होगी?)
(A) O(n)
(B) O(n^2)
(C) O(log n)
(D) O(1)
Correct Answer: (A)
[EN] Without a tail pointer, you must traverse all n nodes from head to find the node whose next == head.
[HI] tail पॉइंटर के बिना अंतिम नोड खोजने के लिए head से सभी n नोड्स को पार करना पड़ता है, अतः O(n) समय लगता है।
Q7. In a Doubly Circular Linked List where only 'head' is stored, what is the time complexity to insert a node at the end?
(यदि केवल 'head' पॉइंटर वाली डबली सर्कुलर लिंक्ड लिस्ट (DCLL) के अंत में नया नोड जोड़ना हो, तो कितना समय लगेगा?)
(A) O(n log n)
(B) O(n)
(C) O(1)
(D) O(log n)
Correct Answer: (C)
[EN] In a DCLL, the last node is directly accessed in O(1) via head->prev, avoiding any linear scan.
[HI] DCLL में अंतिम नोड सीधे head->prev से O(1) में मिल जाता है, इसलिए अंत में इंसर्शन भी O(1) में हो जाता है।
Q8. Which OS CPU scheduling algorithm naturally maps to a Circular Linked List?
(ऑपरेटिंग सिस्टम का कौन सा CPU शेड्यूलिंग एल्गोरिथ्म स्वाभाविक रूप से सर्कुलर लिंक्ड लिस्ट का उपयोग करता है?)
(A) First-Come First-Served Stack
(B) Banker's Deadlock Avoidance
(C) Round-Robin Scheduling
(D) Shortest Job First (Non-preemptive)
Correct Answer: (C)
[EN] Round-Robin cycles endlessly across ready processes in fixed time quanta, matching a circular ring.
[HI] राउंड-रॉबिन शेड्यूलिंग में CPU बारी-बारी से सभी प्रोसेस को एक वृत्ताकार चक्र में टाइम स्लाइस देता है, जो CLL के अनुरूप है।
Q9. When using a do-while loop to traverse an SCLL starting from head, what initial check MUST run before entering the loop?
(head से SCLL को ट्रैवर्स करने के लिए do-while लूप चलाने से पहले कौन सी जांच अनिवार्य है?)
(A) if (head->next == NULL) return;
(B) if (head == NULL) return; (empty list guard)
(C) if (head->prev == head) return;
(D) No initial check is needed before do-while
Correct Answer: (B)
[EN] A do-while executes its body at least once; if head is NULL, dereferencing head->data on iteration 1 crashes.
[HI] do-while कम से कम एक बार चलता ही है; यदि head == NULL हो तो पहले चरण में ही क्रैश हो जाएगा, इसलिए खाली जांच जरूरी है।
Q10. Given 'last' pointing to the tail of an SCLL, what expression accesses the very first node?
(यदि 'last' किसी SCLL के अंतिम नोड को इंगित कर रहा है, तो पहले नोड तक किस एक्सप्रेशन से पहुँचा जाता है?)
(A) last->next
(B) last->prev
(C) last->next->next
(D) head->prev
Correct Answer: (A)
[EN] By circular definition, the successor of the last node is always the first node (head).
[HI] सर्कुलर नियम के अनुसार अंतिम नोड के ठीक बाद वाला नोड (last->next) हमेशा पहला नोड होता है।
Q11. How do you delete the last node in a Singly Circular Linked List when only 'last' is given (and n > 1)?
(n > 1 नोड्स वाली SCLL में अंतिम नोड ('last') को हटाने के लिए किस कॉम्प्लेक्सिटी का ऑपरेशन आवश्यक है?)
(A) O(n^2) to relink every node
(B) O(n) to find the predecessor node before 'last'
(C) O(log n) via binary search
(D) O(1) using last->prev directly
Correct Answer: (B)
[EN] SCLL nodes lack prev links, so deleting 'last' requires traversing from last->next until temp->next == last.
[HI] SCLL में prev पॉइंटर नहीं होता, इसलिए last से ठीक पहले वाले नोड को ढूंढने के लिए O(n) ट्रैवर्सल लगता है।
Q12. In the Josephus problem (n people in a circle, eliminating every k-th person), why is a Circular Linked List preferred over a standard array?
(जोसेफस समस्या (वृत्त में बैठे लोगों में से हर k-वें को हटाना) में एरे की तुलना में सर्कुलर लिंक्ड लिस्ट क्यों बेहतर है?)
(A) Arrays cannot store integer IDs
(B) CLL finds the k-th person in O(1) time without counting
(C) Wrap-around happens automatically and deletions take O(1) without shifting elements
(D) CLL uses zero dynamic memory
Correct Answer: (C)
[EN] Removing an eliminated person in an array requires O(n) element shifting, whereas CLL unlinks the node in O(1).
[HI] एरे से व्यक्ति हटाने पर बाकी तत्व शिफ्ट करने में O(n) समय लगता है, जबकि CLL में लिंक बदलकर O(1) में नोड हट जाता है।
Q13. Which advanced heap data structure relies on Doubly Circular Linked Lists to link sibling trees and merge heaps in O(1) time?
(कौन सी उन्नत हीप संरचना O(1) समय में हीप मर्ज करने और ट्री रूट्स जोड़ने हेतु डबली सर्कुलर लिंक्ड लिस्ट का उपयोग करती है?)
(A) Red-Black Tree
(B) Binary Array Heap
(C) AVL Tree
(D) Fibonacci Heap
Correct Answer: (D)
[EN] Fibonacci Heaps concatenate root lists in O(1) amortized time by splicing two Doubly Circular Linked Lists.
[HI] फिबोनाची हीप में रूट लिस्ट और चाइल्ड लिस्ट को O(1) में जोड़ने (concatenate) के लिए DCLL का उपयोग किया जाता है।
Q14. In a DCLL, which 4 links must update when deleting an interior node X (where X != X->next)?
(DCLL में किसी एक नोड X को हटाते समय (जहाँ X != X->next) कौन से लिंक अपडेट होते हैं?)
(A) X->prev->next = X->next and X->next->prev = X->prev
(B) head->next = X->prev only
(C) X->prev = NULL and X->next = NULL only
(D) X->next->next = X->prev
Correct Answer: (A)
[EN] Connecting X's predecessor and successor directly removes X from the ring cleanly in O(1) time.
[HI] X के पिछले नोड का next अगले से और अगले नोड का prev पिछले से जोड़ने (X->prev->next = X->next; X->next->prev = X->prev) पर X हट जाता है।
Q15. What condition uniquely identifies the end of a full loop when deleting the sole remaining node in SCLL via 'last'?
(SCLL में 'last' पॉइंटर का उपयोग करते समय यह कैसे पता चलता है कि डिलीट किया जा रहा नोड लिस्ट का एकमात्र नोड है?)
(A) last->next->next == NULL
(B) last == NULL
(C) last->next == NULL
(D) last->next == last
Correct Answer: (D)
[EN] When only one node exists, its next pointer points to itself (last->next == last), so after freeing it last becomes NULL.
[HI] केवल एक नोड होने पर उसका next स्वयं पर ही लौटता है (last->next == last); इसे हटाने के बाद last = NULL किया जाता है।
Q16. Which statement is FALSE regarding Circular Linked Lists?
(सर्कुलर लिंक्ड लिस्ट के बारे में निम्नलिखित में से कौन सा कथन असत्य (FALSE) है?)
(A) You can only start traversing a Circular Linked List from the head node
(B) An empty Circular Linked List still uses head == NULL
(C) A Doubly Circular Linked List allows traversal in both clockwise and counter-clockwise directions
(D) SCLL requires only one pointer field per node
Correct Answer: (A)
[EN] Because every node links forward around the ring, you can start traversing from ANY node and still visit all nodes.
[HI] सर्कुलर लिस्ट में आप किसी भी नोड से ट्रैवर्सल शुरू करके सभी नोड्स तक पहुँच सकते हैं; केवल head से शुरू करना जरूरी नहीं है।
Q17. Within Circular Linked List: Singly Circular vs Doubly Circular Lists, which variant / condition directly maps to: "tail->next == head with 1 pointer per node"?
(Circular Linked List: Singly Circular vs Doubly Circular Lists में कौन सा Variant / Condition सीधे "tail->next == head with 1 pointer per node" से संबंधित है?)
(A) Doubly Circular (DCLL)
(B) Traversal Loop Guard
(C) Single-Node CLL State
(D) Singly Circular (SCLL)
Correct Answer: (D)
[EN] In Circular Linked List: Singly Circular vs Doubly Circular Lists, 'Singly Circular (SCLL)' handles 'tail->next == head with 1 pointer per node' (O(1) front and end insert using last pointer).
[HI] Circular Linked List: Singly Circular vs Doubly Circular Lists में 'Singly Circular (SCLL)' का कार्य/विवरण 'tail->next == head with 1 pointer per node' (O(1) front and end insert using last pointer) है।
Q18. Which option accurately describes 'Doubly Circular (DCLL)' in Circular Linked List: Singly Circular vs Doubly Circular Lists?
(Circular Linked List: Singly Circular vs Doubly Circular Lists के संदर्भ में 'Doubly Circular (DCLL)' की सही विशेषता कौन सी है?)
(A) tail->next == head AND head->prev == tail
(B) do-while loop stopping when ptr == start
(C) node->next == node (self-loop)
(D) tail->next == head with 1 pointer per node
Correct Answer: (A)
[EN] 'Doubly Circular (DCLL)' provides 'tail->next == head AND head->prev == tail' — key point: Zero NULL pointers; tail via head->prev in O(1).
[HI] 'Doubly Circular (DCLL)' का मुख्य विवरण 'tail->next == head AND head->prev == tail' है (Zero NULL pointers; tail via head->prev in O(1))।
Q19. In Circular Linked List: Singly Circular vs Doubly Circular Lists, identify the correct parameter for the specification: "node->next == node (self-loop)".
(Circular Linked List: Singly Circular vs Doubly Circular Lists में "node->next == node (self-loop)" विवरण किस विकल्प के लिए सही है?)
(A) Singly Circular (SCLL)
(B) Doubly Circular (DCLL)
(C) Single-Node CLL State
(D) Traversal Loop Guard
Correct Answer: (C)
[EN] 'Single-Node CLL State' corresponds to 'node->next == node (self-loop)' (Deleting sole node resets external pointer to NULL).
[HI] 'Single-Node CLL State' का संबंध 'node->next == node (self-loop)' (Deleting sole node resets external pointer to NULL) से है।
Q20. Considering Circular Linked List: Singly Circular vs Doubly Circular Lists, what key behavior defines 'Traversal Loop Guard'?
(Circular Linked List: Singly Circular vs Doubly Circular Lists में 'Traversal Loop Guard' की मुख्य भूमिका या मान क्या है?)
(A) tail->next == head with 1 pointer per node
(B) do-while loop stopping when ptr == start
(C) tail->next == head AND head->prev == tail
(D) node->next == node (self-loop)
Correct Answer: (B)
[EN] 'Traversal Loop Guard' represents 'do-while loop stopping when ptr == start' (Using while(ptr != NULL) triggers infinite loop).
[HI] 'Traversal Loop Guard' का अर्थ/मान 'do-while loop stopping when ptr == start' है (Using while(ptr != NULL) triggers infinite loop)।
Circular Linked List: Singly Circular vs Doubly Circular Lists — Exam FAQs
Q1: Can you implement a Queue efficiently using a Singly Circular Linked List with just ONE pointer?
क्या केवल एक ही पॉइंटर वाली सिंगली सर्कुलर लिस्ट से कुशल Queue बनाई जा सकती है?
[EN] Yes! Using just a 'rear' pointer, enqueue inserts after 'rear' and moves rear = newNode in O(1), while dequeue removes rear->next (the front) in O(1).
[HI] हाँ! केवल 'rear' पॉइंटर से enqueue (rear के बाद जोड़कर rear आगे बढ़ाना) और dequeue (rear->next को हटाना) दोनों O(1) समय में हो जाते हैं।
Q2: How do you detect whether a given linked list is circular or NULL-terminated?
यह कैसे जांचते हैं कि कोई दी गई लिंक्ड लिस्ट सर्कुलर है या NULL पर समाप्त होती है?
[EN] Traverse with a pointer starting at head->next: if it reaches NULL, it is linear; if it returns to head, it is circular (or use Floyd's slow/fast pointers for general cycles).
[HI] head->next से आगे बढ़ें: यदि NULL मिले तो लिस्ट लीनियर है, और यदि वापस head पर पहुँच जाए तो यह सर्कुलर है।
Q3: What is the main disadvantage of a Circular Linked List compared to a linear linked list?
लीनियर लिंक्ड लिस्ट की तुलना में सर्कुलर लिंक्ड लिस्ट की मुख्य हानि क्या है?
[EN] Higher risk of infinite loops if traversal stop conditions (ptr != start) or single-node deletion edge cases are coded carelessly.
[HI] यदि लूप समाप्ति की शर्त (ptr != start) या एकल-नोड डिलीशन सावधानी से न लिखा जाए, तो अनंत लूप में फँसने का खतरा अधिक रहता है।
Post a Comment
Post a Comment