22. Linked List - Circular

Circular Linked List হলো এমন একটি ডেটা স্ট্রাকচার যেখানে শেষ নোডটি তার পরের নোডের বদলে পুনরায় প্রথম নোড বা Head-কে পয়েন্ট করে। ফলে এটি একটি লুপ বা সার্কেল তৈরি করে।

---

1. সার্কুলার লিঙ্কড লিস্ট কি? (What is Circular Linked List?)

সাধারণ লিঙ্কড লিস্টের শেষ নোড null পয়েন্ট করে, কিন্তু সার্কুলার লিঙ্কড লিস্টে কোনো null থাকে না। লিস্টের শেষ নোড আবার প্রথম নোডের অ্যাড্রেস হোল্ড করে।

Node Structure

// Java Circular Node
class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

# Python Circular Node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

---

2. প্রকারভেদ (Types)

Singly Circular

প্রতিটি নোড শুধু পরের নোডকে পয়েন্ট করে এবং শেষ নোডটি হেডকে পয়েন্ট করে।

Doubly Circular

প্রতিটি নোড আগে ও পরে পয়েন্ট করে। এখানে শেষ নোডের next হেডে এবং হেডের prev শেষ নোডে পয়েন্ট করে।

---

3. ট্রাভার্সাল টেকনিক (Traversal)

সার্কুলার লিস্টে ট্রাভার্স করার সময় সাবধানে থাকতে হয় কারণ এখানে কোনো null নেই, তাই লুপ ইনফিনিট হয়ে যেতে পারে।

🛠 কর্মপদ্ধতি (Step-by-Step Logic)

1. একটি টেম্পোরারি পয়েন্টার curr হেডে রাখুন।
2. একটি do-while লুপ ব্যবহার করুন (অথবা প্রথমবার ডাটা প্রিন্ট করে লুপ শুরু করুন)।
3. যতক্ষণ curr পুনরায় হেডে না ফিরে আসে, ততক্ষণ ট্রাভার্স করতে থাকুন।

Implementation

// Java Circular Traversal
public void printList(Node head) {
    if (head == null) return;
    Node curr = head;
    do {
        System.out.print(curr.data + " ");
        curr = curr.next;
    } while (curr != head);
}

# Python Circular Traversal
def print_list(head):
    if not head: return
    curr = head
    while True:
        print(curr.data, end=" ")
        curr = curr.next
        if curr == head: break

---

4. ইনসার্শন এবং ডিলিশন (Insertion & Deletion)

ইনসার্ট করার সময় সবচেয়ে গুরুত্বপূর্ণ হলো শেষ নোড বা Tail খুঁজে বের করা এবং সেটির কানেকশন আপডেট করা।

• Insert at Head: নতুন নোড তৈরি করুন এবং শেষ নোডের next হিসেবে এটি সেট করুন।
• Deletion: যদি হেড ডিলিট করতে হয়, তবে টেইল খুঁজে বের করে তার next নতুন হেডে সেট করতে হবে।

Implementation

// Java Circular Insertion (at end)
public Node insertAtEnd(Node head, int data) {
    Node newNode = new Node(data);
    if (head == null) {
        newNode.next = newNode;
        return newNode;
    }
    Node curr = head;
    while (curr.next != head) curr = curr.next;
    curr.next = newNode;
    newNode.next = head;
    return head;
}

# Python Circular Insertion (at end)
def insert_at_end(head, data):
    new_node = Node(data)
    if not head:
        new_node.next = new_node
        return new_node
    curr = head
    while curr.next != head:
        curr = curr.next
    curr.next = new_node
    new_node.next = head
    return head

---

5. ব্যবহারের ক্ষেত্র (Use Cases)

• Round Robin Scheduling: অপারেটিং সিস্টেমে প্রসেস শিডিউলিং করার জন্য।
• Multiplayer Games: প্লেয়ারদের এক এক করে সুযোগ দেওয়ার জন্য।
• Streaming Media: যখন একটি প্লেলিস্ট শেষ হওয়ার পর পুনরায় প্রথম গান থেকে শুরু হয়।

---

6. জোসেফাস প্রবলেম (Josephus Problem)

এটি একটি বিখ্যাত সমস্যা যা সার্কুলার লিঙ্কড লিস্টের মাধ্যমে সমাধান করা যায়।

• এন (N) সংখ্যক মানুষ একটি বৃত্তে দাঁড়িয়ে থাকে।
• প্রতি কে (K)-তম মানুষকে বাদ দেওয়া হয়।
• শেষ পর্যন্ত কে বেঁচে থাকবে তা বের করতে হয়।

📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)

• Time Complexity: O(n * k)
• Space Complexity: O(n) (লিঙ্কড লিস্ট স্টোর করার জন্য)।

---

📊 কমপ্লেক্সিটি অ্যানালাইসিস (General Complexity)

Operation	Time Complexity
Search/Access	O(n)
Insert at Beginning	O(1) (যদি টেইল পয়েন্টার মেইনটেইন করা হয়)
Deletion	O(n)

---

IMPORTANT

সার্কুলার লিঙ্কড লিস্টের সবচেয়ে বড় সুবিধা হলো, যে কোনো নোড থেকে শুরু করলে সম্পূর্ণ লিস্ট ট্রাভার্স করা সম্ভব।

---

TIP

কোড করার সময় একটি Tail পয়েন্টার মেইনটেইন করলে হেড এবং টেইল উভয় জায়গায় ইনসারশন অনেক বেশি ফাস্ট হয়।