从最最最最简单的数据结构开始:数组和链表
在实际运用中,不同编程语言对于同一理论性数据结构的实现可能有所不同。在我们后面具体编程的过程中,用到的实践性数据结构和理论性数据结构也有可能不同。
本章里讲的数组和链表,是理论上的数据结构,我们关注的是逻辑层面的数据组织方式和其上操作的运行方式。
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 相同之处
数组和单向链表有许多共性:
- 在数组或链表中,都有一些固定的“位置”,其中的数据——被称作元素——每个占据一个独立的位置。
- 数组和单向链表中的元素都是从前到后一个挨着一个,排成一队:
- 除了首尾,每一个元素都有且仅有两个“邻居”——前邻居和后邻居;
- 首元素只有一个后邻居,尾元素只有一个前邻居;
- 每个元素的“地位”都是平等的,只有相对位置的前后差异,没有从属关系。
无论数组还是单向链表,只要求所有元素都要排成一列,每个元素不是在其他元素之前,就是在其他元素之后。
而不要求内部的元素一定从前到后按某个顺序排列。其中元素可以是有序的,也可以是无序的。
也就是说,假设有一个数字元素组成的数组或者单向链表,里面每一个数字一定在另一个数字的前面或者后面,但是从头到尾的数字不一定非要越来越大或者越来越小,完全可以先大再小或者先小再大。
2.1.4 不同之处
数组和单向链表的不同之处也很明显。
一排“盒子”从出现的那一刻开始,这一排里面有多少个盒子单位就已经确定了,此后单位的数量不能加也不能减。
而一列“火车”的车厢之间则是由锁链连接在一起的,刚开始的时候可以只有一个车头,然后再把一个个车厢用锁链连上去。如果想卸载其中一个车厢,就解开该车厢前后的锁链,把这节车厢移除后再将其前后邻居连起来。
数组和链表最基本的区别,是静态和动态的区别。
它们的符号化表示也很形象地体现了这一点——
- 数组:

- 链表:

是不是看起来很像排盒和火车?
数组和链表的不同之处当然不止这些,我们下面分别来看看这两种数据结构。
2.1.5 访问(读)和更新(写)
通过对它们的类比和对比可见,如果我们有一个数据序列,对其只是需要进行访问(读取操作),那么选择数组合适,通过下标我们一下就可以找到要找的元素。
比如:
在一个长度为 10000 的数组中找第 965 个元素,我们直接用这个元素的下标964就可以访问到该元素了。
但如果是在一个单向链表中找地 965 个元素,则需要从头节点开始,向后顺序访问 965 次,才能找到。
但是,如果我们需要在序列中添加新元素或者删除旧元素(更新操作),就是链表方便了。
如果一个数组的所有“空位”都已经被占满,那就不能再加入新的元素,除非把原有的某个元素“扔掉”。
链表则不受限制,在任意位置都可以断开相邻的两个节点的连接,插入一个新节点,删除节点亦然。
- 插入节点 E:

- 删除节点 C:

为什么人们要设计两个这么别扭的数据结构,非都要有“缺陷”不可?为什么就不能设计一个既可以方便读取,又方便插入删除的数据结构?
这是因为,数据结构的设计并非天马行空虚构出来的,而是要结合计算机硬件的限制考虑。具体是怎样的限制呢?我们下章再讲。
欢迎关注我公众号:AI悦创,有更多更好玩的等你发现!
公众号:AI悦创【二维码】

AI悦创·编程一对一
AI悦创·推出辅导班啦,包括「Python 语言辅导班、C++ 辅导班、java 辅导班、算法/数据结构辅导班、少儿编程、pygame 游戏开发」,全部都是一对一教学:一对一辅导 + 一对一答疑 + 布置作业 + 项目实践等。当然,还有线下线上摄影课程、Photoshop、Premiere 一对一教学、QQ、微信在线,随时响应!微信:Jiabcdefh
C++ 信息奥赛题解,长期更新!长期招收一对一中小学信息奥赛集训,莆田、厦门地区有机会线下上门,其他地区线上。微信:Jiabcdefh
方法一:QQ
方法二:微信:Jiabcdefh
