Data Structures and Algorithms: Basic Notes
1. Searching Techniques
Linear Search
- Iterates through each element in the list sequentially.
- Example: Searching for 5 in [1, 2, 3, 4, 5, 6].
Binary Search
- Works on sorted arrays by repeatedly dividing the search interval in half.
- Example: Searching for 15 in [5, 10, 15, 20, 25].
2. Sorting Techniques
Bubble Sort
- Swaps adjacent elements if they are in the wrong order.
- Example: Sorting [5, 2, 4, 3] into [2, 3, 4, 5].
Insertion Sort
- Builds the sorted list one element at a time.
- Example: Insert 3 into [1, 2, 4] to get [1, 2, 3, 4].
Selection Sort
- Finds the smallest element in the unsorted part and places it in the correct position.
- Example: Select the smallest from [4, 3, 1, 2] to [1, 4, 3, 2].
Shell Sort
- Sorts elements at a certain gap before reducing the gap.
- Example: Sorting [10, 8, 6, 4, 2] with gap 2 first.
Quick Sort
- Divides the list using a pivot and sorts recursively.
- Example: Pivot: 10 in [10, 5, 20, 15] - Left: [5], Right: [20, 15].
Merge Sort
- Divides the array into halves, sorts them, and merges back.
- Example: Split [8, 4, 7, 3] into [8, 4] and [7, 3], then merge sorted halves.
Radix Sort
- Sorts based on individual digits, starting from the least significant.
- Example: Sorting [170, 45, 75, 90] by units, then by tens.
3. Hashing Techniques
Modulo Division
- Use key mod table size.
- Example: Key: 42, Table size: 10 -> 42 % 10 = 2.
Digit Extraction
- Extract specific digits of the key.
- Example: Key: 4256, Extract 2nd and 4th digits -> 25.
Fold Shift
- Divide the key into parts, sum them, and take modulo.
- Example: Key: 123456, Fold into [123, 456], Sum = 579.
Linear Probe (Collision Resolution)
- Resolve collisions by sequentially checking the next slot.
- Example: Key 12 hashes to slot 2; slot 2 is full -> Try slot 3.
4. Linear Data Structures
Stacks
- LIFO (Last In, First Out).
- Basic Operations:
- Push: Add an element.
- Pop: Remove the top element.
- Peek: View the top element.
- Applications:
- Balancing parenthesis: [( { )}] -> Valid.
- Converting infix to postfix: A+B -> AB+.
Queues
- FIFO (First In, First Out).
- Types:
- Linear Queue: Straightforward queue.
- Circular Queue: Connects end to start for better space utilization.
Priority Queue
- Elements are dequeued based on priority.
- Example: Tasks with priorities [3, 1, 2] -> Serve 1 first.
Deque (Double-Ended Queue)
- Insert and delete elements from both ends.
- Example: Add 10 at the front, add 20 at the rear.
5. Linked Lists
Singly Linked List (SLL)
- A list where each node points to the next node.
- Operations: Insert, Display, Delete, Search.
- Example: 10 -> 20 -> 30 -> None.
Circular Linked List (CLL)
- The last node points back to the first node.
- Example: 10 -> 20 -> 30 -> 10 (circular).
Doubly Linked List (DLL)
- Each node has a pointer to the previous and next node.
- Example: None <- 10 <-> 20 <-> 30 -> None.
6. Non-Linear Data Structures
Tree
- Hierarchical structure with parent-child relationships.
- Example:
- Binary Tree: Each node has at most 2 children.
- Binary Search Tree (BST): Left < Root < Right.
Heap
- Complete binary tree, either Min-Heap (smallest at root) or Max-Heap (largest at root).
- Example: Min-Heap: [2, 5, 10, 20].
Graph
- Represented as nodes and edges.
- Types:
- Directed: Edges have direction.
- Undirected: Edges have no direction.
- Representation:
- Adjacency Matrix.
- Adjacency List.
- Traversals:
- BFS (Breadth-First Search).
- DFS (Depth-First Search).