Doubly Linked List: নোড ম্যানিপুলেশন

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 একটি শক্তিশালী ডেটা স্ট্রাকচার যা উভমুখী ট্রাভার্সাল এবং ডেটা পরিচালনার জন্য সক্ষম। নোড ইনসার্ট, ডিলিট এবং ট্রাভার্স করার পদ্ধতিগুলি ব্যবহার করে আপনি বিভিন্ন ধরনের সমস্যা সমাধান করতে পারেন। এই কৌশলগুলি জানার মাধ্যমে আপনি ডাবল লিঙ্কড লিস্ট ব্যবহার করে আরও জটিল এবং কার্যকরী প্রোগ্রাম তৈরি করতে পারবেন।