Circular Linked List: নোড সংযোজন এবং অপসারণ

Circular Linked List হল একটি বিশেষ ধরনের লিঙ্কড লিস্ট যেখানে শেষ নোডের পয়েন্টার প্রথম নোডের দিকে নির্দেশ করে, ফলে এটি একটি সার্কেলের মতো তৈরি হয়। এটি সিঙ্গল বা ডাবল লিঙ্কড লিস্ট হতে পারে। সার্কুলার লিঙ্কড লিস্টে উপাদানগুলির মধ্যে পুনরাবৃত্তি করা সহজ এবং এটি বিভিন্ন ডেটা ব্যবস্থাপনার জন্য কার্যকর।

নিচে সিঙ্গল সার্কুলার লিঙ্কড লিস্টের জন্য নোড সংযোজন এবং অপসারণের পদ্ধতি বিস্তারিতভাবে আলোচনা করা হলো।

১. Circular Linked List এর নোডের গঠন

প্রথমে, Circular Linked List এর জন্য নোডের একটি গঠন তৈরি করতে হবে:

#include <stdio.h>
#include <stdlib.h>

// Node structure
struct Node {
    int data;              // Data part
    struct Node* next;     // Pointer to the next node
};

২. নোড সংযোজন (Node Insertion)

নতুন নোড যুক্ত করার জন্য বিভিন্ন পদ্ধতি রয়েছে: তালিকার শুরুতে এবং শেষের দিকে।

২.১ শুরুতে নোড সংযোজন

void insertAtBeginning(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Create new node
    newNode->data = newData;   // Assign data

    if (*head == NULL) { // If list is empty
        newNode->next = newNode; // Point to itself
    } else {
        struct Node* last = *head; // Find the last node
        while (last->next != *head) {
            last = last->next; // Traverse to the last node
        }
        last->next = newNode; // Link last node to new node
        newNode->next = *head; // Point new node to head
    }
    
    *head = newNode; // Move head to point to new node
}

২.২ শেষে নোড সংযোজন

void insertAtEnd(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Create new node
    newNode->data = newData;   // Assign data
    newNode->next = NULL;      // Initialize next as NULL

    if (*head == NULL) { // If list is empty
        newNode->next = newNode; // Point to itself
        *head = newNode; // Make new node the head
    } else {
        struct Node* last = *head; // Find the last node
        while (last->next != *head) {
            last = last->next; // Traverse to the last node
        }
        last->next = newNode; // Link last node to new node
        newNode->next = *head; // Point new node to head
    }
}

৩. নোড অপসারণ (Node Deletion)

Circular Linked List থেকে একটি নোড মুছে ফেলার জন্য, প্রথমে তালিকা থেকে নোড খুঁজে বের করতে হবে এবং তারপর মুছতে হবে।

উদাহরণ: একটি নির্দিষ্ট মানের নোড অপসারণ

void deleteNode(struct Node** head, int key) {
    if (*head == NULL) return; // If list is empty

    struct Node *temp = *head, *prev = NULL;

    // If head node itself holds the key to be deleted
    if (temp->data == key) {
        if (temp->next == *head) { // Only one node in the list
            free(temp);
            *head = NULL; // Update head
            return;
        } else {
            while (temp->next != *head) { // Find the last node
                temp = temp->next;
            }
            temp->next = (*head)->next; // Link last node to the next of head
            free(*head); // Free old head
            *head = temp->next; // Update head
        }
        return;
    }

    // Search for the key to be deleted, keep track of the previous node
    while (temp->next != *head && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    // If key was not present in linked list
    if (temp == *head) {
        printf("Key not found.\n");
        return;
    }

    // Unlink the node from linked list
    prev->next = temp->next; // Link previous node to next node
    free(temp); // Free memory
}

৪. ট্রাভার্স (Traversal)

Circular Linked List এর সব নোড প্রিন্ট করতে ট্রাভার্স করা হয়।

উদাহরণ:

void printList(struct Node* head) {
    if (head == NULL) return; // If list is empty

    struct Node* temp = head;
    do {
        printf("%d -> ", temp->data); // Print data
        temp = temp->next;             // Move to next node
    } while (temp != head);            // Stop when we come back to head

    printf("...\n"); // Indicate the circular nature
}

৫. পুরো প্রোগ্রাম উদাহরণ

#include <stdio.h>
#include <stdlib.h>

// Node structure
struct Node {
    int data;
    struct Node* next;
};

// Function to insert a node at the beginning
void insertAtBeginning(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;

    if (*head == NULL) {
        newNode->next = newNode; // Point to itself
        *head = newNode;
    } else {
        struct Node* last = *head;
        while (last->next != *head) {
            last = last->next; // Traverse to the last node
        }
        last->next = newNode; // Link last node to new node
        newNode->next = *head; // Point new node to head
    }
}

// Function to insert a node at the end
void insertAtEnd(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;

    if (*head == NULL) {
        newNode->next = newNode; // Point to itself
        *head = newNode;
    } else {
        struct Node* last = *head;
        while (last->next != *head) {
            last = last->next; // Traverse to the last node
        }
        last->next = newNode; // Link last node to new node
        newNode->next = *head; // Point new node to head
    }
}

// Function to delete a node
void deleteNode(struct Node** head, int key) {
    if (*head == NULL) return; // If list is empty

    struct Node *temp = *head, *prev = NULL;

    // If head node itself holds the key to be deleted
    if (temp->data == key) {
        if (temp->next == *head) {
            free(temp); // Only one node in the list
            *head = NULL; // Update head
            return;
        } else {
            while (temp->next != *head) {
                temp = temp->next; // Find the last node
            }
            temp->next = (*head)->next; // Link last node to the next of head
            free(*head); // Free old head
            *head = temp->next; // Update head
        }
        return;
    }

    // Search for the key to be deleted
    while (temp->next != *head && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == *head) {
        printf("Key not found.\n");
        return;
    }

    // Unlink the node from linked list
    prev->next = temp->next; // Link previous node to next node
    free(temp); // Free memory
}

// Function to print the circular linked list
void printList(struct Node* head) {
    if (head == NULL) return; // If list is empty

    struct Node* temp = head;
    do {
        printf("%d -> ", temp->data); // Print data
        temp = temp->next;             // Move to next node
    } while (temp != head);            // Stop when we come back to head

    printf("...\n"); // Indicate the circular nature
}

int main() {
    struct Node* head = NULL;

    insertAtEnd(&head, 1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);
    printf("Circular Linked List after inserting nodes: ");
    printList(head); // Output: 1 -> 2 -> 3 -> ...

    insertAtBeginning(&head, 0);
    printf("Circular Linked List after inserting at the beginning: ");
    printList(head); // Output: 0 -> 1 -> 2 -> 3 -> ...

    deleteNode(&head, 2);
    printf("Circular Linked List after deleting a node: ");
    printList(head); // Output: 0 -> 1 -> 3 -> ...

    return 0;
}