Day 12 ：阵列(array)与链结串列(linked list)

讨论过这麽多种演算法之後，会发现操作时常常会使用阵列或是某些资料结构。资料结构是指电脑中管理资料的特定方式，有助於资料的运用，选择适合的结构也可以增进演算法效率。

接下来几回会讨论几种资料结构以及它们的特性和适合的情境。

阵列与链结串列

我们学习程序最早接触的、每天都会操作的资料结构，可能就是阵列。阵列通常是由相同类型元素组成的资料集合。每当使用阵列，阵列中的元素就会被存在连续的记忆体中，所以我们可以用索引(index)来知道元素的储存位址。

链结串列是一种线性资料结构，其中的元素并不会储存在连续的记忆体中。链结串列的元素被称作节点(node)，以最简单的结构来说，每一个节点都会包含储存的值，以及下一个节点的位址(reference)。这样一来，节点未必会在相连的位址，所以我们必须依循节点的顺序才能存取特定节点。

关於两种结构储存方式的差异，Grokking Algorithms这本书里提供了蛮好懂得比喻。书中提到这就像去电影院看电影，阵列就像是一群朋友坚持座位要连在一起，所以一定要有至少跟人数一样多的相连位置才有办法买到票；链结串列就像是一群朋友接受分开坐，所以只要电影院内有足够位子就可以坐进去。

所以当我们在选择要使用阵列或链结串列，可以考虑它们的特性会如何影响特定操作的时间。

新增与删除

如果建立一个购物清单，可能随时需要在资料中插入或删除项目。

使用阵列的话，插入或删除元素成本会比较高。如果与阵列相邻的记忆体已有别的资料，在插入新的元素时就必须将整个阵列移到可以容纳新阵列的记忆体位址。解决这个问题的一种方式，是先将长度定在资料量可能的上限，但这麽做往往浪费更多记忆体。而删除虽然没有记忆体不够的问题，可是删除一个元素，代表後面的所有元素都要往前移，所以在阵列中不管是插入或删除元素，最坏情况的执行时间都是O(n)。

如果换成使用链结串列，插入或删除元素都相对简单，在已知节点位址的情况下，插入或删除都只需要O(1)，因为只需要改变节点指向的位址即可。

存取资料

如果一份资料的大小相对固定，但常常要修改资料，我们会需要能够快速找到特定资料的位址。

这时候阵列的索引就可以实现随机存取(random access)，让我们以O(1)存取任意的元素。但链结串列就只能够进行循序存取(sequential access)，也就是只能够线性地从第一个节点知道第二个节点的位址，再从第二个点知道第三个节点的位址...所以执行时间为O(n)。

综上所述，阵列的优势在於：

• 可以随机存取，资料调用或修改速度较快，因此执行一些需要操作特定元素的演算法会更有效率(例如像二分搜寻要找到阵列的中间元素，或快速排序需要随机的基准值)。

• 以同样长度的资料来说，阵列需要的空间更少，因为不需要储存每个元素的位址。

链结串列的优势则在於：

• 不需要连续的记忆体让链结串列的长度有弹性，所以适合不确定资料大小，或资料大小会频繁变动的情境，可以在执行时随着资料增加而逐步增加。

• 也因为上述原因，链结串列较易於插入或删除元素。