Class 12: Unit-2: Data Structure

A data structure is a specific way to organize and store data in a computer’s memory to enable efficient access and manipulation. 

डेटा संरचना कंप्यूटर की मेमोरी में डेटा को व्यवस्थित और संग्रहीत करने का एक विशिष्ट तरीका है

1. Arrays: One and Two Dimensional

English: Arrays are data structures used to store multiple elements of the same type in contiguous memory. They can be:

  • One Dimensional (1D): Like a list.
  • Two Dimensional (2D): Like a table or matrix.

Hindi: ऐरे डेटा स्ट्रक्चर होते हैं जो एक जैसे प्रकार के कई तत्वों को निरंतर मेमोरी में संग्रहित करते हैं। ये दो प्रकार के होते हैं:

  • एक-आयामी (1D): सूची के समान।
  • द्वि-आयामी (2D): तालिका या मैट्रिक्स के समान।

2. Memory Allocation and Address Calculation

English:

  • Arrays use sequential memory allocation.
  • Address of an element = Base Address + (Index * Size of data type)

Hindi:

  • ऐरे में मेमोरी अनुक्रमिक रूप से आवंटित होती है।
  • तत्व का पता = बेस एड्रेस + (इंडेक्स × डेटा टाइप का साइज)

3. One Dimensional Array Operations

English:

  • Traversal: Accessing each element one by one.
  • Searching:
    • Linear Search
    • Binary Search (only on sorted arrays)
  • Insertion: Adding an element at a specific position.
  • Deletion: Removing an element and shifting others.
  • Sorting Algorithms:
    • Insertion Sort
    • Selection Sort
    • Bubble Sort
  • Concatenation: Joining two arrays.
  • Merging: Combining two sorted arrays into one.

Hindi:

  • ट्रैवर्सल: प्रत्येक तत्व को एक-एक करके एक्सेस करना।
  • सर्चिंग:
    • लीनियर सर्च
    • बाइनरी सर्च (केवल सॉर्टेड ऐरे पर)
  • इंसर्शन: किसी निश्चित स्थान पर नया तत्व जोड़ना।
  • डिलीशन: किसी तत्व को हटाना और बाकी को शिफ्ट करना।
  • सॉर्टिंग एल्गोरिदम:
    • इंसर्शन सॉर्ट
    • सिलेक्शन सॉर्ट
    • बबल सॉर्ट
  • कॉनकेटनेशन: दो ऐरे को जोड़ना।
  • मर्जिंग: दो सॉर्टेड ऐरे को एक में मिलाना।

4. Two Dimensional Array Operations

English:

  • Traversal: Using nested loops to access elements.
  • Sum/Difference: Perform addition or subtraction on corresponding elements of two NxM matrices.
  • Row/Column Interchange: Swap rows and columns to transpose the matrix.

Hindi:

  • ट्रैवर्सल: नेस्टेड लूप्स का उपयोग करके तत्वों तक पहुंच।
  • योग/अंतर: दो NxM ऐरे के संबंधित तत्वों का जोड़ या घटाव।
  • पंक्ति/स्तंभ अदला-बदली: पंक्तियों और स्तंभों को बदलना (मैट्रिक्स ट्रांसपोज)।

Linked List

🔗 Linked List (English Explanation)

A Linked List is a linear data structure where each element (called a node) is connected using pointers. Each node contains:

  1. Data – the actual value.
  2. Next – a reference (or pointer) to the next node in the sequence.

📌 Types of Linked Lists:

  • Singly Linked List: Each node points to the next node.
  • Doubly Linked List: Each node points to both next and previous nodes.
  • Circular Linked List: The last node points back to the first node.

🧠 Why Use Linked Lists?

  • Dynamic size (can grow or shrink easily).
  • Easier insertion and deletion compared to arrays.

🔗 लिंक्ड लिस्ट (Linked List in Hindi)

Linked List एक linear data structure है जिसमें हर element (जिसे node कहते हैं) pointers की मदद से अगले node से जुड़ा होता है। हर node में दो चीजें होती हैं:

  1. Data – जो वैल्यू स्टोर करता है।
  2. Next – अगले node का पता (reference या pointer)।

📌 लिंक्ड लिस्ट के प्रकार:

  • Singly Linked List: हर node केवल अगले node की ओर इशारा करता है।
  • Doubly Linked List: हर node अगले और पिछले दोनों nodes की ओर इशारा करता है।
  • Circular Linked List: आख़िरी node फिर से पहले node की ओर इशारा करता है।

🧠 लिंक्ड लिस्ट क्यों इस्तेमाल करें?

  • इसका साइज dynamic होता है (आसान से बड़ा या छोटा किया जा सकता है)।
  • Array की तुलना में insertion और deletion ज़्यादा आसान होता है।

Stack (Array and Linked List Implementation) / स्टैक (ऐरे और लिंक्ड लिस्ट इम्प्लीमेंटेशन)

1. Stack Definition / स्टैक की परिभाषा

  • English: Stack is a linear data structure that follows the Last In First Out (LIFO) principle.
  • Hindi: स्टैक एक रैखिक डेटा संरचना है जो अंतिम अंदर गया तत्व पहले बाहर (LIFO) सिद्धांत का पालन करती है।

2. Stack Operations / स्टैक पर क्रियाएँ

  • PUSH: Add an element to the top of the stack.
    पुश: स्टैक के शीर्ष पर एक तत्व जोड़ना।
  • POP: Remove the top element from the stack.
    पॉप: स्टैक से शीर्ष तत्व को हटाना।

3. Stack Implementation in C++ / C++ में स्टैक का इम्प्लीमेंटेशन

a) Using Array / ऐरे का उपयोग करके:

  • Use a fixed-size array with a top variable.
  • push() adds at top + 1.
  • pop() removes from top.

b) Using Linked List / लिंक्ड लिस्ट का उपयोग करके:

  • Use nodes where each node points to the next.
  • push() adds a new node at the beginning.
  • pop() removes the head node.

4. Expression Conversion / अभिव्यक्तियों का रूपांतरण

a) Infix to Postfix / इन्फिक्स से पोस्टफिक्स:

  • Use stack to hold operators.
  • Apply precedence and associativity rules.

b) Postfix Evaluation / पोस्टफिक्स का मूल्यांकन:

  • Scan left to right.
  • Use stack to hold operands.
  • When an operator is found, pop two operands, perform the operation, and push result.