Data Structures & Algorithms

# Data Structures & Algorithms (DSA) Master Revision Cheatsheet > **Target Exam**: Competitive Programming & CS Entrance Exams (GATE, RPSC Computer Inspector, Technical Officer) > **Subject**: Data Structures & Algorithms > **Topic Page**: [https://upscorer.in/topics/data-structures-algorithms](https://upscorer.in/topics/data-structures-algorithms) --- ## 🌟 Key Concepts & Core Rules ⭐⭐⭐⭐⭐ ### 1. Asymptotic Notations & Complexity Analysis - **Big-O ($O$)**: Upper bound of execution time (Worst-case performance guarantee). - **Big-Omega ($\Omega$)**: Lower bound of execution time (Best-case performance guarantee). - **Big-Theta ($\Theta$)**: Tight bound (Average & exact growth rate when upper and lower bounds match). - **Growth Rate Hierarchy**: $$\mathcal{O}(1) < \mathcal{O}(\log n) < \mathcal{O}(n) < \mathcal{O}(n \log n) < \mathcal{O}(n^2) < \mathcal{O}(n^3) < \mathcal{O}(2^n) < \mathcal{O}(n!)$$ --- ### 2. Linear Data Structures #### A. Arrays - **Memory Layout**: Contiguous memory allocation. - **Access Time**: $\mathcal{O}(1)$ via index arithmetic: $\text{Address}(A[i]) = \text{Base} + i \times \text{Size}$. - **Insertion/Deletion**: $\mathcal{O}(n)$ worst-case due to element shifting. #### B. Linked Lists - **Structure**: Nodes containing Data + Pointer to next node. - **Access Time**: $\mathcal{O}(n)$ sequential traversal. - **Insertion/Deletion**: $\mathcal{O}(1)$ at known pointer location (no shifting required). - **Variants**: Singly Linked List, Doubly Linked List ($\mathcal{O}(1)$ backward traversal), Circular Linked List (last node points to head). #### C. Stacks - **Principle**: Last-In, First-Out (LIFO). - **Primary Operations**: `push(x)` $\mathcal{O}(1)$, `pop()` $\mathcal{O}(1)$, `peek()` $\mathcal{O}(1)$. - **Key Applications**: Function call stack, Infix to Postfix/Prefix evaluation, Balancing Parentheses, Backtracking. #### D. Queues - **Principle**: First-In, First-Out (FIFO). - **Primary Operations**: `enqueue(x)` $\mathcal{O}(1)$, `dequeue()` $\mathcal{O}(1)$. - **Circular Queue**: Solves space wastage of array queue using modulo arithmetic: $\text{rear} = (\text{rear} + 1) \pmod N$. - **Applications**: CPU Scheduling (Round Robin), BFS Graph Traversal, Buffer management. --- ### 3. Non-Linear Data Structures #### A. Trees & Binary Search Trees (BST) - **Binary Tree**: Each node has at most 2 children. - **Tree Traversals**: - **Inorder** (Left, Root, Right): Returns sorted sequence for BST! - **Preorder** (Root, Left, Right): Used for expression trees and tree duplication. - **Postorder** (Left, Right, Root): Used for tree deletion and Postfix generation. - **Level-Order**: Breadth-First search using Queue. - **BST Property**: $\text{Left Child} < \text{Root} \le \text{Right Child}$. - Search, Insert, Delete Time Complexity: $\mathcal{O}(h)$ where $h$ is tree height ($\mathcal{O}(\log n)$ balanced, $\mathcal{O}(n)$ skewed). #### B. Binary Heaps - **Complete Binary Tree** stored in array ($i$'s left child = $2i+1$, right child = $2i+2$, parent = $\lfloor(i-1)/2\rfloor$). - **Min-Heap**: Parent $\le$ Children. Max-Heap: Parent $\ge$ Children. - **Heap Operations**: Insert $\mathcal{O}(\log n)$, Extract Min/Max $\mathcal{O}(\log n)$, Heapify array $\mathcal{O}(n)$. #### C. Graphs - **Representations**: Adjacency Matrix ($\mathcal{O}(V^2)$ space) vs Adjacency List ($\mathcal{O}(V + E)$ space). - **Graph Traversals**: - **BFS**: Level-by-level using Queue. Time: $\mathcal{O}(V + E)$. Finds shortest path in unweighted graphs. - **DFS**: Deep exploration using Stack / Recursion. Time: $\mathcal{O}(V + E)$. Used for Topological Sorting and Cycle Detection. --- ### 4. Sorting & Searching Algorithms Summary Table | Algorithm | Best Time | Avg Time | Worst Time | Space | Stable? | | :--- | :---: | :---: | :---: | :---: | :---: | | **Linear Search** | $\mathcal{O}(1)$ | $\mathcal{O}(n)$ | $\mathcal{O}(n)$ | $\mathcal{O}(1)$ | Yes | | **Binary Search** | $\mathcal{O}(1)$ | $\mathcal{O}(\log n)$ | $\mathcal{O}(\log n)$ | $\mathcal{O}(1)$ | Yes | | **Bubble Sort** | $\mathcal{O}(n)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(1)$ | Yes | | **Selection Sort** | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(1)$ | No | | **Insertion Sort** | $\mathcal{O}(n)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(1)$ | Yes | | **Merge Sort** | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n)$ | Yes | | **Quick Sort** | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n^2)$ | $\mathcal{O}(\log n)$ | No | | **Heap Sort** | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n \log n)$ | $\mathcal{O}(n \log n)$ | $\mathcal{O}(1)$ | No | --- ## 🚨 Common Exam Pitfalls & Misconceptions 1. **Array Indexing vs Element Shift**: Direct index access in array is $\mathcal{O}(1)$, but insertion/deletion requires shifting $\mathcal{O}(n)$ elements. 2. **Inorder Traversal of BST**: Inorder traversal of any Binary Search Tree ALWAYS yields elements in strictly sorted ascending order. 3. **Queue Space Wastage**: Linear array queue runs out of space when `rear = N-1` even if front elements are dequeued. Use Circular Queue with modulo arithmetic $(\text{rear} + 1) \pmod N$. 4. **Binary Search Requirement**: Binary Search CANNOT be performed on an unsorted array or a standard Singly Linked List in $\mathcal{O}(\log n)$ time due to lack of random access. 5. **Quick Sort Worst Case**: Quick sort degenerates to $\mathcal{O}(n^2)$ time complexity when the pivot is chosen poorly on an already sorted array. 6. **Heap Build Time**: Building a heap from an unsorted array of size $n$ takes $\mathcal{O}(n)$ time using Floyd's algorithm, NOT $\mathcal{O}(n \log n)$. 7. **Stack Overflow vs Underflow**: Stack Overflow occurs when `push()` is called on a full stack (`top == MAX-1`). Stack Underflow occurs when `pop()` is called on an empty stack (`top == -1`). 8. **BFS Data Structure**: BFS requires a **Queue**, whereas DFS requires a **Stack** (or recursive call stack). 9. **Stability in Sorting**: A sorting algorithm is stable if two elements with equal keys appear in the same relative order in output as in input (e.g. Merge Sort is stable, Quick Sort & Heap Sort are unstable). 10. **Recursion Space**: Recursive algorithms require $\mathcal{O}(h)$ auxiliary call stack space where $h$ is maximum recursion depth. --- ## 🇮🇳 हिंदी मास्टर सारांश (Hindi Revision Summary) # डेटा स्ट्रक्चर्स एवं एल्गोरिदम (Data Structures & Algorithms) - **ऐरे (Array)**: लगातार (Contiguous) मेमोरी लोकेशन पर डेटा स्टोर करता है। इंडेक्स द्वारा एक्सेस टाइम $\mathcal{O}(1)$ होता है। - **लिंक्ड लिस्ट (Linked List)**: नोड्स में डेटा और अगले नोड का पॉइंटर होता है। एलिमेंट्स को खिसकाए बिना $\mathcal{O}(1)$ में इंसर्ट/डिलीट संभव है। - **स्टैक (Stack)**: LIFO (Last-In, First-Out) सिद्धांत पर कार्य करता है। मुख्य ऑपरेशन्स: Push, Pop, Peek ($\mathcal{O}(1)$)। - **क्यू (Queue)**: FIFO (First-In, First-Out) सिद्धांत पर कार्य करता है। सर्कुलर क्यू (Circular Queue) मेमोरी की बर्बादी रोकता है: $(\text{rear}+1) \pmod N$। - **बाइनरी सर्च ट्री (BST)**: बायां बच्चा < रूट $\le$ दायां बच्चा। इनऑर्डर (Inorder) ट्रैवर्सल हमेशा सॉर्टेड (Sorted) क्रम देता है। - **बाइनरी सर्च (Binary Search)**: केवल सॉर्टेड ऐरे पर कार्य करता है। समय जटिलता (Time Complexity) $\mathcal{O}(\log n)$ है। - **सॉर्टिंग जटिलता**: - Merge Sort: $\mathcal{O}(n \log n)$ (सर्वदा स्थाई/Stable)। - Quick Sort: औसतन $\mathcal{O}(n \log n)$, वर्स्ट केस $\mathcal{O}(n^2)$ (अस्थाई/Unstable)। - Heap Sort: $\mathcal{O}(n \log n)$ (इन-प्लेस/In-Place, $\mathcal{O}(1)$ अतिरिक्त स्पेस)।