动态数组是怎样实现的？

Question

现在的很多高级语言里面的Array都是动态数组，这个是怎么实现的？按理说效率应该很低的啊，而且swift里面还可以拷内存啊什么的

Answer 1

反对 @肥肥的兔子 的观点。

题主明确说了是高级语言中的 Array，很显然 Array 就是线性表的顺序存储，而不是 linked list，不过在实现中，有一些变通方法，然而 Ø(1) 的读取等数组的特征却是必须的，你的 linked list 如何 Ø(1) 读取？

我讲一下三种实现方式吧：

1. 模仿 std::vector 的实现，比如说 ArrayList 等，当 storage() == size() 事件发生的时候（逻辑元素数量已经达到了存储容量），将会按照增长因子进行容量翻倍，并且将原有数据拷贝到新的内存中。关于增长因子有必要一提，不少实现中都是 2，然而 sum(i ^ 2, {i, 0, n - 1} 是小于 n^2 的，所以之前的内存都不会被重用，cache 不友好，理论表明，最好的增长因子是 1 ＋ (√5 - 1) / 2，即黄金分割率，工程上大多使用 1.5. 时间复杂度最佳Ø(1)，最坏Ø(n)，然而扩容的期望值为 1 / n，算出平均时间复杂度 = Ø(n) * 1 / n = Ø(1)

2. 如果你能保证该动态数组的元素一定有默认构造函数，而且元素能够被 realloc() 或者其他语言中类似的东西分配，那就可以在上述事件发生时进行 realloc()，时间复杂度 Ø(1).

3. 模仿 std::deque 的实现，一般实现为多块定长数组，增长时间复杂度是 Ø(1) 了，顺带也支持了 front 上操作，何乐而不为呢？唯一的缺点是读取、插入看似都是 Ø(1)，然而实际上操作更复杂，系数比较大，如果只有尾部操作，速度反而比 std::vector、ArrayList 要慢 30% 左右。

Answer 2

update

经 @rushcheyo提醒，确实链式存储的方法不太靠谱。确实这方面我不太了解，所以我在答案前也说明是抛砖引玉一下，后来上网查阅一下才大概弄懂。另外，题主可以参考一下这里有代码和对应的解释。

---

原答案

抛砖引玉一下，貌似有两种方式，第一种是添加元素时会拷贝之前的内容，和你新添加的内容放到新的空间里（空间上仍然是连续存储），第二种是采用链式存储（空间上不连续）。

Answer 3

首先，任何数据结构都会有各自的优缺点，使用时需要根据需求取舍。比如需要高效率的随机访问（random access），可能就会有低效率的随机插入/删除（insert/delete in middle），反之亦然。

其次，关于动态数组（高效率的随机访问）的实现，题主可以参考 C++ 中 std::vector。简单来说与 @rushcheyo 的说法类似，初始时系统会分配一块内存，每当数组中的元素个数达到上限时，就会再次分配一块更大的内存（增加的速率由算法决定），然后将原有的元素移动到新分配的内存中去（当然如果数组的元素类型不支持移动构造函数（move constructor），则会拷贝数组中的元素到新内存中）。其实现效率并不低。另外 C++11 中引入了右值引用（rvalue reference）可以有效的减少在移动数组时拷贝的发生。

需要注意的是 std::vector 对于在数组中间的插入/删除操作是相对低效率的（一般情况下仍然可以接受），它会移动被插入/删除元素后面的所有元素。

对于 Python 中的 List，根据官方文档可知，也是按照类似的方法进行设计的。根据这篇博文，在 Python 最常见实现的 CPython 中，List 是通过一个变长数组实现的，数组的元素是指向 List 中元素的指针。

Answer 4

补充一个Python的实现：
[https://github.com/python/cpython/blob/master/Include/listobject.h#L23-L40]
[https://github.com/python/cpython/blob/master/Objects/listobject.c]
Python里面内置List的实现方式很简单，就是一个指针数组，分配在堆上，加一个allocated字段保存指针数组当前已经分配的内存数和一个ob_size字段保存当前已经占用的内存数。Python中List操作若涉及长度变化就会判断当前List已经分配的内存数是否足够，如果不够就realloc重新分配内存，够了就直接用已经分配的内存。