ডেটা স্ট্রাকচার

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

সঠিক ডেটা স্ট্রাকচার নির্বাচনের তিনটি প্রধান শর্ত: (১) ডেটার পরিমাণ ও তাদের অভ্যন্তরীণ সম্পর্ক, (২) মৌলিক অপারেশনগুলোর পুনরাবৃত্তির হার (যেমন অনুসন্ধান, সন্নিবেশ, মোচন), এবং (৩) সিস্টেম রিসোর্সের সীমাবদ্ধতা (সিপিইউ সময় ও মেমরির ব্যবহার)।

ডেটা স্ট্রাকচারকে মূলত দুটি স্তরে বিভক্ত করা হয়:

• প্রিমিটিভ ডেটা স্ট্রাকচার: যেসব মৌলিক ডেটা টাইপ সরাসরি কম্পিউটার হার্ডওয়্যার ও মেশিন নির্দেশনা দ্বারা সমর্থিত। যেমন C ভাষায় int, float, char, double এবং পয়েন্টার মেমরি অ্যাড্রেস। এরা প্রতিটি মুহূর্তে একটিমাত্র পরমাণবিক (atomic) মান ধারণ করে।
• নন-প্রিমিটিভ ডেটা স্ট্রাকচার: একাধিক সমজাতীয় বা অসমজাতীয় ডেটা উপাদান সুসংগঠিত করার জন্য প্রিমিটিভ টাইপ থেকে উদ্ভূত জটিল কাঠামো। এগুলোকে আবার দুই ভাগে ভাগ করা হয়:

যেকোনো ডেটা স্ট্রাকচারের উপর প্রধান ছয়টি অপারেশন পরিচালিত হয়:

1. ট্রাভার্সিং (Traversing): কাঠামোর প্রতিটি উপাদানকে অন্তত একবার পরিদর্শন ও প্রক্রিয়াকরণ করা (যেমন প্রিন্ট করা বা যোগফল নির্ণয়)।
2. ইনসার্শন (Insertion): ডেটা স্ট্রাকচারের নির্দিষ্ট অবস্থানে একটি নতুন ডেটা উপাদান যুক্ত করা।
3. ডিলিশন (Deletion): ডেটা স্ট্রাকচার থেকে কোনো বিদ্যমান উপাদান অপসারণ করা।
4. সার্চিং (Searching): প্রদত্ত টার্গেট কি-এর মান অনুসারে কোনো উপাদানের উপস্থিতি বা মেমরি অবস্থান খুঁজে বের করা (লিনিয়ার ও বাইনারি সার্চ)।
5. সর্টিং (Sorting): উপাদানগুলোকে কোনো নির্দিষ্ট যৌক্তিক ক্রমে (ঊর্ধ্বক্রম বা নিম্নক্রম) সাজানো (বাবল, সিলেকশন, ইনসার্শন সর্ট)।
6. মার্জিং (Merging): দুটি ভিন্ন সাজানো ডেটা তালিকাকে একত্রিত করে একটি একক সাজানো তালিকা তৈরি করা।

একমাত্রিক অ্যারে হলো একই ডেটা টাইপের সমজাতীয় উপাদানের একটি নির্দিষ্ট আকারের অবিচ্ছিন্ন মেমরি ব্লক। C ভাষায় অ্যারের ইনডেক্স সর্বদা 0 থেকে শুরু হয়, অর্থাৎ $N$ আকারের একটি অ্যারের ইনডেক্স সীমা হলো $0, 1, 2, \dots, N-1$।

যেহেতু সমস্ত উপাদান মেমরিতে পাশাপাশি অবিচ্ছিন্নভাবে থাকে, তাই যেকোনো ইনডেক্স $A[i]$-এর মেমরি ঠিকানা মধ্যবর্তী উপাদান পরিদর্শন না করেই সরাসরি গাণিতিক সূত্রের মাধ্যমে $O(1)$ কনস্ট্যান্ট সময়ে বের করা সম্ভব।

যদি অ্যারে $A$-এর বেস অ্যাড্রেস $B$ (প্রথম উপাদানের মেমরি ঠিকানা), নিম্নসীমা $\text{LB}$ (C ভাষায় $\text{LB} = 0$) এবং প্রতিটি উপাদানের সাইজ $W$ বাইট হয়:

উদাহরণস্বরূপ, যদি int marks[50]-এর বেস অ্যাড্রেস $2000$ হয় এবং প্রতিটি ইন্টিজার $4$ বাইট ($W=4, \text{LB}=0$) গ্রহণ করে, তবে $marks[15]$-এর ঠিকানা হবে:

$$\text{Loc}(marks[15]) = 2000 + (15 - 0) \times 4 = 2000 + 60 = 2060$$

অ্যালগরিদম ১: নির্দিষ্ট স্থানে উপাদান সন্নিবেশ (Insertion at Position $k$)

$N$ উপাদানবিশিষ্ট একটি অ্যারের $k$ ইনডেক্সে নতুন মান বসাতে হলে $N-1$ থেকে $k$ পর্যন্ত সমস্ত উপাদানকে এক ঘর ডানদিকে সরাতে (Shift right) হয়:

for (int i = N - 1; i >= k; i--) {
    A[i + 1] = A[i]; // ডানদিকে স্থানান্তর
}
A[k] = new_value;
N++; // মোট সংখ্যা বৃদ্ধি

টাইম কমপ্লেক্সিটি: বেস্ট কেস $O(1)$ (শেষে যোগ করলে), ওয়ার্স্ট কেস $O(n)$ (শুরুতে যোগ করলে সমস্ত উপাদান সরাতে হয়)।

অ্যালগরিদম ২: নির্দিষ্ট স্থান থেকে উপাদান মোচন (Deletion at Position $k$)

$k$ ইনডেক্সের উপাদান অপসারণ করতে হলে $k+1$ থেকে $N-1$ পর্যন্ত সমস্ত উপাদানকে এক ঘর বামদিকে সরাতে (Shift left) হয়:

for (int i = k; i < N - 1; i++) {
    A[i] = A[i + 1]; // বামদিকে স্থানান্তর
}
N--; // মোট সংখ্যা হ্রাস

দ্বিমাত্রিক অ্যারে হলো $M$ সারি (Rows) এবং $N$ কলামের (Columns) একটি ম্যাট্রিক্স, C ভাষায় যা int A[M][N] দ্বারা ঘোষিত হয়। কিন্তু কম্পিউটারের ফিজিক্যাল মেমরি (RAM) একমাত্রিক হওয়ায় কম্পাইলারকে দ্বিমাত্রিক গ্রিডকে রৈখিক ধারায় সাজাতে হয়। এর জন্য দুটি পদ্ধতি রয়েছে:

1. রো-মেজর অর্ডার (Row-Major Order - RMO): মেমরিতে উপাদানগুলো সারি অনুসারে পরপর সংরক্ষিত হয়। প্রথমে সারি 0, তারপর সারি 1, তারপর সারি 2 সংরক্ষিত হয়। C, C++, Java এবং Python এই নিয়ম ব্যবহার করে।
2. কলাম-মেজর অর্ডার (Column-Major Order - CMO): মেমরিতে উপাদানগুলো কলাম অনুসারে পরপর সংরক্ষিত হয়। প্রথমে কলাম 0, তারপর কলাম 1 সংরক্ষিত হয়। Fortran এবং MATLAB এই নিয়ম ব্যবহার করে।

স্ট্যাক হলো একটি রৈখিক ডেটা কাঠামো যা LIFO (Last-In, First-Out) বা লাস্ট-ইন ফার্স্ট-আউট নীতি মেনে চলে। স্ট্যাকের উপাদান সংযোজন ও বিয়োজন শুধুমাত্র একটি নির্দিষ্ট প্রান্ত দিয়ে ঘটে, যাকে TOP বলা হয়। বিপরীত প্রান্তটি আবদ্ধ থাকে এবং তাকে Base বলা হয়।

MAX আকারের একটি স্ট্যাকে TOP পয়েন্টার শীর্ষ উপাদানের অবস্থান নির্দেশ করে:

• প্রাথমিক খালি অবস্থা: TOP = -1।
• PUSH অপারেশন: স্ট্যাকের শীর্ষে নতুন উপাদান প্রবেশ করানো।
  শর্ত যাচাই: যদি TOP == MAX - 1 হয়, তবে নতুন মান প্রবেশ করানো যায় না; এই অবস্থাকে স্ট্যাক ওভারফ্লো (Stack Overflow) বলা হয়। অন্যথায় TOP-কে ১ বৃদ্ধি করে মান রাখা হয়: Stack[++TOP] = val;।
• POP অপারেশন: স্ট্যাকের শীর্ষ থেকে বর্তমান উপাদান অপসারণ করা।
  শর্ত যাচাই: যদি TOP == -1 হয়, তবে স্ট্যাক থেকে কোনো উপাদান পাওয়া যায় না; একে স্ট্যাক আন্ডারফ্লো (Stack Underflow) বলা হয়। অন্যথায় মান ফেরত দিয়ে TOP-কে ১ কমানো হয়: val = Stack[TOP--];।
• PEEK অপারেশন: উপাদান মুছে না ফেলে শীর্ষ মান পরিদর্শন করা।
• isEmpty(): TOP == -1 হলে সত্য ফেরত দেয়।
• isFull(): TOP == MAX - 1 হলে সত্য ফেরত দেয়।

#include <stdio.h>
#define MAX 5

int stack[MAX];
int top = -1;

void push(int val) {
    if (top == MAX - 1) {
        printf("Stack Overflow!\n");
        return;
    }
    stack[++top] = val;
}

int pop() {
    if (top == -1) {
        printf("Stack Underflow!\n");
        return -1;
    }
    return stack[top--];
}

1. ফাংশন কল ও রানটাইম কল স্ট্যাক: যখন কোনো ফাংশন কল করা হয়, অপারেটিং সিস্টেম লোকাল ভেরিয়েবল ও রিটার্ন অ্যাড্রেস সংবলিত একটি অ্যাক্টিভেশন রেকর্ড স্ট্যাকে পুশ করে। রিকার্শনে বেস কেস না পৌঁছানো পর্যন্ত ফ্রেম পুশ হতে থাকে এবং ফেরার সময় পপ হয়।
2. এক্সপ্রেশন রূপান্তর (ইনফিক্স, প্রিফিক্স, পোস্টফিক্স): ইনফিক্স রাশিমালার বন্ধনী দূর করে কম্পিউটার মূল্যায়নের উপযোগী পোস্টফিক্স (Reverse Polish Notation) রাশিতে রূপান্তর করতে অপারেটর স্ট্যাক ব্যবহৃত হয়।
3. পোস্টফিক্স রাশিমালা মূল্যায়ন: অপারেন্ড স্ট্যাক ব্যবহার করে একক পাসে দ্রুত রাশিমালা গণনা করা হয়।
4. বন্ধনী সামঞ্জস্য যাচাই (Parentheses Balancing): কম্পাইলার কোড যাচাই করার সময় খোলার বন্ধনী ((, {, [) দেখলে স্ট্যাকে পুশ করে এবং বন্ধ করার বন্ধনী পেলে পপ করে মেলায়।
5. ব্যাকট্র্যাকিং অ্যালগরিদম: ব্রাউজারের Back বোতাম, টেক্সট এডিটরের Undo/Redo এবং মেজ ট্রাভার্সাল।

কিউ হলো একটি রৈখিক ডেটা কাঠামো যা FIFO (First-In, First-Out) বা ফার্স্ট-ইন ফার্স্ট-আউট নীতিতে কাজ করে। কিউ-এর এক প্রান্ত দিয়ে উপাদান প্রবেশ করানো হয় যাকে REAR বলা হয়, এবং অন্য প্রান্ত দিয়ে উপাদান বের করা হয় যাকে FRONT বলা হয়।

একটি সাধারণ লিনিয়ার অ্যারে কিউতে উপাদান যুক্ত করার সাথে সাথে REAR বাড়তে বাড়তে একসময় MAX - 1-এ পৌঁছায়। এরপর কিছু উপাদান DEQUEUE করে বের করে দিলেও শুরুর দিকের ইনডেক্স ($0, 1, 2, \dots$) খালি হয়ে থাকা সত্ত্বেও লিনিয়ার কিউতে আর কোনো উপাদান ENQUEUE করা যায় না কারণ REAR ইতিমধ্যে শেষ সীমায় অবস্থান করছে। একে ফলস ওভারফ্লো (False Overflow) বলা হয়।

ফলস ওভারফ্লো দূর করার জন্য অ্যারেকে একটি বৃত্তাকার রিং হিসেবে কল্পনা করা হয়, যেখানে শেষ ইনডেক্স MAX - 1-এর পরের ইনডেক্স হিসেবে 0 ব্যবহৃত হয় মডিউলো পাটিগণিতের (%) মাধ্যমে।

#define MAX 5
int cqueue[MAX];
int front = -1, rear = -1;

void enqueue(int val) {
    if ((rear + 1) % MAX == front) {
        printf("Circular Queue Overflow!\n");
        return;
    }
    if (front == -1) front = 0;
    rear = (rear + 1) % MAX;
    cqueue[rear] = val;
}

int dequeue() {
    if (front == -1) {
        printf("Circular Queue Underflow!\n");
        return -1;
    }
    int val = cqueue[front];
    if (front == rear) front = rear = -1;
    else front = (front + 1) % MAX;
    return val;
}

• ডবল এন্ডেড কিউ (Deque): FRONT ও REAR উভয় প্রান্ত দিয়েই উপাদান সন্নিবেশ ও মোচন করা সম্ভব।
• প্রায়োরিটি কিউ (Priority Queue): উপাদানগুলোর একটি অগ্রাধিকার মান থাকে। সবচেয়ে বেশি অগ্রাধিকারপ্রাপ্ত উপাদান সবার আগে নিষ্কাশিত হয়।
• বাস্তব প্রয়োগ: অপারেটিং সিস্টেমের রাউন্ড-রবিন সিপিইউ শিডিউলিং, প্রিন্টারের স্পুলিং বাফার, কিবোর্ড ইনপুট বাফার এবং গ্রাফের BFS ট্রাভার্সাল।

অ্যারেতে সরাসরি অ্যাক্সেস সুবিধা থাকলেও বাস্তব ক্ষেত্রে এর প্রধান তিনটি অসুবিধা রয়েছে:

• স্থির আকার: কম্পাইল টাইমে নির্ধারিত আকার পরে বাড়ানো বা কমানো যায় না।
• অবিচ্ছিন্ন মেমরির বাধ্যবাধকতা: মেমরিতে মোট পর্যাপ্ত খালি স্থান থাকলেও তা যদি খণ্ড খণ্ডভাবে থাকে, তবে বড় অ্যারে তৈরি করা অসম্ভব।
• ব্যয়বহুল সন্নিবেশ ও মোচন: শুরুতে বা মাঝে কোনো উপাদান যুক্ত বা মুছতে হলে বাকি উপাদানগুলোকে স্থানান্তর করতে হয়, যা অত্যন্ত ধীরগতির ($O(n)$ সময় নেয়)।

সিঙ্গলি লিঙ্কড লিস্ট হলো হিপ মেমরিতে গতিশীলভাবে তৈরি স্বাধীন নোড (Node)-এর একটি শৃঙ্খল। প্রতিটি নোডে দুটি অংশ থাকে:

1. ডেটা অংশ (Data): প্রকৃত তথ্য বা উপাত্ত ধারণ করে।
2. পয়েন্টার অংশ (Next): পরবর্তী নোডের মেমরি ঠিকানা ধারণ করে।

struct Node {
    int data;              // ডেটা মান
    struct Node *next;     // পরবর্তী নোডের পয়েন্টার
};
struct Node *head = NULL;  // তালিকার প্রথম নোডকে নির্দেশ করে

১. ট্রাভার্সাল (Traversal): head থেকে শুরু করে শেষ নোডের NULL পর্যন্ত প্রতিটি নোড পরিদর্শন করা ($O(n)$ সময়)।

২. শুরুতে নতুন নোড যুক্ত করা (Insertion at Beginning - $O(1)$):

void insertAtBeginning(struct Node **head_ref, int val) {
    struct Node *new_node = (struct Node *)malloc(sizeof(struct Node));
    new_node->data = val;
    new_node->next = *head_ref; // আগের প্রথম নোডকে লিংক করা
    *head_ref = new_node;       // head পয়েন্টার আপডেট করা
}

৩. শুরুর নোড অপসারণ (Deletion of First Node - $O(1)$):

void deleteFromBeginning(struct Node **head_ref) {
    if (*head_ref == NULL) return;
    struct Node *temp = *head_ref;
    *head_ref = (*head_ref)->next;
    free(temp); // মেমরি লিক এড়াতে মুক্ত করা হলো
}

• লিনিয়ার সার্চ (Linear Search): তালিকার প্রথম উপাদান থেকে শেষ উপাদান পর্যন্ত একের পর এক ক্রমিকভাবে টার্গেটের সাথে তুলনা করা হয়। এলোমেলো ও সাজানো উভয় অ্যারেতেই কাজ করে। টাইম কমপ্লেক্সিটি: বেস্ট $O(1)$, ওয়ার্স্ট $O(n)$।
• বাইনারি সার্চ (Binary Search): ডিভাইড অ্যান্ড কনকার নীতিতে কাজ করে। মাঝের উপাদান mid-এর সাথে তুলনা করে প্রতি ধাপে অনুসন্ধান পরিসীমা অর্ধেক করে ফেলে। শর্ত: অ্যারে অবশ্যই সাজানো (Sorted) হতে হবে। টাইম কমপ্লেক্সিটি: বেস্ট $O(1)$, ওয়ার্স্ট $O(\log_2 n)$। ১০ লক্ষ ডেটায় লিনিয়ার সার্চে ১০ লক্ষ তুলনা লাগলেও বাইনারি সার্চে মাত্র ২০টি তুলনা লাগে!

1. বাবল সর্ট (Bubble Sort): পাশাপাশি দুটি উপাদান তুলনা করে ভুল ক্রমে থাকলে সোয়াপ (Swap) করে। প্রতি পাসে সবচেয়ে বড় উপাদানটি শেষে চলে যায়। ফ্ল্যাগ ভেরিয়েবল ব্যবহার করলে সাজানো ডেটায় বেস্ট কেস $O(n)$ হয়, নতুবা $O(n^2)$।
2. সিলেকশন সর্ট (Selection Sort): প্রতি পাসে অসাজানো অংশ থেকে ক্ষুদ্রতম উপাদানটি খুঁজে বের করে সেই অংশের শুরুতে সোয়াপ করে। এতে সর্বদা সর্বনিম্ন সংখ্যক সোয়াপ (সর্বোচ্চ $N-1$ টি বা $O(n)$) ঘটে। সকল ক্ষেত্রে টাইম কমপ্লেক্সিটি $O(n^2)$।
3. ইনসার্শন সর্ট (Insertion Sort): তাসের মতো প্রতিটি নতুন উপাদানকে ইতিমধ্যে সাজানো অংশের সঠিক স্থানে ইনসার্ট করে। প্রায় সাজানো ডেটায় অত্যন্ত দ্রুত কাজ করে ($O(n)$ বেস্ট কেস)।