基础数据结构
🏗️ 数组 vs 链表
Section titled “🏗️ 数组 vs 链表”理解数组和链表的本质差异，是掌握所有数据结构的基础。
⚔️数组 vs 链表
3
📦 数组 (Array)
步骤: 0连续内存: 0x1000, 0x1004, 0x1008...
[0]
10
[1]
20
[2]
30
[3]
40
[4]
50
[5]
60
O(1): 直接通过索引计算内存地址: base + index × size
🔗 链表 (Linked List)
步骤: 0非连续: 0x2000 → 0x3050 → 0x1800...
head→
10
→
20
→
30
→
40
→
50
→
60
→
null
O(n): 必须从头节点开始逐个遍历
| 操作 | 数组 | 链表 | 胜者 |
|---|---|---|---|
| 👁️ 访问 | O(1) | O(n) | 🏆 数组 |
| 🔍 搜索 | O(n) | O(n) | 🤝 平手 |
| ➕ 插入 | O(n) | O(1)* | 🏆 链表* |
| 🗑️ 删除 | O(n) | O(1)* | 🏆 链表* |
* 链表插入/删除 O(1) 假设已知位置，否则需要 O(n) 遍历找到位置
📚 栈与队列
Section titled “📚 栈与队列”栈和队列是最基础的线性数据结构，理解 LIFO 和 FIFO 的差异。
📚栈与队列
📥 栈 (Stack) - LIFO
后进先出10
20
30
栈底
↑ 栈顶 (Top): 30
🚶 队列 (Queue) - FIFO
先进先出出口←
10
20
30
入口←
队首 (Front): 10队尾 (Rear): 30
| 特性 | 📥 栈 | 🚶 队列 |
|---|---|---|
| 原则 | LIFO 后进先出 | FIFO 先进先出 |
| 插入 | Push O(1) | Enqueue O(1) |
| 删除 | Pop O(1) | Dequeue O(1) |
| 查看 | Peek/Top O(1) | Front O(1) |
| 典型应用 | 函数调用、撤销、DFS | 任务调度、BFS、缓冲 |
📊 复杂度对比
Section titled “📊 复杂度对比”| 操作 | 数组 | 链表 | 栈 | 队列 |
|---|---|---|---|---|
| 访问 (按索引) | O(1) ✅ | O(n) | O(n) | O(n) |
| 搜索 | O(n) | O(n) | O(n) | O(n) |
| 插入 (头部) | O(n) | O(1) ✅ | - | - |
| 插入 (尾部) | O(1) 摊销 | O(n)/O(1)* | O(1) | O(1) |
| 删除 (头部) | O(n) | O(1) ✅ | - | O(1) |
| 删除 (尾部) | O(1) | O(n) | O(1) | O(n) |
*链表尾部插入: 单链表 O(n)，双链表或带尾指针 O(1)
💡 选择指南
Section titled “💡 选择指南”- 需要频繁随机访问
- 数据量固定或变化小
- 需要缓存友好 (连续内存)
- 需要频繁插入/删除
- 不需要随机访问
- 数据量变化大
- 需要 LIFO (后进先出)
- 函数调用、撤销操作、括号匹配、DFS
- 需要 FIFO (先进先出)
- 任务调度、BFS、消息缓冲