动态数组

动态数组
术语名称	动态数组
英语名称	dynamic array
别名	变长数组, resizable array, growable array, array list

动态数组(dynamic array)或变长数组(resizable array)指逻辑结构为线性表、存储结构为数组，且数组长度可变的数据结构。也就是长度可变的顺序表。

在有些编程语言中，动态数组可能被实现为基本的数组类型。

动态数组通常涉及内存的动态分配、移动和动态释放，因此被称为动态数组。 本质上，动态数组和静态数组的区分是其是否涉及运行期的（动态）内存分配释放操作。 即使长度不进行变更，如果语言允许数组长度编译时未知，在运行期重新分配，这一数组也视为不太典型的动态数组； 相反，如果编译时预设最大长度，运行期修改其使用范围，则视为不太典型的静态数组。

语言实例

动态数组
语言	版本/库	对应内容	说明
C	C89	包括三种： 通过动态分配和指针转换实现，如malloc,calloc,realloc系列函数 变长数组(variable-length array, VLA)语法（GCC 扩展，C99 采纳），不要求编译期确定长度的数组，长度可以接受整形表达式，运行时动态分配 柔性数组（GCC 扩展，C99 采纳），结构体最后一个成员是长度为 0 的数组，运行时加上数组一起分配内存，并通过这个指向成员后的数组基址索引元素	标准库及语法规则
C++	C++98	std::vector	STL

实现实例

libcxx: libc/src/__support/CPP/array.h

libstdc++: libstdc++-v3/include/std/array

GSSDS 定义

GSSDS: array/include/sds/dynamic_array/dynamic_array.h

时间复杂度估计与优化

本节讨论动态数组对其逻辑结构线性表的操作实现。

插入删除操作

由于需要保持索引与地址的公式关系，元素的插入和删除需要较复杂的操作，见数组的插入、删除。

重新分配操作

动态数组的一个常见使用方式是逐渐加入新元素，如果每次扩展 [math]\displaystyle{ \Delta s }[/math] 的大小，此时添加 [math]\displaystyle{ n }[/math] 次需要添加 [math]\displaystyle{ \tfrac{n}{\Delta s} }[/math] 次重新的内存分配。如果每次以不大于 2 的比例增加，则这个复杂度可以被平摊到线性。这一比例称为增长因子(growth factor)。在不同的实现中，增长因子可能为 1.5 （如 MSVC ， Java ），也可能为 2 （如 gcc libcxx ， clang stdlibc++） 。

时间复杂度

记数组长度为 [math]\displaystyle{ n }[/math] 。

操作		最好	最坏	平均
基本操作	初始化 Create	一次分配，可能和是否指定预计长度相关
	长度 Length/Size	[math]\displaystyle{ O(1) }[/math] ，用保存的长度或指针差
	清空	一次释放，可能和长度有关
元素获取	指定索引、指定位置 Get	[math]\displaystyle{ O(1) }[/math] ，只需要计算地址偏移
	头部 Head
	尾部 Rear
插入删除	动态内存分配附加	平摊 [math]\displaystyle{ O(n) }[/math] ，每次使用增长因子扩展
	指定索引、指定位置（无重新分配） Insert/Remove	[math]\displaystyle{ \Theta(1) }[/math] ，尾部	[math]\displaystyle{ \Theta(n) }[/math] ，头部	[math]\displaystyle{ \sim\tfrac{n}{2}=\Theta(n) }[/math] ，平均后续长度
	头部（无重新分配）	[math]\displaystyle{ \Theta(n) }[/math]
	尾部（无重新分配）	[math]\displaystyle{ \Theta(1) }[/math]
元素顺序	指定位置前趋后继 Pred/Succ	[math]\displaystyle{ \Theta(1) }[/math] ，只需要计算地址偏移

模板:数据结构