[数据结构02] 列表1 – 用数组实现列表

2026-07-22

笔记

共

2,175

字，大约需要

9–14

分钟

列表（List）

最基本的列表（静态列表）

静态列表和 C 中的数组（Array）一样：

可以存储给定数量和类型的元素；
可以写/改某个位置的元素；
可以读取某个位置的元素；

动态列表

可以为空；
可以在列表的任意位置插入/删除元素；
可以计算列表的元素数；
可以读/写某一个位置的元素；
可以为列表指定类型；

实现一个动态列表

方法

以 C 语言为例，可以用数组实现一个动态列表，只需要这样做：

创建一个非常大的数组，规定一个最大长度 MAXSIZE；
创建一个变量 size，表示列表最后一项的下标，如果列表为空，这个值可以是 -1；

int size = 0;
int capacity = MAXSIZE;

int size = 0;
int capacity = MAXSIZE;

列表需要能够在任意位置插入一个元素，因为数组原生不提供这种功能，所以我们要自己实现：

如果我们想要向下标为 n 的位置插入一个数，就要让下标为 n+1 的项及其之后的项，都向后挪动一次；
然后给空出的位置，也就是下标为 n 的位置，赋要插入的值；
把 size 的值加 1；
这个功能可以包装成一个函数 insert(index, element)
例如 insert(2, Animal.dog) 表示在列表的第三项插入一个 dog 元素（因为下标是从 0 开始的）；

用伪代码可以写成：

for (int i = size; i > index; i--) {
    data[i] = data[i - 1];
}

data[index] = element;
size++;

for (int i = size; i > index; i--) {
    data[i] = data[i - 1];
}

data[index] = element;
size++;

同理，如果想删除某个位置的元素，可以把该元素之后的每一项依次向前挪动一项，然后把 size 的值减 1，这个功能可以封装为 remove(index) 函数；

用伪代码可以写成：

for (int i = index; i < size - 1; i++) {
    data[i] = data[i + 1];
}

size--;

for (int i = index; i < size - 1; i++) {
    data[i] = data[i + 1];
}

size--;

这样，我们用 C 中的数组就实现了上述的动态列表：可以用 insert() 插入元素，用 remove() 删除元素，读和改都是数组原本就具备的功能。

问题

我们刚才提到了，由于 C 语言本身的限制，我们在用数组实现动态列表的时候，需要一个最大尺寸 MAXSIZE，但是这个值具体是多少呢？

这个值没有一个合适的大小。

我们可以创建一个容量更大的新数组，并迁移原来的数据到新数组：

创建一个新的更大的数组；
复制旧数组中的所有元素到新的数组；
释放旧数组的内存；

C 语言中普通数组的长度不能直接改变。如果数组位于动态分配的内存中，可以使用 realloc() 尝试扩容；它可能在原地址扩展，也可能申请新空间并复制数据。

那么新数组增加的大小应该是多少？

通常要采用几何扩容，即将大小扩充到原来的 N 倍（N ＞ 1），常见的倍率是 1.5 ~ 2 之间，这取决于对时间和空间的权衡。

主流的选择是 2 倍（如部分 C++ 标准库实现中的 std::vector）或 1.5 倍（Java 的 ArrayList、MSVC 的 std::vector）

这门课之后会介绍具体的原因。

实现一个操作的成本

（一）分析操作的成本

把元素从旧数组复制到新数组的过程有很高的时间成本，在学习数据结构的时候，我们不仅要研究操作及其实现，也要研究操作的时间/空间成本。

对于我们刚刚提到的操作，其时间成本来自以下几个方面：

Access
对某个位置的元素进行读/写存在一个固定的时间成本 O(1)；
Insert
如果我们想要向列表中特定的位置插入元素，我们需要将这个位置之后的所有元素都挪动位置。在最坏的情况下（N = 0，即向开头插入元素时）我们不得不把所有的元素都向后移动一个位置。此时，这个操作花费的时间将与列表的长度成正比，如果列表长度为 n，则这个操作的时间复杂度为 O(n)；
Remove
同理，删除一个元素时，也需要移动元素，并且在最坏的情况下（删除第一项的时候）需要挪动所有的元素，所以时间复杂度同样是 O(n)；
Add
- 列表未满时
  我们把向列表的末尾插入元素称为 Add，在列表未满的时候，这个操作的时间复杂度是 O(1)，也就是花费一个固定的时间，因为在末尾添加元素只需要做一次赋值；
- 列表已满时
  但是在刚好达到最大长度的时候，就需要对整个列表进行一次复制的操作，这个操作的时间成本与列表的长度有关，如果列表长度为 n，时间复杂度为 O(n)；

（二）回顾扩容问题

所以，对于刚才的扩容问题，选择成倍扩容效率最高。

假设一个数组初始大小为 1，我们要连续插入 N 个元素，并且每次扩容都将数组容量扩充到两倍。

当插入第 $2^{k}+1$ 个元素的时候，原容量 $2^{k}$ 已满，需要翻倍扩容到 $2^{k+1}$ ，并复制原来的 $2^{k}$ 个元素。

从始至终，因扩容而需要进行的复制总次数为 $1+2+4+8+…+2^k = 2^{k+1}-1$ 次。

最坏的情况是，在插入第 N 个元素时恰好发生了扩容，那么此时 $N=2^k+1$ ，复制总成本就是

2^{k+1} - 1 = 2 \times 2^k - 1 = 2(N - 1) - 1 = 2N - 3

此外，每一次插入元素还需要进行写入，N 次插入也就是 N 次写入，所以这个情况下，完整的操作成本就是 $T(N) = 3N-3$

当一系列操作之间存在联系，某些昂贵操作不会频繁发生，而且能够证明总成本较低时，就可以做均摊分析。所以我们时间成本均摊到每一次操作上上，即 $\frac{3N-3}{N} < 3$ ，即时间复杂度为 O(1)。

但是如果我们采用“每次满了就将长度增加 100”的策略，而不是翻倍：

第 1~100 次插入，消耗固定的时间，无需扩容。
第 101 次插入：数组满了，触发扩容，需要申请 200 的空间，并复制 100 个旧元素。
第 201 次插入：需要申请 300 的空间，复制 200 个旧元素。
…
第 N 次插入：需要复制 N-100 个元素。

如果取 $N = 100k+1$ ，即在插入第 N 个元素时刚好扩容，完成复制操作的总成本就是

T(N)=100 + 200 + 300 + … + N =\frac{N^2}{200}-\frac{N}{2}

当 N 很大时， $-\frac{N}{2}$ 的影响可以忽略不计，因此总复制次数为 O(N²)，更准确的写法是 Θ(N²)，表示总成本紧确地按照 N² 的速度增长。

将总的复制成本均摊给 N 次插入（即 $\frac{N^2/2}{N}=\frac{N}{200}$ ），平均每次插入的成本会随着 N 线性增长，所以时间复杂度就变成 Θ(N)，远高于翻倍扩容。

所以，我们设计的这个动态列表实现，每一个操作的复杂度：

操作	最坏时间复杂度	说明
按下标读取	(O(1))	通过地址计算直接访问
按下标修改	(O(1))	通过地址计算直接访问
任意位置插入	(O(n))	可能需要移动后续元素
任意位置删除	(O(n))	可能需要移动后续元素
尾部添加，不扩容	(O(1))	直接写入末尾
尾部添加，发生扩容	(O(n))	需要复制原有元素
尾部添加，均摊	(O(1))	多次连续操作的平均成本

总结

用数组实现动态列表，就内存而言效率并不高，因为总有一部分空间是浪费的。其实还存在着一种在大部分情况下，内存利用率更高的动态列表实现方式——链表。

不过，通过数组实现的列表在一些情况下比链表更具优势，这个之后再进行讨论。

Tags: C/C++, C语言, 数据结构