Cheatsheet
A quick recap of all the data structures and algorithms covered in this tutorial.
Data Structures - Time Complexity
| Data Structure |
Access |
Search |
Insert |
Delete |
| Array |
O(1) |
O(n) |
O(n) |
O(n) |
| Linked List |
O(n) |
O(n) |
O(1)* |
O(1)* |
| Stack |
O(n) |
O(n) |
O(1) |
O(1) |
| Queue |
O(n) |
O(n) |
O(1) |
O(1) |
| Hash Table |
- |
O(1) avg |
O(1) avg |
O(1) avg |
| BST |
O(log n) avg |
O(log n) avg |
O(log n) avg |
O(log n) avg |
| AVL Tree |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
| Red-Black Tree |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
| Heap |
- |
O(n) |
O(log n) |
O(log n) |
| Trie |
O(m) |
O(m) |
O(m) |
O(m) |
*O(1) if you already hold a reference to the node. m = key length.
Sorting Algorithms
| 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 |
Graph Algorithms
| Algorithm |
Time |
Notes |
| BFS |
O(V + E) |
Level traversal, shortest path unweighted |
| DFS |
O(V + E) |
Deep traversal, cycle detection |
| Dijkstra |
O((V+E) log V) |
Shortest path weighted, no negative edges |
| Kruskal |
O(E log E) |
MST, good for sparse graphs |
| Prim |
O(E log V) |
MST, good for dense graphs |
What to Use When
| Need |
Best Choice |
| Fast access by index |
Array |
| Frequent insert/delete in the middle |
Linked List |
| LIFO operations |
Stack |
| FIFO operations |
Queue |
| Key-value lookup |
Hash Table |
| Sorted data + fast search |
BST / AVL / Red-Black |
| Highest priority |
Heap / Priority Queue |
| String prefix search |
Trie |
| Shortest path |
Dijkstra (weighted) / BFS (unweighted) |
| Connect all nodes |
Kruskal / Prim (MST) |
| Sorting large data |
Merge Sort / Quick Sort |
| Sorting small data |
Insertion Sort |
| Nearly sorted data |
Insertion Sort / Bubble Sort |
Big O Cheat
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
Constant Logarithmic Linear Lin-log Quad Exponential Factorial
Tips
- First understand which operations are performed most frequently.
- The data size determines the right algorithm.
- There is always a trade-off between time and memory.
- Benchmark with real data, not just theory.
- Built-in data structures are already optimized for most cases.
Congratulations on finishing the Data Structures tutorial! Keep practicing and apply what you've learned in real projects.
