从最最最最简单的数据结构开始：数组和链表

在实际运用中，不同编程语言对于同一理论性数据结构的实现可能有所不同。在我们后面具体编程的过程中，用到的实践性数据结构和理论性数据结构也有可能不同。

本章里讲的数组和链表，是理论上的数据结构，我们关注的是逻辑层面的数据组织方式和其上操作的运行方式。

1. 数据结构的定义

我们先来看看数组和链表的定义。

1.1 数组

在计算机科学中，数组是一种由若干元素组成的集合，每一个元素被至少一个索引（index）或者关键字（key）标识，每一个元素的位置都可以通过计算索引得到。

之所以说数组中的每一个元素至少有一个索引，是因为，一个元素还可以有两个三个或者更多的索引。因为，数组可以是1维的，也可以是 2维 3维乃至 n维的。

1 维数组，也称为线性数组，形式简单，就是一个线性的序列。2维数组看起来就会是数学中二维矩阵的形式，3维数组则会是一个数字组成的长方体。下图中包含了 1维 2维 3维三个数组：

我们这门课里会用到的只有 1维数组，所以，我们暂时不考虑 2维以上（含）的情况。

一个（1维）数组一旦被创建出来，它的长度（可容纳元素的个数）就是固定的，访问其中任意一个元素都要用到该元素的索引（又称下标）。

小贴士：此后，在本课中只要提到的“数组”一词，指的就是1维数组。

下图这个数组的长度是 10，也就是说它有 10 个位置可以用来容纳元素。这十个位置分别对应 0-9 这 10 个下标。

由图可见，下标为0的位置上的元素是数字 10，下标为 1 的位置上的元素是 20……

通过这个例子我们看到，数组的下标是从0开始计数的。

实际上，从 0 开始并不是唯一的元素索引方法，数组的第一个元素下标也可以从 1 开始，或者从 n（自由选择的一个数字）开始。

实践中，一个数组的首元素索引到底从几开始和编程语言有关系，但是因为现在主流的编程语言（C/C++， Java，包括我们用的 Python 等）都是从 0 开始的，所以，我们只考虑从 0 开始索引元素的数组即可。

1.2 链表

链表（Linked list）是一种线性表，链表通常由一连串节点组成，每个节点包含数据和一个或两个用来指向上一个/或下一个节点的位置的链接（links）。

链表又可以分为非循环链表和循环链表：

1.2.1 非循环链表

非循环链表是一种由若干元素组成的有限序列，存在一个唯一没有前驱的（头）元素；存在一个唯一的没有后继的（尾）元素；此外，每一个元素均有一个直接前驱和一个直接后继元素。

这类链表中最简单的一种是单向非循环链表：

单向非循环链表由若干节点构成，每个节点包含两个域：一个信息域和一个连接域，前者用于承载数据元素；后者内则保存着一个链接，这个链接指向列表中的下一个节点，而最后一个节点的链接则指向一个空值。

双向非循环链表，是一种比单向链表复杂的结构：

同样是由若干节点构成，每个节点有一个信息域和两个连接域。因此也就有两个链接：一个指向前一个节点（头节点的这个链接指向空值）；而另一个指向后一个节点（尾节点的这个链接指向空值）。

1.2.2 循环链表

有些链表的头节点和尾节点连在一起，这种方式在单向和双向链表中皆可实现，从任何一个节点开始都可以走遍链表的每一个节点，这种“无头无尾”的链表叫做循环链表(Circularly Linked List)，它也有单向和双向之分：

• 单向循环链表：

• 双向循环链表：

1.2.3 更复杂的链表

其实，链表的结构还可以很复杂，比如多向链表，每个节点可以包括两个以上的连接域，这些连接可以将链表中的元素按任意顺序组合。

不过，虽然可以很复杂，但却是最简单的最常用。在大多数情况下，我们用的都是单向非循环链表。

NOTE：因为一般常用的链表都是非循环的，因此本课后续部分，当我们不特意指明是循环链表，而仅说“链表”时，指的就是非循环链表。

故而，单项非循环链表我们称为单向链表(Singly Linked List)，双向非循环链表称为双向链表(Doubly Linked List)，

2. 直观理解数据结构

上面的定义部分是不是看起来有点晕？没关系，下面我们就从直观角度，来解释一下。

2.1 数组 & 单向链表

数组和单向链表是我们最常用的数组和链表结构，尤其是前者，可以说是最最简单、基础，在实际中也被使用最多的数据结构了。

它们为什么这么简单又这么常用呢？因为它们是序列结构，简单来说就是把若干数据串成一串。

比如下图就可以看作一个序列，其中每个水果就是一个元素：

还记得前面小明一家算账的例子吗？那个例子就可以应用数组或者链表。

2.1.1 直观一维数组

数组就像一排连在一起的“盒子”：

• 盒子的个数(数组的大小)在创建的时候确定，位置也在创建时固定——盒子之间的相互位置不会改变；
• 每个盒子上都有标号——根据盒子上的标号（index，又叫索引、下标）可以直接找到某一个盒子；
• 每个盒子里面可以装东西（元素），也可以是空的；
• 空着的盒子可以把东西放进去，有东西的盒子可以把东西拿出来；
• 如果要把一个盒子里原有的东西换成新的，需要：
  • 把原有的拿出来；
  • 把新的放进去。

2.1.2 直观单向链表

单向链表就像一列火车：

• 在被创建出来之后，长度（车厢的个数）是可以改变的；
• 每个车厢都有一根“链”连接一个（后）或者两个（前和后）邻居；
• 火车中的车厢就是容纳元素的单位空间，这些空间：
  • 没有标号——访问其中一节车厢，必须要从车头（或者车尾）开始，依次向后（或向前）顺序访问，不能用标号直接找到；
  • 原有的车厢可以“卸掉”，新的车厢可以加上 ——车厢之间的相对位置可以改变；
• 车头和车尾与头尾之间的车厢不同；
• 车厢里一般都会有东西，没有空置的车厢——如果有哪节车厢里的货（数据）被清空了，车厢也就没用了，直接卸掉它就可以了。

2.1.3 相同之处

数组和单向链表有许多共性：

1. 在数组或链表中，都有一些固定的“位置”，其中的数据——被称作元素——每个占据一个独立的位置。
2. 数组和单向链表中的元素都是从前到后一个挨着一个，排成一队：
   1. 除了首尾，每一个元素都有且仅有两个“邻居”——前邻居和后邻居；
   2. 首元素只有一个后邻居，尾元素只有一个前邻居；
   3. 每个元素的“地位”都是平等的，只有相对位置的前后差异，没有从属关系。

无论数组还是单向链表，只要求所有元素都要排成一列，每个元素不是在其他元素之前，就是在其他元素之后。

而不要求内部的元素一定从前到后按某个顺序排列。其中元素可以是有序的，也可以是无序的。

也就是说，假设有一个数字元素组成的数组或者单向链表，里面每一个数字一定在另一个数字的前面或者后面，但是从头到尾的数字不一定非要越来越大或者越来越小，完全可以先大再小或者先小再大。

2.1.4 不同之处

数组和单向链表的不同之处也很明显。

一排“盒子”从出现的那一刻开始，这一排里面有多少个盒子单位就已经确定了，此后单位的数量不能加也不能减。

而一列“火车”的车厢之间则是由锁链连接在一起的，刚开始的时候可以只有一个车头，然后再把一个个车厢用锁链连上去。如果想卸载其中一个车厢，就解开该车厢前后的锁链，把这节车厢移除后再将其前后邻居连起来。

数组和链表最基本的区别，是静态和动态的区别。

它们的符号化表示也很形象地体现了这一点——

• 数组：

• 链表：

是不是看起来很像排盒和火车？

数组和链表的不同之处当然不止这些，我们下面分别来看看这两种数据结构。

2.1.5 访问（读）和更新（写）

通过对它们的类比和对比可见，如果我们有一个数据序列，对其只是需要进行访问（读取操作），那么选择数组合适，通过下标我们一下就可以找到要找的元素。

比如：

在一个长度为 10000 的数组中找第 965 个元素，我们直接用这个元素的下标964就可以访问到该元素了。

但如果是在一个单向链表中找地 965 个元素，则需要从头节点开始，向后顺序访问 965 次，才能找到。

但是，如果我们需要在序列中添加新元素或者删除旧元素（更新操作），就是链表方便了。

如果一个数组的所有“空位”都已经被占满，那就不能再加入新的元素，除非把原有的某个元素“扔掉”。

链表则不受限制，在任意位置都可以断开相邻的两个节点的连接，插入一个新节点，删除节点亦然。

• 插入节点 E：

• 删除节点 C：

为什么人们要设计两个这么别扭的数据结构，非都要有“缺陷”不可？为什么就不能设计一个既可以方便读取，又方便插入删除的数据结构？

这是因为，数据结构的设计并非天马行空虚构出来的，而是要结合计算机硬件的限制考虑。具体是怎样的限制呢？我们下章再讲。

欢迎关注我公众号：AI悦创，有更多更好玩的等你发现！

公众号：AI悦创【二维码】