9.2　为什么存在不同种类的容器

为什么会有不同种类的容器呢？这是因为各种容器兼具长处和短处。

容器中的数据实际上是存放在内存中的。内存就像投币式储物柜，由固定大小的箱子按秩序排列，并编上序号（图 9.1）。容器的类型不同，内存中存储数据的方式也不同，其长处和短处正是由这些差异而来。接下来我们就来看一下存储数据方式的差异。

图 9.1　内存 固定大小的箱子按秩序排列并编好序号

数组与链表

我们先来比较两种容器，一种是数组，另一种是链表 2。

2链表的英文是 Linked List，发明于 1955 年左右。链表常被认为是一种数据结构。其实数据结构是一个很宽泛的概念，它不仅仅指能放入多个元素的东西，还包含更广泛的含义。

往数组和链表中都放入相同的三个数据 A、B、C，内存中会出现什么样的情形呢？其模式图如图 9.2。

在数组中，A、B、C 按顺序存放着，非常直观简单。而在链表中，存放了 A 数据的下一个箱子中还存放有表示下一个值在何处的信息。存放 C 数据的箱子的下一个箱子中存放的是 0，表示没有下一个值了。该图表现了链表中存储数据的两种不同方式，但不管何种方式，我们都可以看出 A、B、C 三个数据是按此种顺序存放进去的。

图 9.2　内存中的数据存放方式

往数组中插入数值

乍一看，链表的这种数据存放方式要消耗两倍于数组的内存，有些浪费。然而，这种方式的长处也很明显。其一就是插入数值所需的时间。比如要在 A 和 B 之间插入数值 Z，该如何操作呢？

数组中的存放方式是数值按顺序排列存放的，也就是说，要先把 Z 放入 101 号箱子，再分别把 B 和 C 重新挪入 102 号和 103 号箱子中（图 9.3）。往数组中插入数值时，要求把插入此位置的所有元素都重新挪到别的位置去（复制）。

图 9.3　往数组中插入数值需要进行复制

这个例子中因为数组中存放的数据量不多，只需复制两次就可以了。但如果要在一个有 10 000 个元素的数组的初始位置插入一个元素，有要进行 10 000 次复制，工作量可想而知。

往链表中插入数值

与之相对地，链表不要求在内存中按顺序存储，而是在内存中同时存放表示下一个数据存放位置的信息。

往链表中插入数据，首先要在合适的位置插入数据 Z（图 9.4）。

图 9.4　链表中插入数据只需放入两个新的箱子并修改一个箱子的内容就 OK

图中是在 106 位置插入的箱子，事实上，只要是空着的位置，在哪插入都没有关系。Z 的下一个箱子中存放了 Z 的下一个值所在的位置信息。该信息内容是 102，表示下一个值存放在 102 位置。最后，在 101 号箱子中存放的 A 的下一个值所在的位置信息被替换了，换成 A 的下一个值即 Z 所在的位置，也就是 106 号箱子。

对于链表来说，只需要添加两个新的箱子并修改一个箱子的内容，便可以实现新的元素的插入。即使有 10 000 个元素，这个工作量也是不变的。

在元素较少时，使用数组还是链表的差别并不大。但是随着元素个数的增加，数组所需时间不断增加，而链表所需时间却没有变化。所以对于元素多、插入操作频繁的情况，链表是更适合的。

链表的模式图

数组在内存中的存储方式是连续的，大前提就是要有连续的内存区域。而链表却没有这一要求，它可以使用零散细分的内存区域。与数组不一样，对于链表来说，这些零散的区域在内存中所处的位置并不太重要。因此有如图 9.5 所示的一般表现形式，不明确指示出在内存的哪个位置，而只是用箭头来表示指向关系 3。

3这里的箭头表示位置信息，类似 C 语言中的指针。但不太赞成用指针这个名称的人比较多，这里姑且不使用指针这个词。

图 9.5　链表的模式图

链表的长处与短处

本节我们用大 O 表示法来说明链表的长处与短处。

链表的长处是插入元素的计算量为 O(1)，而对于数组是 O(n)。元素的删除同样如此。链表只需要修改表示下一个元素所在位置的信息，因此计算量为 O(1)。而对于数组则需要把删除元素之后的所有元素都挪位，因此计算量为 O(n)。

另一方面，链表也有其短处，要获得第 n 个元素需要花费较长时间。

因为数组中的存放方式固定的，因此很容易得到第 n 个元素。比如要想知道从 100 号位置开始的数组中的第 10 个元素，在 100 上加上 10，得到的 110 号位置上读取到的数据就是它了。这时，计算量是 O(1)4。

4数组的第一个元素称为第 0 个。

而链表可以把各元素存放在喜欢的任何位置，因此无法使用该方法 获得第 n 个元素。比如要知道从 100 号位置开始的链表的第 10 个元素，首先要读取最前面的元素，找到下一个元素所在的位置，再读取下一个元素，然后再找到其下一个元素所在的位置，如此反复操作 10 次才可以得到第 10 个元素。这时，计算量是 O(n)。

所以说，数组和链表都有各自的长处和短处。在实际使用中要留意自己使用的容器类型和特点，以及它是否和自己所要达到的目的相符。

专栏 5

大 O 表示法——简洁地表达计算时间和数据量之间的关系

在此，我们先介绍一种能简洁方便地表达计算所花时间和数据量之间关系的方法。

如果是像数组中的插入一样的操作，当数据量 n 翻倍时，计算所花费的时间也翻倍，这种性质用 O(n ) 表示，读作 n 的数量级 6。

而如果是像链表的插入一样的操作，即使数据量 n 翻倍，计算所花时间也不变，这种性质用 O(1) 表示，读作常数的数量级 7。

除此之外，当数据量变为 2 倍、3 倍时，计算时间增加到 4 倍、9 倍，这个用 O(n²) 表示；当数据量变成 2 倍时增加的计算时间，和数据量从 2 倍增加到 4 倍时增加的计算时间相同，这种情形用 O(log n) 表示。对于大量数据，进行 for 循环是 O(n)，进行二重 for 循环是 O(n²)。

随着 n 的增大，大致有以下关系：

O(1) < O(log n) < O(n) < O(n²)

这种表达方式只是非常粗略地表现出函数的增加速度和方式，因此不管是 n²+2n+1 还是 3 n² 都表达为 O(n²)。这样写是为了省去一些细节。

5本专栏仅针对大 O 表示法进行大致说明，在此不涉及严密的定义，读者可以从其他著作中了解。如《C 语言による最新アルゴリズム事典》（中文译名：基于最新算法的 C 语言实现大全）一书中关于 O(n) 有如下解释：对于常数 C（>0），如果存在数 N，使得当 n≧N 时 | f(n)|≦c|g(n)| 一定成立，那么当 n→∞时 f(n) ＝ O(g(n)) 成立。

6也称作线性时间。

7也称作常数时间。

语言的差异

在 Java、Python、Ruby 等语言中都将数组作为一种最基本的容器标准 8。比如 Python 语言中的 [1, 2, 3]，里面的元素在内存中是排列好存放的。

8数组在对象的包装下辅以一些便利的操作方法的情况很多见。

与此相对应，在 LISP、Scheme、Haskell 等语言中都将链表作为一种最基本的容器。LISP 语言中的 (1 2 3) 和 Haskell 语言中的 [1, 2, 3] 表达的是当前值以及下一个值存放位置信息的集合。

不言而喻，大多数语言中的容器都是在库中提供的。Python 语言中的 collection.deque 是使用链表的容器 9，Haskell 语言中的 Data.Array 是使用了数组的容器。

9准确来讲，前面介绍的链表包括下一个数值的位置信息，而 Python 语言的 deque 在此基础上还包括前一个数值的位置信息，是一种双向链表。