Basic Notes on Data Structures and Algorithms
Searching Techniques
1. Linear Search:
- Iterates through each element in the list sequentially.
- Best case: O(1), Worst case: O(n).
- Suitable for unsorted or small datasets.
2. Binary Search:
- Works on sorted arrays by repeatedly dividing the search interval in half.
- Time complexity: O(log n).
- Example: Searching for a key in a phonebook.
Sorting Techniques
1. Bubble Sort:
- Repeatedly swaps adjacent elements if they are in the wrong order.
- Time complexity: O(n^2).
2. Insertion Sort:
- Builds the sorted array one element at a time.
- Time complexity: O(n^2), Best case: O(n) (nearly sorted data).
3. Selection Sort:
Basic Notes on Data Structures and Algorithms
- Finds the smallest element in the unsorted part and places it in the correct position.
- Time complexity: O(n^2).
4. Shell Sort:
- Improves insertion sort by comparing elements separated by a gap.
- Time complexity: Depends on the gap sequence; average case: O(n log n).
5. Quick Sort:
- Divides the array using a pivot element and sorts recursively.
- Time complexity: O(n log n), Worst case: O(n^2).
6. Merge Sort:
- Divides the array into halves, sorts them, and merges back.
- Time complexity: O(n log n).
7. Radix Sort (Self-Learning):
- Non-comparative sorting; processes digits from least significant to most significant.
- Time complexity: O(d(n + k)), where d is the number of digits, k is the range.
Hashing Techniques
1. Modulo Division:
- Key mod table size.
- Example: key mod 7.
Basic Notes on Data Structures and Algorithms
2. Digit Extraction:
- Extracts specific digits of the key for hash computation.
3. Fold Shift:
- Divides the key into parts, sums them, and takes modulo.
4. Fold Boundary:
- Similar to fold shift but reverses alternate segments before summing.
5. Linear Probe (Collision Resolution):
- Resolves collisions by checking the next slot sequentially.
Self-Learning Topics:
- Direct Hashing: Direct mapping of key to hash.
- Subtraction Hashing: Uses subtraction operations for key transformation.
- Quadratic Probe: Checks slots at intervals based on square increments.
Linear Data Structures
1. Stack:
- LIFO (Last In First Out).
- Applications: Infix to Postfix, Postfix evaluation, Parenthesis balancing.
Basic Notes on Data Structures and Algorithms
2. Queue:
- FIFO (First In First Out).
- Linear Queue: Insert at the rear, delete from the front.
- Circular Queue: Reuses space by connecting the rear to the front.
Self-Learning Topics:
- Priority Queue: Each element has a priority; higher priority elements are dequeued first.
- Dequeue: Allows insertion and deletion from both ends.
Linked Lists
1. Singly Linked List (SLL):
- Linear nodes with next pointers.
- Operations: Insert, Delete, Search, Count.
2. Circular Linked List:
- Last node points back to the head.
3. Doubly Linked List:
- Nodes have next and previous pointers.
- Operations: Insert, Delete, Display.
Self-Learning Topics:
- Reverse an SLL.
Basic Notes on Data Structures and Algorithms
- Merge two sorted linked lists.
Non-Linear Data Structures
1. Tree:
- Binary Search Tree (BST): Left subtree < node, Right subtree > node.
- Traversals: Preorder, Postorder, Inorder.
- Operations: Insert, Search, Find smallest/largest node, Count nodes.
2. Heap:
- Min Heap: Root is smallest.
- Max Heap: Root is largest.
- Operations: reheapUp, reheapDown, Delete.
3. Graph:
- Representation: Adjacency Matrix/List.
- Traversals: BFS (Breadth-First Search), DFS (Depth-First Search).
- Minimum Spanning Tree (Prims): Finds the subset of edges with minimum weight connecting all
vertices.