2.1. 空间比较¶

既然你已经见过了线性表的两种截然不同的实现， 自然会想知道哪一种更好。 特别是，如果要为某个任务实现一个线性表， 你应当选择哪种实现？

给定一组待存储的元素，无论它们是简单的整数 还是带有很多字段的大对象，都要占据一定的空间。 而像线性表这样的容器型数据结构， 还需要一些额外的空间来组织所存储的元素。 这些额外的空间称为 空间开销 。

基于数组的线性表 的缺点是必须先确定其大小，然后才能分配数组。 基于数组的线性表无法增长到超出预定的大小。 只要线性表中只含有少量元素， 大量空间就可能被一个近乎空置的数组占用。 这些空闲的空间就是基于数组的线性表所需的空间开销。 链表 的优点是只需为实际存于线性表中的对象分配空间。 只要有可用的 自由存储区 内存， 链表上的元素数量就没有上限。 链表所需的空间量为 \(\Theta(n)\) ， 而基于数组的线性表实现所需的空间量为 \(\Omega(n)\) ， 还可能更大。

基于数组的线性表的优点是单个元素不会浪费任何空间。 链表则要求在每个线性表结点中都增加一个 next 字段的额外指针。 因此，链表把这些 next 指针当作空间开销。 如果元素很小，链接的空间开销就可能占总存储量的相当大比例。 当基于数组的线性表所用的数组被完全填满时， 不存在浪费的空间，也就没有空间开销。 此时，基于数组的线性表会比链式实现更节省空间， 差距为一个常数因子。

有一个简单的公式可以判断：在特定情形下， 基于数组的线性表与链表实现哪一个更节省空间。 设 \(n\) 为线性表中当前的元素个数， \(P\) 为指针的大小（以存储单位计，通常为 4 字节）， \(E\) 为数据元素的大小（以存储单位计，取值不限： 从一个布尔变量的 1 个比特， 直到复杂记录的数千字节甚至更多）， \(D\) 为数组中最多能存储的线性表元素个数。 基于数组的线性表所需的空间量为 \(DE\) ， 与任意给定时刻线性表中实际存储的元素个数无关。 链表所需的空间量为 \(n(P + E)\) 。 对于给定的 \(n\) 值，两个表达式中较小者， 决定了存储 \(n\) 个元素时更节省空间的实现。 一般来说，当线性表中的元素相对较少时， 链式实现比基于数组的实现所需的空间更少； 反之，当数组接近填满时，基于数组的实现变得更节省空间。 利用该等式，我们可以解出 \(n\) ， 从而确定 平衡点 —— 在任意特定情形下，超过该点之后， 基于数组的实现都更节省空间。该点满足

如果 \(P = E\) ，那么平衡点位于 \(D/2\) 处。 当元素字段是一个 4 字节的 int 值或一个指针， 而 next 字段是典型的 4 字节指针时， 就会出现这种情况。 也就是说，只要数组的填充程度超过一半， 基于数组的实现就更高效 （前提是链接字段与元素字段大小相同）。

根据经验，当所实现的线性表的元素个数变化很大或不可预知时， 链表更节省空间。 而当用户事先大致知道线性表会增长到多大， 并且确信线性表绝不会超出某个界限时， 基于数组的线性表通常更节省空间。

2.2. 时间比较¶

按位置访问时，基于数组的线性表更快。 通过 next 和 prev 方法， 可以方便地向前或向后调整位置。 这些操作总是需要 \(\Theta(1)\) 时间。 相比之下，单链表无法显式访问前一个元素， 按位置访问必须从线性表前端（或当前位置） 一路前进到指定位置。 如果我们假设每次调用 prev 或 moveToPos 时， 线性表上每个位置被访问的概率相等， 那么这两种操作在平均情况和最坏情况下 都需要 \(\Theta(n)\) 时间。

如果已经获得指向线性表中合适位置的指针， 链表的 insert 和 remove 方法只需要 \(\Theta(1)\) 时间。 基于数组的线性表则必须在数组内将其余元素整体上移或下移。 这在平均情况和最坏情况下需要 \(\Theta(n)\) 时间。 对许多应用而言，插入和删除元素的时间支配着所有其他操作。 因此，链表往往比基于数组的线性表更受青睐。

在实现基于数组的线性表时， 实现者可以允许数组的大小随实际存储的元素数量增长和收缩。 这种数据结构称为 动态数组 。 例如，Java 和 C++/STL 的 Vector 类都实现了动态数组， 而 JavaScript 的数组天生就是动态的。 动态数组让程序员得以绕开传统数组的一个限制—— 数组一旦创建，其大小就无法改变。 这也意味着，直到动态数组即将投入使用时才需要为它分配空间。 这种方法的缺点是：处理数组的空间调整需要时间。 数组每次扩容，都必须复制其内容。 动态数组的一个良好实现会以合理的方式增长和收缩数组， 使得一系列插入/删除操作的总体代价保持相对低廉， 尽管偶尔某次插入/删除操作的代价可能很高。 一条简单的经验法则是：数组填满时将其大小加倍， 数组只剩四分之一满时将其大小减半。 要分析动态数组操作随时间累积的总体代价， 需要使用一种称为 摊还分析 的技术。