Reference Resources
Data Structure Operation Complexity Quick Reference
| Data Structure | Insert | Delete | Search | Traverse |
|---|---|---|---|---|
| Array | O(n) middle / O(1) end | O(n) middle / O(1) end | O(1) by index / O(n) by value | O(n) |
| Singly Linked List | O(1) head / O(n) tail | O(1) head / O(n) specified position | O(n) | O(n) |
| Doubly Linked List | O(1) (known position) | O(1) (known position) | O(n) | O(n) |
| Stack | O(1) | O(1) | — | — |
| Queue | O(1) | O(1) | — | — |
| Priority Queue (Heap) | O(log n) | O(log n) | — | — |
| Binary Tree (BST) | O(log n)~O(n) | O(log n)~O(n) | O(log n)~O(n) | O(n) |
| Hash Table | O(1) average | O(1) average | O(1) average | — |
| Heap | O(log n) | O(log n) | O(1) heap top | — |
| Graph | O(1) adjacency list | O(E) | O(V+E) DFS/BFS | O(V+E) |
Sorting Algorithm Quick Reference
| Algorithm | Average Complexity | Worst-case Complexity | Space | Stable | One-liner |
|---|---|---|---|---|---|
| Bubble | O(n²) | O(n²) | O(1) | Yes | Simple but slow, suitable for teaching |
| Selection | O(n²) | O(n²) | O(1) | no | Fewest swaps |
| Insertion | O(n²) | O(n²) | O(1) | Yes | Optimal for small-scale or nearly sorted data |
| Quick | O(n log n) | O(n²) | O(log n) | no | Universal first choice, clever partitioning idea |
| Merge | O(n log n) | O(n log n) | O(n) | Yes | Stable performance but requires extra space |
| Heap Sort | O(n log n) | O(n log n) | O(1) | no | In-place sorting, optimal space |
| Shell | O(n^1.3) | O(n²) | O(1) | no | Improved version of insertion sort |
Big O Complexity Ranking
| Complexity | n=10 | n=1000 | n=1000000 | Rating |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | Optimal |
| O(log n) | ~3 | ~10 | ~20 | Excellent |
| O(n) | 10 | 1000 | 1000000 | Acceptable |
| O(n log n) | ~30 | ~10000 | ~20000000 | Fair |
| O(n²) | 100 | 1000000 | 10¹² | Be wary |
| O(2ⁿ) | 1024 | Astronomical number | Impossible | Unusable |
Recommended Learning Resources
| Type | Name | Description |
|---|---|---|
| Classic Textbook | "Data Structures (C Language Edition)" by Yan Weimin | Standard textbook for domestic universities, comprehensive system |
| Classic Textbook | "Introduction to Algorithms" (CLRS) | Authoritative reference in the algorithm field, in-depth and systematic |
| Online Practice | LeetCode (leetcode.com) | Massive algorithm problems, top choice for interview practice |
| Online Practice | Nowcoder (nowcoder.com) | Domestic interview practice platform, suitable for campus recruitment preparation |
| Visualization Tool | Visualgo (visualgo.net) | Algorithm visualization, helps understand execution process |
| Online Compiler | Compiler Explorer (godbolt.org) | View assembly after C code compilation, understand underlying details |