← Back to DSA Course | Chapter 4: Linked Lists | Lesson 3 of 8

Circular Linked List क्या है

एक circular linked list एक ring में हाथ पकड़े kids जैसी है: आखिरी वाला पहले वाले का हाथ पकड़ता है, इसलिए आप हमेशा के लिए round में जाते रह सकते हैं।

In this page:

  1. What is Circular Linked List
  2. Traversal
  3. Insertion
  4. Advantages
  5. Careful Traversal
Syntax
markup 
current = head
while True:
    process(current.data)
    current = current.next
    if current == head:
        break

What is Circular Linked List

एक circular linked list एक normal linked list जैसी structured है सिवाय इसके कि आखिरी node का next pointer null के बजाय वापस पहले node की ओर point करता है, एक straight line के बजाय एक continuous loop बनाते हुए।

उदाहरण: What is Circular Linked List

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* a = new Node{1, nullptr};
    Node* b = new Node{2, nullptr};
    Node* c = new Node{3, nullptr};
    a->next = b; b->next = c; c->next = a;
    cout << "last node points back to first: " << (c->next == a) << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2), c = new Node(3);
        a.next = b; b.next = c; c.next = a;
        System.out.println("last node points back to first: " + (c.next == a));
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

a, b, c = Node(1), Node(2), Node(3)
a.next = b
b.next = c
c.next = a
print("last node points back to first:", c.next is a)
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    struct Node *c = malloc(sizeof(struct Node));
    a->data = 1; b->data = 2; c->data = 3;
    a->next = b; b->next = c; c->next = a;
    printf("last node points back to first: %d\n", c->next == a);
    return 0;
}

Traversal

चूंकि 'रुको' signal करने के लिए आखिर में कोई null नहीं, traversal को explicitly जांचना पड़ता है कि आप उस node पर वापस आए हैं या नहीं जहां से शुरू किया था, नहीं तो एक naive loop हमेशा के लिए चलेगा।

उदाहरण: Traversal

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* a = new Node{1, nullptr};
    Node* b = new Node{2, nullptr};
    Node* c = new Node{3, nullptr};
    a->next = b; b->next = c; c->next = a;
    Node* curr = a;
    do {
        cout << curr->data << " ";
        curr = curr->next;
    } while (curr != a);
    cout << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2), c = new Node(3);
        a.next = b; b.next = c; c.next = a;
        Node curr = a;
        do {
            System.out.print(curr.data + " ");
            curr = curr.next;
        } while (curr != a);
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

a, b, c = Node(1), Node(2), Node(3)
a.next = b
b.next = c
c.next = a
curr = a
while True:
    print(curr.data, end=" ")
    curr = curr.next
    if curr is a:
        break
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    struct Node *c = malloc(sizeof(struct Node));
    a->data = 1; b->data = 2; c->data = 3;
    a->next = b; b->next = c; c->next = a;
    struct Node *curr = a;
    do {
        printf("%d ", curr->data);
        curr = curr->next;
    } while (curr != a);
    printf("\n");
    return 0;
}

Insertion

एक circular list में एक नया node insert करने का मतलब बस loop संरक्षित करते हुए नए node से होकर route करने के लिए appropriate next pointers redirect करना है, जो अक्सर end पर simpler है क्योंकि handle करने के लिए कोई special null case नहीं।

उदाहरण: Insertion

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* a = new Node{1, nullptr};
    Node* b = new Node{2, nullptr};
    a->next = b; b->next = a;
    Node* n = new Node{99, nullptr};
    n->next = b->next;
    b->next = n;
    cout << "inserted after b: " << b->next->data << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2);
        a.next = b; b.next = a;
        Node n = new Node(99);
        n.next = b.next;
        b.next = n;
        System.out.println("inserted after b: " + b.next.data);
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

a, b = Node(1), Node(2)
a.next = b
b.next = a
n = Node(99)
n.next = b.next
b.next = n
print("inserted after b:", b.next.data)
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    a->data = 1; b->data = 2;
    a->next = b; b->next = a;
    struct Node *n = malloc(sizeof(struct Node));
    n->data = 99;
    n->next = b->next;
    b->next = n;
    printf("inserted after b: %d\n", b->next->data);
    return 0;
}

Advantages

चूंकि कोई भी node पूरे sequence में वापस एक natural entry point के रूप में काम कर सकता है, circular lists उन चीज़ों के लिए एक अच्छा fit हैं जो बार-बार cycle करती हैं, जैसे round-robin CPU scheduling या एक rotating playlist।

उदाहरण: Advantages

#include <iostream>
using namespace std;
struct Node { int id; Node* next; };
int main() {
    Node* p1 = new Node{1, nullptr};
    Node* p2 = new Node{2, nullptr};
    Node* p3 = new Node{3, nullptr};
    p1->next = p2; p2->next = p3; p3->next = p1;
    Node* curr = p1;
    for (int round = 0; round < 2; round++) {
        for (int i = 0; i < 3; i++) {
            cout << "running process " << curr->id << endl;
            curr = curr->next;
        }
    }
    return 0;
}
class Node { int id; Node next; Node(int i) { id = i; } }
public class Main {
    public static void main(String[] args) {
        Node p1 = new Node(1), p2 = new Node(2), p3 = new Node(3);
        p1.next = p2; p2.next = p3; p3.next = p1;
        Node curr = p1;
        for (int round = 0; round < 2; round++) {
            for (int i = 0; i < 3; i++) {
                System.out.println("running process " + curr.id);
                curr = curr.next;
            }
        }
    }
}
class Node:
    def __init__(self, id_):
        self.id = id_
        self.next = None

p1, p2, p3 = Node(1), Node(2), Node(3)
p1.next = p2
p2.next = p3
p3.next = p1
curr = p1
for _ in range(2):
    for _ in range(3):
        print("running process", curr.id)
        curr = curr.next
#include <stdio.h>
#include <stdlib.h>
struct Node { int id; struct Node *next; };
int main() {
    struct Node *p1 = malloc(sizeof(struct Node));
    struct Node *p2 = malloc(sizeof(struct Node));
    struct Node *p3 = malloc(sizeof(struct Node));
    p1->id = 1; p2->id = 2; p3->id = 3;
    p1->next = p2; p2->next = p3; p3->next = p1;
    struct Node *curr = p1;
    for (int round = 0; round < 2; round++)
        for (int i = 0; i < 3; i++) {
            printf("running process %d\n", curr->id);
            curr = curr->next;
        }
    return 0;
}

Careful Traversal

Circular lists के साथ सबसे आम bug एक ordinary linked-list traversal pattern उपयोग करना है जो null जांचता है: चूंकि वह condition कभी true नहीं होती, आपको इसके बजाय explicitly starting node track और compare करना होगा।

उदाहरण: Careful Traversal

#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
    Node* a = new Node{1, nullptr};
    Node* b = new Node{2, nullptr};
    a->next = b; b->next = a;
    int count = 0;
    Node* curr = a;
    do {
        count++;
        curr = curr->next;
    } while (curr != a && count < 10);
    cout << "visited " << count << " nodes (never null, so we compare to start)" << endl;
    return 0;
}
class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
    public static void main(String[] args) {
        Node a = new Node(1), b = new Node(2);
        a.next = b; b.next = a;
        int count = 0;
        Node curr = a;
        do {
            count++;
            curr = curr.next;
        } while (curr != a && count < 10);
        System.out.println("visited " + count + " nodes (never null, so we compare to start)");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

a, b = Node(1), Node(2)
a.next = b
b.next = a
count = 0
curr = a
while True:
    count += 1
    curr = curr.next
    if curr is a or count >= 10:
        break
print("visited", count, "nodes (never None, so we compare to start)")
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
    struct Node *a = malloc(sizeof(struct Node));
    struct Node *b = malloc(sizeof(struct Node));
    a->data = 1; b->data = 2;
    a->next = b; b->next = a;
    int count = 0;
    struct Node *curr = a;
    do {
        count++;
        curr = curr->next;
    } while (curr != a && count < 10);
    printf("visited %d nodes (never NULL, so we compare to start)\n", count);
    return 0;
}
Related Topics

Doubly Linked List क्या है · Linked List को Reverse करना · Singly Linked List क्या है · Linked List का Middle ढूँढना

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. while (cur != nullptr) से traverse करना, जो कभी खत्म नहीं होता क्योंकि आखिरी node वापस head की ओर point करता है।
  2. एक while loop उपयोग करना जो पहले step से पहले head जांचता है, इसलिए loop बिल्कुल नहीं चलता (एक do-while चाहिए)।
  3. आखिर में insert करते समय नए आखिरी node को head की ओर point करना भूल जाना।
🔒

Chapter Quiz — Complete all 8 topics to unlock

0/8 topics done

Complete these topics first:

← Previous Lesson Doubly Linked List Next Lesson → Linked List Reversal

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.