数组
Vol 2：算法森林探险 · 数组特辑
遭遇战：林间驿站的两条岔路
你走在算法森林小径上，面前两条岔路。
木牌 A（数组路）： 笔直开阔的大路，路边整齐排列 30 个树洞驿站，门牌号固定刻在石板上——找 17 号？直接走过去就行。
木牌 B（链表路）： 弯弯曲曲的小路，棚屋散落，靠细绳串在一起，路线随时在变。
本章先走木牌 A。
什么是数组？
连续的内存块，像一排电影院座位。座位号就是下标。
地址： 基址 基+4 基+8 基+12 基+16
索引： [0] [1] [2] [3] [4]
┌──────┬──────┬──────┬──────┬──────┐
│ 10 │ 20 │ 30 │ 40 │ 50 │
└──────┴──────┴──────┴──────┴──────┘静态数组
遇到问题： 想看第 17 号驿站？门牌号固定——知道在哪一格就行。
python
from array import array
static_arr = array('i', [10, 20, 30, 40, 50])
print(static_arr[2]) # 30
# 输出: 30为什么随机访问是 O(1)？ arr[k] = 基地址 + k × 元素大小。一个乘法 + 一个加法——与 n 无关。
动态数组
遇到问题： 想新增驿站？静态数组长度不能变——得另找空地搬家。
Python list、Java ArrayList、C++ std::vector 底层还是连续数组，但容量不够时自动扩容：
python
arr = []
for i in range(10):
arr.append(i)
# 扩容因子约 1.125 倍（Python 3.x）
# ArrayList 1.5 倍，std::vector 2 倍每次扩容 O(n)（分配 + 拷贝），但均摊到单次 append 是 O(1)。
复杂度表
| 操作 | 静态数组 | 动态数组 |
|---|---|---|
随机访问 arr[k] | O(1) | O(1) |
| 末尾插入 | 不可变 | O(1) / O(n) / 摊销 O(1) |
| 中间/开头插入 | — | O(n) |
| 按值查找 | O(n) | O(n) |
| 删除末尾 | — | O(1) |
| 删除中间 | — | O(n) |
插一句： 知道元素数量时，Java 用
new ArrayList<>(initialCapacity)，C++ 用reserve(n)预分配，避免多次扩容。
常见陷阱
| 说法 | 真相 |
|---|---|
| "Python list 是链表" | ❌ 动态数组（连续内存 + O(1) 索引） |
| "数组插入慢，链表一定更快" | ❌ 找位置也是 O(n)，加上缓存差异数组往往更优 |
| "动态数组是无限的" | ❌ 只是伪装成无限。知道上限时一次性分配最省事 |
通关挑战
- 手写动态数组 resize：容量满时翻倍，拷贝旧元素
- 用数组实现环形队列（循环利用删除位置）
验收标准
- [ ] 能画出数组连续内存布局
- [ ] 能解释
arr[k]为什么是 O(1) - [ ] 能解释"动态数组末尾插入是摊销 O(1)"
- [ ] 能说出数组最怕什么操作（中间插入/删除）
旅人笔记
连续内存 + O(1) 随机访问 = 数据结构世界的基石。95% 实战场景，动态数组就是默认选择。
→ 下一站预告
领教了数组的直来直往，该拐进木牌 B 了——链表。没有下标，全靠指针。插入 O(1)，但找第 k 个元素？一个一个数过去吧。
继续阅读：链表 →