Data Structure Cheat Sheet: Complete Guide
Welcome to the ultimate DSA cheat sheet! This page consolidates all the key information from our Data Structures and Algorithms tutorial series into a single, scannable reference. Use this to review concepts, memorize complexities, and ace your technical interviews.
Pro Tip: Bookmark this page for quick revision before interviews. Understanding when to use a specific data structure is just as important as knowing how it works.
1. Data Structures & Big O Complexity
Legend: * denotes O(1) time with known position (e.g., at head or tail).
| Data Structure | Access | Search | Insertion | Deletion | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Stack | O(1) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(1) | O(n) | O(1) | O(1) | O(n) |
| Singly Linked List | O(n) | O(n) | O(1)* | O(1)* | O(n) |
| Doubly Linked List | O(n) | O(n) | O(1)* | O(1)* | O(n) |
| Hash Table | O(1) avg | O(1) avg | O(1) avg | O(1) avg | O(n) |
| BST | O(log n) avg | O(log n) avg | O(log n) avg | O(log n) avg | O(n) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Heap (Min/Max) | O(1) | O(n) | O(log n) | O(log n) | O(n) |
| B-Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
2. Sorting Algorithms Summary
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes |
| Bucket Sort | O(n+k) | O(n+k) | O(n²) | O(n) | Yes |
3. Graph Algorithms Cheat Sheet
| Algorithm | Use Case | Time Complexity | Space Complexity |
|---|---|---|---|
| BFS | Shortest path (unweighted), level traversal | O(V + E) | O(V) |
| DFS | Cycle detection, topological sort, path finding | O(V + E) | O(V) |
| Dijkstra's | Shortest path (positive weights) | O((V+E) log V) | O(V) |
| Bellman-Ford | Shortest path (negative weights, cycle detection) | O(VE) | O(V) |
| Floyd-Warshall | All-pairs shortest path | O(V³) | O(V²) |
| Kruskal's | Minimum Spanning Tree (MST) | O(E log E) | O(V) |
| Prim's | Minimum Spanning Tree (MST) | O((V+E) log V) | O(V) |
| Topological Sort | Ordering vertices in a DAG | O(V + E) | O(V) |
4. Algorithm Paradigms — Quick Guide
- Brute Force: Exhaustive search. Simple but often exponential (O(2ⁿ) or O(n!)). E.g., Subset sum, TSP.
- Divide & Conquer: Split problem into subproblems, solve recursively, merge. E.g., Merge Sort, Quick Sort, Binary Search.
- Greedy: Make locally optimal choices at each step. Fast, but may not yield global optimum. E.g., Activity Selection, Fractional Knapsack.
- Dynamic Programming: Break into overlapping subproblems and store results (memoization/tabulation). Guarantees optimal solution. E.g., 0/1 Knapsack, LCS, Fibonacci.
- Backtracking: Explore all solutions, abandon (backtrack) when constraint fails. E.g., N-Queens, Sudoku solver.
5. Key Data Structure Definitions
- Array: Contiguous memory allocation, fixed size (static) or dynamic. Provides O(1) random access.
- Linked List: Dynamic size, non-contiguous memory (nodes). Efficient O(1) insert/delete at known positions.
- Stack: LIFO (Last-In-First-Out). Implemented via arrays/linked lists. Used in DFS, recursion, undo/redo.
- Queue: FIFO (First-In-First-Out). Used in BFS, scheduling, buffering.
- Binary Search Tree (BST): Left child < Parent < Right child. Average O(log n) search, insert, delete.
- AVL Tree: Self-balancing BST. Balance factor = {-1, 0, 1}. Guarantees O(log n) operations.
- Heap: Complete binary tree. Max-heap: Parent ≥ Children. Min-heap: Parent ≤ Children. Used for Priority Queues.
- Hash Table: Key-Value store using hash functions. Average O(1) operations. Collision handling: Chaining, Open Addressing.
- Graph: Nodes (Vertices) connected by edges. Directed/Undirected, Weighted/Unweighted.
- Trie: Tree-like structure for strings. Efficient prefix searching (O(m) where m is word length).
- B-Tree: Self-balancing multi-way tree. Optimized for disk I/O. Used in databases and file systems.
6. Common Pitfalls & Tips
- Off-by-one errors: Carefully check loop boundaries, especially with 0-based indexing.
- Recursion depth: For large inputs, prefer iterative solutions or increase recursion limit.
- Hash map collisions: Ensure a good hash function and reasonable load factor (e.g., 0.75).
- Integer overflow: When calculating sums in problems like "Maximum Subarray", use appropriate data types (e.g., `long` in Java).
- Memory leaks: In languages like C/C++, always free dynamically allocated memory.
- Reading the problem: Always read the constraints first. They dictate the required complexity (e.g., n ≤ 10⁶ -> O(n log n) is acceptable).
7. Complexity Comparison Visualization
For n = 10⁶ elements:
- O(1): 1 operation (Instant)
- O(log n): ~20 operations (Instant)
- O(n): 1,000,000 operations (~0.01s)
- O(n log n): ~20,000,000 operations (~0.2s)
- O(n²): 10¹² operations (~10 minutes)
- O(2ⁿ): Impossible for n=10⁶
🎉 Congratulations! You've completed the entire DSA Tutorial Series! 🎉
You now have a solid foundation in Data Structures and Algorithms. Keep practicing, stay curious, and never stop learning!
PreviousDSA Roadmap for Beginners: Step-by-Step Guide to Master in DSA
Next You're at the end!
Ready to master Data Structures & Algorithms?
Learn DSA hands-on with mentor-led sessions, real interview practice, and placement support.