লিঙ্কড লিস্ট (Linked List in C)

লিঙ্কড লিস্ট হল একটি ডেটা স্ট্রাকচার যা বিভিন্ন উপাদানকে সংযুক্ত করে রাখে। প্রতিটি উপাদান (নোড) একটি মান এবং পরবর্তী উপাদানের ঠিকানা ধারণ করে। এটি একটি ডাইনামিক ডেটা স্ট্রাকচার, অর্থাৎ এর সাইজ প্রোগ্রাম চলাকালীন সময়ে পরিবর্তনশীল। নিচে C প্রোগ্রামিং ভাষায় লিঙ্কড লিস্টের ধারণা, প্রকারভেদ, এবং ব্যবহার নিয়ে বিস্তারিত আলোচনা করা হলো।

১. লিঙ্কড লিস্ট কি?

লিঙ্কড লিস্ট হল একটি সিরিজ নোডের সংযোগ, যেখানে প্রতিটি নোড একটি ডেটা অংশ এবং একটি পয়েন্টার অংশ ধারণ করে। পয়েন্টারটি পরবর্তী নোডের ঠিকানাকে নির্দেশ করে। এটি অ্যারে থেকে আলাদা, কারণ এতে ডেটার জন্য পরপর মেমরি ব্লকগুলির প্রয়োজন হয় না।

২. লিঙ্কড লিস্টের প্রকারভেদ

সিঙ্গল লিঙ্কড লিস্ট (Singly Linked List):

• প্রতিটি নোড কেবল পরবর্তী নোডের পয়েন্টার ধারণ করে।

ডাবল লিঙ্কড লিস্ট (Doubly 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
};

৩.২ নতুন নোড তৈরি করা

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Memory allocation
    newNode->data = data;  // Set data
    newNode->next = NULL;  // Initialize next pointer
    return newNode;        // Return new node
}

৩.৩ লিঙ্কড লিস্টে নোড যুক্ত করা

void insertAtEnd(struct Node** head, int data) {
    struct Node* newNode = createNode(data); // Create new node

    if (*head == NULL) {
        *head = newNode; // If list is empty, make new node the head
        return;
    }

    struct Node* last = *head; // Traverse to the last node
    while (last->next != NULL) {
        last = last->next;
    }

    last->next = newNode; // Link the new node at the end
}

৩.৪ লিঙ্কড লিস্ট প্রিন্ট করা

void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data); // Print data
        node = node->next;             // Move to next node
    }
    printf("NULL\n"); // End of the list
}

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

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

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

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to insert a new node at the end
void insertAtEnd(struct Node** head, int data) {
    struct Node* newNode = createNode(data);

    if (*head == NULL) {
        *head = newNode;
        return;
    }

    struct Node* last = *head;
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = newNode;
}

// Function to print the linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

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

    insertAtEnd(&head, 1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);

    printf("Linked List: ");
    printList(head); // Output: Linked List: 1 -> 2 -> 3 -> NULL

    return 0;
}

৫. লিঙ্কড লিস্টের সুবিধা এবং অসুবিধা

সুবিধা:

• ডাইনামিক সাইজ: অ্যারের মতো পূর্ব নির্ধারিত সাইজের প্রয়োজন হয় না।
• ইনসার্ট এবং ডিলিট: নোড ইনসার্ট এবং ডিলিট করা সহজ এবং দ্রুত।

অসুবিধা:

• মেমরি ব্যবহারের সমস্যা: অতিরিক্ত মেমরি ব্যবহার হতে পারে কারণ প্রতিটি নোডের জন্য পয়েন্টার সংরক্ষণ করতে হয়।
• অ্যাক্সেস টাইম: অ্যারের তুলনায় ডেটা অ্যাক্সেসের গতি ধীর।

লিঙ্কড লিস্ট হল একটি ডেটা স্ট্রাকচার যা ডেটার উপাদানগুলোকে (নোড) একত্রে সংযুক্ত করে রাখে। প্রতিটি নোডে একটি মান (ডেটা) এবং পরবর্তী নোডের পয়েন্টার (ঠিকানা) থাকে। এটি অ্যারের থেকে ভিন্ন, কারণ এতে পূর্বনির্ধারিত সাইজের প্রয়োজন হয় না এবং এটি ডাইনামিকভাবে মেমরি বরাদ্দ করতে সক্ষম।

লিঙ্কড লিস্ট ব্যবহার করে বিভিন্ন ধরনের ডেটা সংগঠনের কৌশল তৈরি করা হয়। নিচে লিঙ্কড লিস্টের ধারণা এবং এর প্রকারভেদ বিস্তারিতভাবে আলোচনা করা হলো।

১. লিঙ্কড লিস্টের ধারণা

লিঙ্কড লিস্টে প্রতিটি উপাদান (নোড) একটি পয়েন্টার ধারণ করে, যা পরবর্তী নোডের ঠিকানাকে নির্দেশ করে। প্রথম নোডটিকে হেড (head) বলা হয়, যা লিঙ্কড লিস্টের শুরুতে অবস্থিত। লিঙ্কড লিস্টের সুবিধা হল এটি ডাইনামিক সাইজিং সমর্থন করে এবং উপাদান যুক্ত বা মুছে ফেলা সহজ।

লিঙ্কড লিস্টের বৈশিষ্ট্য:

• ডাইনামিক সাইজ: লিঙ্কড লিস্টের সাইজ প্রোগ্রাম চলাকালীন সময়ে পরিবর্তিত হতে পারে।
• মেমরি ব্যবস্থাপনা: নতুন নোড তৈরি করার সময় মেমরি বরাদ্দ করা হয়, এবং নোড ডিলেট করার সময় মেমরি মুক্ত করা হয়।
• দ্রুত ইনসার্ট এবং ডিলিট: লিঙ্কড লিস্টে নোড যুক্ত বা মুছে ফেলা অ্যারের তুলনায় দ্রুত হয়, কারণ এটি পুনর্বিন্যাস করতে হয় না।

২. লিঙ্কড লিস্টের প্রকারভেদ

লিঙ্কড লিস্টের বিভিন্ন প্রকার রয়েছে, এবং প্রতিটি প্রকারের নিজস্ব বৈশিষ্ট্য ও প্রয়োগ রয়েছে। প্রধান প্রকারগুলি হলো:

২.১ সিঙ্গল লিঙ্কড লিস্ট (Singly Linked List)

সিঙ্গল লিঙ্কড লিস্ট হল একটি নোডের তালিকা যেখানে প্রতিটি নোড কেবল পরবর্তী নোডের পয়েন্টার ধারণ করে। এর ফলে এটি একমুখী ডেটা প্রবাহ তৈরি করে।

• নোড স্ট্রাকচার:

struct Node {    int data; // ডেটা অংশ    struct Node* next; // পরবর্তী নোডের পয়েন্টার };

২.২ ডাবল লিঙ্কড লিস্ট (Doubly Linked List)

ডাবল লিঙ্কড লিস্ট হল একটি নোডের তালিকা যেখানে প্রতিটি নোড পূর্ববর্তী এবং পরবর্তী উভয় নোডের পয়েন্টার ধারণ করে। এর ফলে এটি উভমুখী ডেটা প্রবাহ তৈরি করে।

• নোড স্ট্রাকচার:

struct Node {    int data; // ডেটা অংশ    struct Node* next; // পরবর্তী নোডের পয়েন্টার    struct Node* prev; // পূর্ববর্তী নোডের পয়েন্টার };

২.৩ সার্কুলার লিঙ্কড লিস্ট (Circular Linked List)

সার্কুলার লিঙ্কড লিস্ট হল একটি সিঙ্গল বা ডাবল লিঙ্কড লিস্ট যেখানে শেষ নোডের পরবর্তী পয়েন্টার প্রথম নোডকে নির্দেশ করে। এটি একটি সার্কেলের মতো তৈরি করে।

• নোড স্ট্রাকচার:

struct Node {    int data; // ডেটা অংশ    struct Node* next; // পরবর্তী নোডের পয়েন্টার };

২.৪ সার্কুলার ডাবল লিঙ্কড লিস্ট (Circular Doubly Linked List)

সার্কুলার ডাবল লিঙ্কড লিস্ট হল একটি ডাবল লিঙ্কড লিস্ট যেখানে শেষ নোডের পরবর্তী পয়েন্টার প্রথম নোড এবং প্রথম নোডের পূর্ববর্তী পয়েন্টার শেষ নোডকে নির্দেশ করে।

• নোড স্ট্রাকচার:

struct Node {
    int data; // ডেটা অংশ
    struct Node* next; // পরবর্তী নোডের পয়েন্টার
    struct Node* prev; // পূর্ববর্তী নোডের পয়েন্টার
};

Singly 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
    newNode->next = *head;     // Point to old 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));
    newNode->data = newData;   // Assign data
    newNode->next = NULL;      // New node will be the last, so next is NULL

    if (*head == NULL) {
        *head = newNode;       // If list is empty, new node is head
        return;
    }

    struct Node* last = *head; // Traverse to the last node
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = newNode;       // Change the next of last node
}

২.৩ নির্দিষ্ট অবস্থানে নোড ইনসার্ট করা

void insertAtPosition(struct Node** head, int newData, int position) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;

    if (position == 0) {
        newNode->next = *head; // Insert at the beginning
        *head = newNode;
        return;
    }

    struct Node* current = *head;
    for (int i = 0; i < position - 1 && current != NULL; i++) {
        current = current->next; // Traverse to the position
    }

    if (current == NULL) {
        printf("The previous node is null.\n");
        return;
    }

    newNode->next = current->next; // Link new node to the next of current
    current->next = newNode;        // Link current to new node
}

৩. নোড ডিলিট (Node Deletion)

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

৩.১ একটি নির্দিষ্ট মানের নোড ডিলিট করা

void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head, *prev = NULL;

    // If head node itself holds the key to be deleted
    if (temp != NULL && temp->data == key) {
        *head = temp->next; // Changed head
        free(temp);         // Free old head
        return;
    }

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

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

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

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

লিঙ্কড লিস্টের সব নোড প্রিন্ট করতে ট্রাভার্স করা হয়।

উদাহরণ:

void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data); // Print data
        node = node->next;             // Move to next node
    }
    printf("NULL\n"); // End of the list
}

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

#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;
    newNode->next = *head;
    *head = newNode;
}

// 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;
    newNode->next = NULL;

    if (*head == NULL) {
        *head = newNode;
        return;
    }

    struct Node* last = *head;
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = newNode;
}

// Function to delete a node
void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head, *prev = NULL;

    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

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

    prev->next = temp->next;
    free(temp);
}

// Function to print the linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

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

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

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

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

    return 0;
}

Doubly Linked List হল একটি বিশেষ ধরনের ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডের দুটি পয়েন্টার থাকে: একটি পূর্ববর্তী নোডের জন্য এবং অন্যটি পরবর্তী নোডের জন্য। এর ফলে এটি উভমুখী ট্রাভার্সাল (traversal) করার সুযোগ প্রদান করে। নিচে ডাবল লিঙ্কড লিস্টের জন্য নোড ইনসার্ট, ডিলিট এবং ট্রাভার্স করার পদ্ধতি বিস্তারিতভাবে আলোচনা করা হলো।

১. ডাবল লিঙ্কড লিস্টের নোডের গঠন

প্রথমে, ডাবল লিঙ্কড লিস্টের জন্য নোডের একটি গঠন তৈরি করতে হবে:

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

// Node structure
struct Node {
    int data;               // Data part
    struct Node* next;      // Pointer to the next node
    struct Node* prev;      // Pointer to the previous 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

    newNode->next = *head;     // Point to the old head
    newNode->prev = NULL;      // Previous of new node is NULL

    if (*head != NULL) {       // If list is not empty
        (*head)->prev = newNode; // Update previous of 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
    struct Node* last = *head; // Used to traverse to the last node

    newNode->data = newData;   // Assign data
    newNode->next = NULL;      // New node will be the last, so next is NULL

    if (*head == NULL) {       // If list is empty
        newNode->prev = NULL;  // New node becomes head
        *head = newNode;
        return;
    }

    while (last->next != NULL) { // Traverse to the last node
        last = last->next;
    }

    last->next = newNode;       // Link the new node at the end
    newNode->prev = last;       // Link the last node to the new node
}

২.৩ নির্দিষ্ট অবস্থানে নোড ইনসার্ট করা

void insertAtPosition(struct Node** head, int newData, int position) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;

    if (position == 0) {
        insertAtBeginning(head, newData);
        return;
    }

    struct Node* current = *head;
    for (int i = 0; i < position - 1 && current != NULL; i++) {
        current = current->next; // Traverse to the position
    }

    if (current == NULL) {
        printf("The previous node is null.\n");
        return;
    }

    newNode->next = current->next; // Link new node to the next of current
    newNode->prev = current;        // Link current to the new node
    if (current->next != NULL) {
        current->next->prev = newNode; // Link next node back to new node
    }
    current->next = newNode;       // Link current to new node
}

৩. নোড ডিলিট (Node Deletion)

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

উদাহরণ:

void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head;

    // If head node itself holds the key to be deleted
    if (temp != NULL && temp->data == key) {
        *head = temp->next; // Change head
        if (*head != NULL) { // If there is a next node
            (*head)->prev = NULL; // Update previous of new head
        }
        free(temp); // Free old head
        return;
    }

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

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

    // Unlink the node from linked list
    if (temp->next != NULL) {
        temp->next->prev = temp->prev; // Update previous pointer of next node
    }
    if (temp->prev != NULL) {
        temp->prev->next = temp->next; // Update next pointer of previous node
    }
    free(temp); // Free memory
}

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

ডাবল লিঙ্কড লিস্টের সব নোড প্রিন্ট করতে ট্রাভার্স করা হয়।

উদাহরণ:

void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d <-> ", node->data); // Print data
        node = node->next;              // Move to next node
    }
    printf("NULL\n"); // End of the list
}

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

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

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

// 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;
    newNode->next = *head;
    newNode->prev = NULL;

    if (*head != NULL) {
        (*head)->prev = newNode; // Update previous of head
    }

    *head = newNode; // Move head to point to new node
}

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

    newNode->data = newData;
    newNode->next = NULL;

    if (*head == NULL) {
        newNode->prev = NULL;
        *head = newNode;
        return;
    }

    while (last->next != NULL) {
        last = last->next;
    }
    last->next = newNode;
    newNode->prev = last; // Link the last node to new node
}

// Function to delete a node
void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head;

    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        if (*head != NULL) {
            (*head)->prev = NULL; // Update previous of new head
        }
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        temp = temp->next;
    }

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

    if (temp->next != NULL) {
        temp->next->prev = temp->prev; // Update previous pointer of next node
    }
    if (temp->prev != NULL) {
        temp->prev->next = temp->next; // Update next pointer of previous node
    }
    free(temp); // Free memory
}

// Function to print the doubly linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d <-> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

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

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

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

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

    return 0;
}

উপসংহার

Doubly 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;
}