DSA Basics PDF

Detailed Notes: Data Structures and Algorithms 1. Basic Terminologies 1. Data: It represents values, facts, or observations stored in memory. 2. Data Structure: A format for organizing, managing, and storing data efficiently (e.g., arrays, linked lists). 3. Algorithms: Step-by-step instructions...

Detailed Notes: Data Structures and Algorithms 1. Basic Terminologies 1. Data: It represents values, facts, or observations stored in memory. 2. Data Structure: A format for organizing, managing, and storing data efficiently (e.g., arrays, linked lists). 3. Algorithms: Step-by-step instructions for solving problems. 4. Complexity: Measure of the performance of an algorithm in terms of time (Time Complexity) and space (Space Complexity). 5. Operations: Common operations include insertion, deletion, traversal, searching, and sorting. 2. Elementary Data Organizations Data can be organized in several ways: - Arrays: A collection of similar data types stored sequentially. - Linked Lists: A collection of nodes where each node points to the next. - Stacks: Linear structures following LIFO (Last In, First Out). - Queues: Linear structures following FIFO (First In, First Out). - Trees: Hierarchical structures with parent-child relations. - Graphs: A collection of nodes (vertices) connected by edges. 3. Data Structure Operations Data structures support various operations: - Insertion: Adding an element to a structure. - Deletion: Removing an element. - Traversal: Visiting each element (e.g., Depth-First Search in trees). - Searching: Finding an element (e.g., Linear or Binary Search). - Sorting: Arranging elements in order (ascending/descending). 4. Linear Search and Binary Search 1. Linear Search: - A simple search algorithm that checks each element sequentially. - Complexity: O(n) where n is the number of elements. 2. Binary Search: - Works on sorted arrays by dividing the array into halves. - Steps: Compare the middle element, decide to search in the left or right half. - Complexity: O(log n). Example of Binary Search in C: ```c int binarySearch(int arr[], int low, int high, int key) { while (low key) high = mid - 1; else low = mid + 1; } return -1; } ``` 5. Stacks and Queues 1. **Stack**: - LIFO structure (Last In, First Out). - Operations: Push (insert), Pop (remove). - Applications: Function calls, Undo operations. 2. **Queue**: - FIFO structure (First In, First Out). - Types: Simple, Circular, Priority Queues. - Applications: Scheduling tasks, managing requests. 6. Linked Lists Linked lists store data in nodes with pointers connecting them: 1. Singly Linked List: Each node points to the next node. 2. Doubly Linked List: Nodes have pointers to both the previous and next nodes. 3. Circular Linked List: The last node points back to the first node. Advantages: - Dynamic size, efficient insertion/deletion. Disadvantages: - Slower search compared to arrays. 7. Trees Trees are hierarchical data structures with a root node: - Binary Tree: Each node has at most two children. - Binary Search Tree (BST): Left child < Parent < Right child. - B+ Tree: Balanced tree used in databases. Operations: - Insertion, Deletion, Traversal (Inorder, Preorder, Postorder). 8. Sorting Algorithms 1. **Selection Sort**: Repeatedly selects the smallest element and places it in order. O(n^2). 2. **Bubble Sort**: Swaps adjacent elements until sorted. O(n^2). 3. **Insertion Sort**: Inserts each element into its correct position. O(n^2). 4. **Quick Sort**: Divides array around a pivot. O(n log n). 5. **Merge Sort**: Divides the array and merges sorted halves. O(n log n). 6. **Heap Sort**: Builds a heap and extracts the max/min. O(n log n). 9. Hashing Hashing is a technique for efficient data storage and retrieval: - Hash Function: Maps a key to an index. - Hash Table: Stores values at hash indices. - Collision Handling: Chaining (linked lists), Open Addressing. Applications: - Data indexing, caches, symbol tables. 10. Graph Representations and Traversal Graphs are collections of vertices (nodes) and edges: - Representations: Adjacency Matrix, Adjacency List. 1. Breadth-First Search (BFS): Visits level by level. 2. Depth-First Search (DFS): Explores as deep as possible before backtracking. Applications: - Shortest Path Algorithms, Network Routing.