डेटा संरचना

डेटा संरचना (Data Structure) कंप्यूटर मेमोरी में डेटा को व्यवस्थित, संसाधित, पुनः प्राप्त और संग्रहीत करने का एक विशेष प्रारूप है ताकि विभिन्न संक्रियाएं न्यूनतम समय में कुशलतापूर्वक निष्पादित की जा सकें। केवल एल्गोरिदम लिखना पर्याप्त नहीं है; एल्गोरिदम की वास्तविक गति डेटा संरचना की उपयुक्तता पर निर्भर करती है।

उपयुक्त डेटा संरचना के चयन हेतु तीन मुख्य कारक हैं: (1) डेटा की मात्रा एवं उनका आपसी संबंध, (2) बुनियादी ऑपरेशनों की आवृत्ति (जैसे खोजना, जोड़ना, हटाना), और (3) हार्डवेयर संसाधन (सीपीयू समय एवं मुख्य मेमोरी की खपत)।

डेटा संरचनाओं को मुख्य रूप से दो श्रेणियों में बांटा गया है:

• प्रिमिटिव डेटा संरचनाएं: वे बुनियादी डेटा प्रकार जो सीधे कंप्यूटर हार्डवेयर और मशीन निर्देशों द्वारा समर्थित होते हैं। C भाषा में int, float, char, double और पॉइंटर्स इसके उदाहरण हैं। ये किसी भी समय केवल एक परमाणु (atomic) मान रखते हैं।
• नॉन-प्रिमिटिव डेटा संरचनाएं: समरूप या विषम डेटा तत्वों के समूह को व्यवस्थित करने के लिए प्रिमिटिव प्रकारों से निर्मित जटिल संरचनाएं। इन्हें पुनः दो वर्गों में विभाजित किया गया है:

सभी डेटा संरचनाओं पर निम्नलिखित छह बुनियादी संक्रियाएं की जाती हैं:

1. ट्रैवर्सिंग (Traversing): संरचना के प्रत्येक तत्व को कम से कम एक बार एक्सेस और प्रोसेस करना (जैसे सभी तत्वों को प्रिंट करना)।
2. इंसर्शन (Insertion): संरचना में किसी निश्चित स्थान पर नया डेटा तत्व जोड़ना।
3. डिलिशन (Deletion): संरचना से किसी मौजूदा तत्व को हटाना।
4. सर्चिंग (Searching): दी गई 'की' (Key) के आधार पर किसी तत्व का स्थान खोजना (लीनियर व बाइनरी सर्च)।
5. सॉर्टिंग (Sorting): तत्वों को किसी निश्चित क्रम (आरोही या अवरोही) में व्यवस्थित करना।
6. मर्जिंग (Merging): दो अलग-अलग सॉर्ट की गई सूचियों को मिलाकर एक संयुक्त सूची बनाना।

1D ऐरे समान डेटा प्रकार के तत्वों का एक निश्चित आकार का सतत (contiguous) मेमोरी ब्लॉक होता है। C भाषा में ऐरे इंडेक्सिंग सदैव 0 से प्रारंभ होती है, अतः $N$ आकार के ऐरे के इंडेक्स $0, 1, 2, \dots, N-1$ होते हैं।

चूंकि सभी तत्व मेमोरी में एक के बाद एक रखे जाते हैं, इसलिए किसी भी तत्व $A[i]$ का भौतिक मेमोरी पता बिना बीच के तत्वों को गिने सीधे गणितीय सूत्र द्वारा $O(1)$ समय में ज्ञात किया जा सकता है।

यदि ऐरे का बेस एड्रेस $B$ (प्रथम तत्व $A[\text{LB}]$ का पता), निम्न सीमा $\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$$

अल्गोरिदम 1: स्थिति $k$ पर तत्व जोड़ना (Insertion at $k$)

$N$ तत्वों वाले ऐरे में इंडेक्स $k$ पर नया मान जोड़ने के लिए इंडेक्स $N-1$ से $k$ तक के सभी तत्वों को एक स्थान दाईं ओर शिफ्ट करना पड़ता है:

for (int i = N - 1; i >= k; i--) {
    A[i + 1] = A[i]; // दाईं ओर खिसकाना
}
A[k] = new_value;
N++; // कुल संख्या में वृद्धि

टाइम कॉम्प्लेक्सिटी: बेस्ट केस $O(1)$ (अंत में जोड़ने पर), वर्स्ट केस $O(n)$ (प्रारंभ में जोड़ने पर सभी को खिसकाना पड़ता है)।

अल्गोरिदम 2: स्थिति $k$ से तत्व हटाना (Deletion at $k$)

इंडेक्स $k$ से तत्व हटाने के लिए $k+1$ से $N-1$ तक के तत्वों को एक स्थान बाईं ओर शिफ्ट किया जाता है:

for (int i = k; i < N - 1; i++) {
    A[i] = A[i + 1]; // बाईं ओर खिसकाना
}
N--; // कुल संख्या में कमी

2D ऐरे $M$ पंक्तियों (Rows) एवं $N$ कॉलमों का आयताकार ग्रिड होता है, जिसे C में int A[M][N] लिखा जाता है। चूंकि कंप्यूटर मेमोरी (RAM) एक-विमीय होती है, कंपाइलर को 2D ग्रिड को दो प्रमुख विधियों में से किसी एक द्वारा रैखिक मेमोरी में बदलना पड़ता है:

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 को 1 बढ़ाकर मान रखा जाता है: Stack[++TOP] = val;।
• POP संक्रिया: स्टैक के शीर्ष से तत्व को हटाना और प्राप्त करना।
  सीमा जांच: यदि TOP == -1 है, तो कोई तत्व नहीं हटाया जा सकता; इसे स्टैक अंडरफ्लो (Stack Underflow) कहते हैं। अन्यथा मान लौटाकर TOP को 1 घटाया जाता है: 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 तथा भूलभुलैया (Maze) हल करना।

क्यू एक रैखिक डेटा संरचना है जो FIFO (First-In, First-Out) अर्थात प्रथम-आगमन प्रथम-निर्गमन नियम पर कार्य करती है। क्यू में एक सिरे से तत्व जोड़े जाते हैं जिसे REAR कहते हैं, तथा दूसरे सिरे से तत्व निकाले जाते हैं जिसे FRONT कहते हैं।

साधारण ऐरे आधारित लीनियर क्यू में तत्व जोड़ने पर REAR बढ़ते-बढ़ते MAX - 1 तक पहुंच जाता है। इसके पश्चात यदि हम कुछ तत्वों को DEQUEUE करके निकाल भी दें, तो आगे के इंडेक्स ($0, 1, 2, \dots$) खाली होने के बावजूद नया तत्व नहीं जोड़ा जा सकता क्योंकि 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 ट्रैवर्सल।

ऐरे में त्वरित एक्सेस होने पर भी व्यावहारिक अनुप्रयोगों में इसकी मुख्य तीन कमियां हैं:

• निश्चित आकार: कंपाइल समय पर तय किया गया आकार रनटाइम पर घटाया या बढ़ाया नहीं जा सकता।
• सतत मेमोरी की बाध्यता: यदि मेमोरी में पर्याप्त खाली स्थान बिखरा हुआ (Fragmented) है, तब भी बड़ा ऐरे आवंटित नहीं हो सकता।
• महंगा इंसर्शन और डिलिशन: बीच में या प्रारंभ में तत्व जोड़ने/हटाने हेतु शेष सभी तत्वों को खिसकाना पड़ता है, जिसमें $O(n)$ समय व्यर्थ होता है।

सिंगली लिंक्ड लिस्ट हीप मेमोरी में स्वतंत्र रूप से बने नोड्स (Nodes) की एक गतिशील श्रृंखला होती है। प्रत्येक नोड में दो भाग होते हैं:

1. डेटा भाग (Data): वास्तविक सूचना या मान संग्रहीत करता है।
2. पॉइंटर भाग (Next): श्रृंखला के अगले नोड का मेमोरी पता रखता है।

struct Node {
    int data;              // डेटा मान
    struct Node *next;     // अगले नोड का पॉइंटर
};
struct Node *head = NULL;  // प्रथम नोड को इंगित करता है

1. ट्रैवर्सल (Traversal): head से प्रारंभ कर अंतिम नोड के NULL तक सभी नोड्स को क्रम से देखना ($O(n)$ समय)।

2. प्रारंभ में नया नोड जोड़ना (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;       // हेड को नए नोड पर सेट करना
}

3. प्रथम नोड हटाना (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)$। 10 लाख तत्वों में लीनियर सर्च में 10 लाख तुलनाएं लग सकती हैं, जबकि बाइनरी सर्च में अधिकतम केवल 20 तुलनाएं लगती हैं!

1. बबल सॉर्ट (Bubble Sort): पास-पास के दो तत्वों की तुलना कर गलत क्रम में होने पर उन्हें आपस में बदलता (Swap) है। प्रत्येक पास में सबसे बड़ा तत्व अंत में पहुंच जाता है। फ्लैग वेरिएबल के साथ सॉर्टेड डेटा पर बेस्ट केस $O(n)$ समय देता है, वर्स्ट केस $O(n^2)$।
2. सिलेक्शन सॉर्ट (Selection Sort): प्रत्येक पास में अव्यवस्थित भाग में से न्यूनतम तत्व ढूंढकर उसे उस भाग के पहले स्थान से बदलता है। इसमें न्यूनतम स्वैप (अधिकतम $N-1$ या $O(n)$ स्वैप) होते हैं। सभी स्थितियों में समय $O(n^2)$ रहता है।
3. इंसर्शन सॉर्ट (Insertion Sort): ताश के पत्तों की भांति नए तत्व को पहले से सॉर्ट किए गए भाग में सही स्थान पर प्रविष्ट करता है। लगभग सॉर्ट किए गए डेटा पर अत्यंत तेज ($O(n)$) कार्य करता है।