上一篇文章中，我们一起探索了二分查找算法。（什么？你没看到？快戳本链接去看一看）在算法的实现过程中，我们选择了数组作为存储算法中相关数据的载体。那样的选择合适吗？能否将它换为其他的存储结构实现？如果换作其他的存储结构，算法的效率又会如何？今天，我们就来一起探索一下。
熟悉数组的人都知道，数组在计算机内存中是连续存储的。具体如下图所示：
实际运用中，数组由于是连续存储，我们可以很方便的通过数组下标来访问数组中的任意一个元素（这样的访问方式，给它一个高级一点的名字就叫做“随机访问”【Random access】）。举个例子，假设数组起始地址为 \(a\) ，待访问的数据下标为 \(i\) 【注意，下标从 0 开始】，存储每一个数据所需的空间大小为 \(m\) ，那么该数据在内存中的地址可以由下式给出：
\[ a ＋ i × m \]
观察这个式子，进一步，我们可以发现：该式中并不含表示数组容量大小的因子。换句话说，访问数组中的任意元素与数组的容量大小无关。无论数组的容量有多大，只需知道数据在数组中的下标，我们就可以很容易的通过上式在常数时间内获取数组中的对应的数据。用“大O”来描述在数组中访问任意一个数据的时间复杂度，就是 \(O(1)\) 。（这里的“1”的含义不是指常数时间等于 1 ，而是用 1 来代表常数时间）。
在很多程序和算法中，都要求数据的存储结构能够提供这样的方便的“随机访问”的功能，这也就是数组在日常编程中经常使用的原因。
但是，数组真的完美无缺吗？
我们尝试换一个角度来看待数组。一般来说，评价一个存储结构，不仅仅要考虑它访问其内部元素的性能，也要从，增添、插入、删除等几个方面来综合考虑。
首先，我们来看看增添的情况。
下图中，数组b中有10个元素。如果增添一个元素，新元素会被放在其当前末尾元素的后一个空闲空间内，此时增添成功（但是我不建议这么做）。
我们再来看看数组a。数组a有4个元素，要增加一个元素的话，需要在其末尾的后一个空间内存储新数据。但是这个空间暂时被其他程序占用了，无法增加新数据。怎么办？
方法1，将新数据放在之后的任意一个空闲空间内。如果这样做，就会导致数组的随机访问特性遭到破环。也就是说，你将无法通过数组下标来获取新增数据的值。
方法2，重新申请一片包含连续5个空闲空间的内存区域，将原来的数组和新增数据复制过来，完成后再释放原空间。这看似是一个比较好的解决方案，但是考虑一个极端情况，如果内存中不存在这样的连续的5个存储空间，那么就无法向数组中增添新的元素。
那究竟怎么解决呢？通常的编程惯例，我们会申请足够大的数组空间来处理。比如我们大约需要50个存储空间，我们可以定义的时候申请60个、70个甚至更多，从而留下向数组增添数据的的空间。不过，这样的方法自然免不了对空间的浪费。
其次，让我们来看一看数组的插入。如果要将数据插入到数组中间的某一位置，那么为了避免新数据将旧数据覆盖，则需要插入位置及其之后的元素统一向后移动一位。移动一位这个操作，在数据量小的时候几乎微不足道，但是当数据量过于庞大时，却是一件极其巨大的工作。除此以外，如果数组已满，那么又要重新申请空间，复制，插入，无疑降低了处理效率。
最后，一起来看看数组中的删除。为了保证数组可“随机访问”的特性，将数据从数组中删除这个操作也需要移动元素。这里移动元素虽说不可能出现“数组已满，需重新申请空间”的情况，但移动元素总会花费时间。
综合以上几点，数组并不是完美无缺的，它也存在缺点，比如在数组空间已满时，增添元素可能会操作失败；插入和删除都需要移动元素，且所花费的时间会随着数组的大小线性增长（用“大O”来描述其时间复杂度便是 \(O(N)\) ）。
针对的这些问题，有人便设计出链表这个新的存储结构。与数组不同，链表是分散存储的，从而可以充分利用内存中“碎片化”的存储区域。链表中的数据分散在内存中不同的地方，如何将他们联系起来呢？设计者给出如下的方案：
每一个链表的元素单元除了存储的数据本身，再开辟一个空间用于存储下一个元素单元的地址，从而将他们连成一个整体。这也是“链表”名字的由来。
接下来，我们和对数组的分析一样，对链表的读取、增添、插入、删除做一个简单的分析。
首先，是对链表任意元素的访问。链表是分散存储的，每一个元素单元的地址由它上一个元素单元决定。因而，链表对元素的访问只能从第一个开始，逐一访问。这就给访问链表中的任意元素造成了极大的困难。随着链表规模的增大，其访问时间也在线性增长，所以链表访问任意一个元素的时间复杂度为 \(O ( N )\) 。
其次，我们来看一看链表的增添操作。增添操作对于链表来说，十分简单。只需申请一个元素单元节点，将此节点的地址与链表末尾节点连接起来即可，无论链表规模有多大，该操作都在常数时间内完成，因而链表增添操作的时间复杂度为 \(O(1)\) 。
接着，我们来分析一下链表的插入操作。相较于数组，链表的插入不需要移动元素，只需申请一个新节点，将它和待插入位置的前后节点连接起来即可。其操作时间也是常数时间，时间复杂度也就是 \(O(1)\) 。
最后，便是对链表的删除的分析。想要删除一个元素，只需将它前一个节点和待删除节点连接起来，再将该元素节点空间释放即可。其时间复杂度为 \(O(1)\) 。
通过以上的探索，我们发现数组和链表各有优劣。那么，究竟如何选取合适的存储结构呢？我认为，要关注问题中对数据存储的要求，选择能发挥存储结构最大优势的那一个。比如，你的程序需要大量的随机访问一个集合中的元素，那么选择数组就OK；如果你的程序存在大量的插入、删除，那么链表会很有效率。
然而，现实中的问题都不是那么理想化。对数据的存储结构，既要求它能够提供随机访问的功能，又要在插入、删除方面具有极高的效率。有人为了解决这个问题，给出如下的数组和链表的混合结构。
尝试自己分析一下这种存储结构在插入、删除、随机访问等方面的效率，看看它是否比数组和链表更加优异。
在文章的最后，我们按照惯例，将本文的要点总结一下：
- 数组作为一种存储结构，提供了随机访问的功能，可以方便地、快速地通过数组下标访问数组中任意的元素。但是，数组并不是完美无缺的，它在很多方面（增加、插入、删除）表现的并不理想。
- 为了解决数组在实际应用中存在的问题，链表应运而生。链表在增加、插入、删除方面表现的非常优秀，但在访问其中的元素的情况下，表现的并不出色。
- 对比存储结构的方式可以从随机访问、插入、删除等方面分析
- 选择合适的存储结构，关键是在运用到某一情境时，该存储结构的优点能够最大化。
- 尝试将基本的存储结构混合（这种结构称作混合结构【Hybird Structure】），各自取长补短，也许会达到一个比较好的效果。
- 数组和链表在几种情况下的时间复杂度对比：
| 操作 | 数组 | 链表 |
|---|---|---|
| 访问 | O（1） | O（N） |
| 插入 | O（N） | O（1） |
| 删除 | O（N） | O（1） |