动态数组
复习
- 数组：连续存储，随机访问快，增删慢
- 摊还分析：偶尔昂贵的操作会被大量廉价操作摊平
- 时间与空间的交换：用空间可以换时间
TL;DR
- 动态数组在容量不足时自动扩容
- 扩容通常要申请更大的空间，并复制旧元素
- 若每次容量翻倍，插入的摊还代价是
O(1) - 它兼顾了数组的随机访问与灵活增长
正文
普通数组的容量在创建时就定死了。可很多时候，我们事先并不知道会放多少数据。总不能一开始就申请一个特别大的空间，白白浪费吧？
于是有了会“自己长大”的动态数组（dynamic array）。
满了就换个大房子
动态数组对外看起来还是数组，但内部多维护了一个信息：当前用了多少（size）、总共能放多少（capacity）。
当要加入新元素，而空间已经装满时，它做一串动作：
- 申请一块更大的空间（通常是原来的两倍）
- 把旧元素全部复制过去
- 释放旧空间，继续使用新空间
对使用者来说，它就像一个永远装得下的数组；但内部其实悄悄搬过一次家。
搬家的代价被摊平了
复制全部元素是 O(n)，看着很吓人。但别忘了上一章讲过的摊还分析。
如果每次扩容都把容量翻倍，那么一次昂贵的复制之后，要再经过差不多同样多次的廉价插入，才会再次装满。把这一连串操作平均下来，每次插入的代价仍然是 O(1)。
这也是为什么扩容通常选“翻倍”，而不是“每次只加一个格”。如果每次只加一格，就会频繁复制，摊还代价反而变成 O(n)。翻倍，正是为了让昂贵操作足够稀疏。
它保留了什么，牺牲了什么
动态数组的优点很清楚：既有数组的 O(1) 随机访问，又能灵活地增长。
但它并没有改变数组的本质：在中间插入或删除，仍然要移动元素，仍是 O(n)。 扩容只解决了“容量不够”，没解决“挪动”的问题。
那么，如果频繁需要在中间增删，又希望代价小，该怎么办？那就要换一种组织方式了——先把它的基础工具“指针”准备好。
思考题 1
为什么动态数组扩容时选择“翻倍”，而不是每次只加一个位置？
思考题 2
动态数组的随机访问性能，会被扩容影响吗？为什么？
小结
知识点
- 动态数组能按需自动扩容
- 扩容通常申请两倍空间并复制元素
- 容量翻倍使插入摊还代价为
O(1) - 中间插入删除仍是
O(n)，随机访问仍是O(1)
参考资料
- Wikipedia(zh)：动态数组：可自动扩展容量的数组
- Wikipedia(zh)：摊还分析：估算一连串操作的平均代价
思考题答案（仅供参考）
思考题 1
因为翻倍能让两次扩容之间插入足够多的元素，把一次昂贵的复制摊薄到多次廉价操作上，从而使摊还代价保持 O(1)。若每次只加一个位置，就会频繁复制，摊还代价反而退化为 O(n)。
思考题 2
不会。扩容改变的只是元素存放的地址，以及内部的容量，但元素依旧连续、等大、可按下标一步定位。所以随机访问仍是 O(1)，扩容只是偶发的搬家，不影响这一点。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪