সি তে ডেটা স্ট্রাকচার ইমপ্লিমেন্টেশন কৌশল

সি প্রোগ্রামিং ভাষায় ডেটা স্ট্রাকচারগুলোকে দক্ষভাবে বাস্তবায়ন করা খুবই গুরুত্বপূর্ণ, কারণ এটি অপটিমাইজড সফটওয়্যার সমাধান তৈরি করতে সাহায্য করে। ডেটা স্ট্রাকচারগুলি ডেটা সঞ্চয়, সংগঠন এবং ব্যবস্থাপনা করতে ব্যবহৃত হয়, যা ইনসারশন, ডিলিশন, সার্চিং এবং আপডেটিং অপারেশনগুলো কম সময়ে সম্পন্ন করতে সহায়ক।

এখানে কিছু সাধারণ ডেটা স্ট্রাকচার ইমপ্লিমেন্টেশন কৌশল নিয়ে আলোচনা করা হলো:

১. অ্যারে (Arrays)

অ্যারে হলো সবচেয়ে সাধারণ ডেটা স্ট্রাকচার যা এক ধরনের ডেটাকে ধারন করে একটি ধারাবাহিক মেমরি লোকেশনে। অ্যারে এলিমেন্টে দ্রুত অ্যাক্সেস করতে দেয়, তবে সাইজ ফিক্সড হওয়ায় এটি সীমাবদ্ধ হতে পারে।

অ্যারে ইমপ্লিমেন্টেশন:

#include <stdio.h>

int main() {
    int arr[5] = {1, 2, 3, 4, 5};

    // অ্যারে এলিমেন্ট অ্যাক্সেস করা
    for(int i = 0; i < 5; i++) {
        printf("Index %d: %d\n", i, arr[i]);
    }
    return 0;
}

• টাইম কমপ্লেক্সিটি:
  • অ্যাক্সেস: O(1)
  • ইনসারশন/ডিলিশন: O(n) (কারণ এলিমেন্ট শিফট করতে হয়)

২. লিংকড লিস্ট (Linked List)

লিংকড লিস্ট হলো একটি লিনিয়ার ডেটা স্ট্রাকচার, যেখানে প্রতিটি নোড ডেটা এবং পরবর্তী নোডের পয়েন্টার ধারণ করে। এটি ডেটাকে ডাইনামিকভাবে মেমরিতে ধারণ করে, এবং ইনসারশন/ডিলিশন অপারেশনগুলি দ্রুত হয়।

সিঙ্গলি লিংকড লিস্ট ইমপ্লিমেন্টেশন:

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

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

// লিস্ট প্রিন্ট করার ফাংশন
void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// লিস্টে নতুন নোড ইনসার্ট করার ফাংশন
void insertAtBeginning(struct Node** head, int newData) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = newData;
    newNode->next = *head;
    *head = newNode;
}

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

    insertAtBeginning(&head, 10);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 30);

    printList(head);
    return 0;
}

• টাইম কমপ্লেক্সিটি:
  • অ্যাক্সেস/সার্চ: O(n)
  • ইনসারশন/ডিলিশন: O(1) (শুরুতে)

৩. স্ট্যাক (Stack)

স্ট্যাক হলো একটি লিনিয়ার ডেটা স্ট্রাকচার যা Last In First Out (LIFO) নীতি অনুসরণ করে। স্ট্যাকের মধ্যে এলিমেন্ট কেবল স্ট্যাকের উপরে ঢোকানো বা বের করা যায়।

স্ট্যাক ইমপ্লিমেন্টেশন:

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

struct StackNode {
    int data;
    struct StackNode* next;
};

void push(struct StackNode** top, int newData) {
    struct StackNode* newNode = (struct StackNode*)malloc(sizeof(struct StackNode));
    newNode->data = newData;
    newNode->next = *top;
    *top = newNode;
}

int pop(struct StackNode** top) {
    if (*top == NULL) {
        printf("Stack Underflow\n");
        return -1;
    }
    struct StackNode* temp = *top;
    int popped = temp->data;
    *top = temp->next;
    free(temp);
    return popped;
}

void printStack(struct StackNode* top) {
    while (top != NULL) {
        printf("%d -> ", top->data);
        top = top->next;
    }
    printf("NULL\n");
}

int main() {
    struct StackNode* stack = NULL;

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("Stack: ");
    printStack(stack);

    printf("Popped: %d\n", pop(&stack));

    return 0;
}

• টাইম কমপ্লেক্সিটি:
  • পুশ/পপ: O(1)
  • সার্চ: O(n)

৪. কিউ (Queue)

কিউ হলো একটি লিনিয়ার ডেটা স্ট্রাকচার যা First In First Out (FIFO) নীতি অনুসরণ করে। কিউতে এলিমেন্ট কেবল এক প্রান্তে ঢোকানো এবং অন্য প্রান্ত থেকে বের করা হয়।

কিউ ইমপ্লিমেন্টেশন:

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

struct QueueNode {
    int data;
    struct QueueNode* next;
};

void enqueue(struct QueueNode** front, struct QueueNode** rear, int newData) {
    struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    newNode->data = newData;
    newNode->next = NULL;
    
    if (*rear == NULL) {
        *front = *rear = newNode;
        return;
    }
    (*rear)->next = newNode;
    *rear = newNode;
}

int dequeue(struct QueueNode** front) {
    if (*front == NULL) {
        printf("Queue Underflow\n");
        return -1;
    }
    struct QueueNode* temp = *front;
    int dequeued = temp->data;
    *front = temp->next;
    free(temp);
    return dequeued;
}

void printQueue(struct QueueNode* front) {
    while (front != NULL) {
        printf("%d -> ", front->data);
        front = front->next;
    }
    printf("NULL\n");
}

int main() {
    struct QueueNode* front = NULL;
    struct QueueNode* rear = NULL;

    enqueue(&front, &rear, 10);
    enqueue(&front, &rear, 20);
    enqueue(&front, &rear, 30);

    printf("Queue: ");
    printQueue(front);

    printf("Dequeued: %d\n", dequeue(&front));

    return 0;
}

• টাইম কমপ্লেক্সিটি:
  • এনকিউ/ডিকিউ: O(1)
  • সার্চ: O(n)

৫. হ্যাশ টেবিল (Hash Table)

হ্যাশ টেবিল একটি ডেটা স্ট্রাকচার যা কিওয়ালু জোড়ে ডেটা সঞ্চয় করে এবং দ্রুত অ্যাক্সেসের জন্য একটি হ্যাশ ফাংশন ব্যবহার করে। এটি ইনসারশন, সার্চ, এবং ডিলিশন অপারেশন দ্রুত করতে ব্যবহৃত হয়।

হ্যাশ টেবিল ইমপ্লিমেন্টেশন (চেনিং সহ):

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

#define TABLE_SIZE 10

struct Node {
    int key;
    int value;
    struct Node* next;
};

struct HashTable {
    struct Node* table[TABLE_SIZE];
};

int hash(int key) {
    return key % TABLE_SIZE;
}

void insert(struct HashTable* ht, int key, int value) {
    int index = hash(key);
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = ht->table[index];
    ht->table[index] = newNode;
}

int search(struct HashTable* ht, int key) {
    int index = hash(key);
    struct Node* temp = ht->table[index];
    while (temp != NULL) {
        if (temp->key == key) {
            return temp->value;
        }
        temp = temp->next;
    }
    return -1;  // Not found
}

int main() {
    struct HashTable ht = {0};

    insert(&ht, 1, 100);
    insert(&ht, 2, 200);
    insert(&ht, 12, 1200);

    printf("Value for key 2: %d\n", search(&ht, 2));
    printf("Value for key 12: %d\n", search(&ht, 12));
    printf("Value for key 5: %d\n", search(&ht, 5));

    return 0;
}

• **

টাইম কমপ্লেক্সিটি**:
- ইনসার্ট/সার্চ/ডিলিশন: O(1) (গড় ক্ষেত্রে)
- খারাপ ক্ষেত্রে: O(n) (যখন অনেক কোলিশন হয়)

৬. বাইনারি ট্রি (Binary Tree)

বাইনারি ট্রি হলো একটি হায়ারার্কিকাল ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডে সর্বাধিক দুটি সন্তান থাকতে পারে। বাইনারি সার্চ ট্রি (BST) হল এমন একটি ট্রি যেখানে প্রতিটি নোডের বাম সন্তানদের মান পিতার মানের চেয়ে ছোট এবং ডান সন্তানদের মান বড়।

বাইনারি সার্চ ট্রি (BST) ইমপ্লিমেন্টেশন:

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

struct Node* insert(struct Node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else {
        root->right = insert(root->right, data);
    }
    return root;
}

void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

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

    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 60);
    root = insert(root, 80);

    printf("Inorder traversal: ");
    inorder(root);
    printf("\n");

    return 0;
}

• টাইম কমপ্লেক্সিটি:
  • সার্চ/ইনসার্ট/ডিলিশন: O(log n) (গড় ক্ষেত্রে)
  • খারাপ ক্ষেত্রে (অপ্রতিসম্পন্ন ট্রি): O(n)

উপসংহার

• অ্যারে সরল ডেটা ধারণ করতে সাহায্য করে তবে সাইজ সীমাবদ্ধ।
• লিংকড লিস্ট ডাইনামিক ডেটা সঞ্চয় করতে সহায়ক, তবে অ্যাক্সেস করার জন্য traversal করতে হয়।
• স্ট্যাক এবং কিউ নির্দিষ্ট অর্ডারে কাজ পরিচালনা করতে ব্যবহৃত হয় (LIFO এবং FIFO)।
• হ্যাশ টেবিল দ্রুত অ্যাক্সেসের জন্য কিওয়ালু জোড়ে ডেটা সঞ্চয় করতে ব্যবহৃত হয়।
• বাইনারি সার্চ ট্রি (BST) দ্রুত অনুসন্ধান, ইনসার্ট এবং ডিলিশন করতে ব্যবহৃত হয়।

এই ডেটা স্ট্রাকচারগুলির প্রত্যেকটির শক্তি এবং সীমাবদ্ধতা রয়েছে, এবং এটি নির্ভর করে সমস্যার ধরন এবং প্রয়োজনীয় পারফরম্যান্সের উপর, কোন ডেটা স্ট্রাকচারটি ব্যবহৃত হবে।