Data Structures & Algorithms
DSA Part-1
- Introduction to Data Structures
- Asymptotic Notations: Big-O, Omega, and Theta Notations
- Time Complexity and Space Complexity Analysis of Algorithms
- 1D Arrays: Memory Representation and Address Calculation
- 2D Arrays: Row-Major and Column-Major Order Formulas and Numericals
- Array Operations: Traversal, Insertion, and Deletion with Algorithms
- Sparse Matrix: Triplet Representation and Linked Representation
- String Operations, Memory Storage, and Pattern Matching Basics
- Linear Search Algorithm and Complexity Analysis
- Binary Search Algorithm (Iterative and Recursive)
- Bubble Sort Algorithm and Optimization
- Selection Sort Algorithm and Step-by-Step Trace
- Insertion Sort Algorithm and In-Place Analysis
- Merge Sort Algorithm (Divide and Conquer Approach)
- Quick Sort Algorithm and Partitioning Methods
- Counting Sort Algorithm (Non-Comparison Sorting)
- Radix Sort Algorithm and Bucket Distribution
DSA Part-2
- Singly Linked List: Concept and Memory Allocation
- Singly Linked List: Insertion Operations
- Singly Linked List: Deletion Operations
- Singly Linked List: Reversal and Search Operations
- Doubly Linked List: Node Structure and Traversal
- Doubly Linked List: Insertion and Deletion Operations
- Circular Singly Linked List: Concept and Operations
- Circular Doubly Linked List: Concept and Operations
- Header Linked List: Grounded and Circular Header Lists
- Polynomial Representation and Addition using Linked List
DSA Part-3
- Stack Data Structure: Array Implementation
- Stack Implementation using Linked List
- Infix, Prefix, and Postfix Notations
- Infix to Postfix Conversion using Stack
- Infix to Prefix Conversion using Stack
- Evaluation of Postfix Expression using Stack
- Recursion and System Stack (Tower of Hanoi)
- Linear Queue: Array Implementation and Operations
- Drawbacks of Linear Queue and Memory Wastage
- Circular Queue: Array Implementation and Condition Checks
- Queue Implementation using Linked List
- Double-Ended Queue (Deque): Input and Output-Restricted
- Priority Queue: Concept, Array and Heap Representation
DSA Part-4
- Tree Data Structure: Terminology and Basic Concepts
- Binary Trees: Types and Properties
- Binary Tree Traversals: Inorder, Preorder, and Postorder
- Level Order Traversal of Binary Tree
- Binary Search Tree (BST): Concept and Search Operation
- Binary Search Tree (BST): Insertion and Deletion Operations
- AVL Tree: Concept and Balance Factor
- AVL Tree Rotations: LL, RR, LR, and RL Rotations
- Binary Heap: Min-Heap and Max-Heap Properties
- Heap Operations: Heapify, Insertion, and Deletion
- B-Tree: Properties, Structure, and Insertion
- B+ Tree: Structure and Comparison with B-Tree
DSA Part-5
- Graph Data Structure: Terminology and Types
- Graph Representation: Adjacency Matrix and Adjacency List
- Breadth First Search (BFS) Algorithm for Graphs
- Depth First Search (DFS) Algorithm for Graphs
- Hashing: Hash Tables and Hash Functions
- Collision Resolution: Open Addressing Techniques
- Collision Resolution: Separate Chaining Method
Collision Resolution: Separate Chaining Method
Separate Chaining (Open Hashing) collision handle karne ki sabse robust aur widely used technique hai (Java ke HashMap aur C++ ke unordered_map me natively implemented). Is method me hash table ka har slot ek pointer hold karta hai jo ek Linked List ko point karta hai.
Table Slots: [0] ---> NULL [1] ---> NULL [2] ---> [ 22 | Next ] ---> [ 42 | Next ] ---> [ 92 | NULL ] [3] ---> [ 13 | NULL ] [4] ---> NULL [5] ---> [ 25 | Next ] ---> [ 75 | NULL ]
Working Principle
Jab bhi koi naya element key insert hota hai, toh hash function index = h(key) calculate karta hai. Fir us index par bani linked list ke starting ya end me naya node attach kar diya jata hai. Agar multiple keys same index par hash hoti hain, toh wo seamlessly linked list me chain hoti chali jaati hain.
Load Factor (α) and Complexity Analysis
Hash table performance Load Factor (α) par depend karti hai:
Load Factor (α) = n / m (n = Total Keys, m = Number of Slots)
- Average Case Time Complexity:
O(1 + α)– Agar hash function uniformly distribute kare aurα <= 0.75rahe, toh search, insert aur delete O(1) constant time me execute hote hain. - Worst Case Time Complexity:
O(n)– Agar saari keys bad hash function ki wajah se single slot par chain ho jayein (pure linked list ban jaye).
Separate Chaining vs Open Addressing Comparison
| Feature | Separate Chaining | Open Addressing |
|---|---|---|
| Storage Location | Linked lists outside table | Directly inside table slots |
| Table Size Limit | Never full (α can be > 1) | Cannot exceed table capacity (α < 1) |
| Deletion Ease | Simple standard linked list node deletion | Complex (requires tombstone/deleted markers) |
| Cache Performance | Poor cache locality (nodes scattered in heap) | Excellent cache performance (contiguous array) |
Is topic ke saath Data Structures & Algorithms (DSA) ka complete syllabus finish hota hai! Agle subject me hum start karenge Design & Analysis of Algorithms (DAA).