Singly Linked List: নোড ইনসার্ট, ডিলিট, এবং ট্রাভার্স

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