DSA with Python - Clean Notes
1. Time & Space Complexity
Big-O notation measures efficiency.
Common complexities: O(1), O(log n), O(n), O(n log n), O(n^2).
Always optimize for worst-case scenarios.
2. Arrays
Arrays store elements in contiguous memory.
Operations: Access O(1), Search O(n), Insert/Delete O(n).
Python uses lists as dynamic arrays.
3. Linked List
A linked list consists of nodes (data + pointer).
Types: Singly, Doubly, Circular.
Pros: Dynamic size. Cons: Slow access O(n).
4. Stack (LIFO)
Stack follows Last In First Out.
Operations: push, pop, peek.
Used in recursion, undo operations.
5. Queue (FIFO)
Queue follows First In First Out.
Operations: enqueue, dequeue.
Variants: Circular Queue, Deque, Priority Queue.
6. Recursion
Function calling itself.
Must have base case to avoid infinite loop.
Used in tree/graph traversal.
7. Searching Algorithms
Linear Search O(n).
Binary Search O(log n) requires sorted array.
8. Sorting Algorithms
Bubble Sort O(n^2), Selection Sort O(n^2), Insertion Sort O(n^2).
Merge Sort O(n log n), Quick Sort O(n log n).
9. Trees
Hierarchical structure with root and children.
Binary Tree, BST, Heap.
Used in databases and file systems.
10. Graphs
Nodes connected by edges.
Represented using adjacency list/matrix.
Traversal: BFS, DFS.
11. Hashing
Key-value mapping using hash function.
Python dict uses hashing.
Average operations: O(1).