一直搞不懂的数据结构，原来这么简单啊！（文末还有福利）

现实世界由万事万物构成，而计算机能够处理，只有数据。说得更直接一点，计算机能够处理的其实都是数字。因此，当我们用计算机来协助处理日常事物的时候，首先要做的一件事就是数字化。

虽然在实践中，通常存储在计算机存储设备上的数字化数据是二进制形式的。但严格来说，任何把模拟源转换为任意类型数字格式的过程，都可以叫做数字化。

数字化指将信息转换成数字格式的过程。具体而言，就是把一个物体，图像，声音，文本或者信号转换为一系列数字的集合：

• 一张图片的数字化是将其被分割成若干的像素，每个像素用 R（red，红色）G（green，绿色）B（blue，蓝色）三种颜色分量对应的三个 0-255 的值来表示；

• 一段声音的数字化则是将记录下来的模拟声波经由傅里叶变换转化为若干三角函数的叠加；

• 文字的数字化是针对不同字符体系进行编码，将某一字符转化为一个特定的数字“号码”；

• ……

接下来，我们将学习三种常用的数据结构：数组、链表，以及冯诺依曼结构。

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

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

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

数据结构的定义

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

数组

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

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

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

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

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

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

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

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

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

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

链表

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

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

非循环链表

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

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

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

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

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

循环链表

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

• 单向循环链表：

• 双向循环链表：

更复杂的链表

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

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

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

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

直观理解数据结构

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

数组 & 单向链表

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

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

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

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

直观一维数组

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

• 盒子的个数(数组的大小)在创建的时候确定，位置也在创建时固定——盒子之间的相互位置不会改变；

• 每个盒子上都有标号——根据盒子上的标号（index，又叫索引、下标）可以直接找到某一个盒子；

• 每个盒子里面可以装东西（元素），也可以是空的；

• 空着的盒子可以把东西放进去，有东西的盒子可以把东西拿出来；

• 如果要把一个盒子里原有的东西换成新的，需要：

• • 把原有的拿出来；

  • 把新的放进去。

直观单向链表

单向链表就像一列火车：

• 在被创建出来之后，长度（车厢的个数）是可以改变的；

• 每个车厢都有一根“链”连接一个（后）或者两个（前和后）邻居；

• 火车中的车厢就是容纳元素的单位空间，这些空间：

• • 没有标号——访问其中一节车厢，必须要从车头（或者车尾）开始，依次向后（或向前）顺序访问，不能用标号直接找到；

  • 原有的车厢可以“卸掉”，新的车厢可以加上 ——车厢之间的相对位置可以改变；

• 车头和车尾与头尾之间的车厢不同；

• 车厢里一般都会有东西，没有空置的车厢——如果有哪节车厢里的货（数据）被清空了，车厢也就没用了，直接卸掉它就可以了。

相同之处

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

1. 在数组或链表中，都有一些固定的“位置”，其中的数据——被称作元素——每个占据一个独立的位置。

2. 数组和单向链表中的元素都是从前到后一个挨着一个，排成一队：

• 除了首尾，每一个元素都有且仅有两个“邻居”——前邻居和后邻居；

• 首元素只有一个后邻居，尾元素只有一个前邻居；

• 每个元素的“地位”都是平等的，只有相对位置的前后差异，没有从属关系。

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

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

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

不同之处

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

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

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

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

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

• 数组：

• 链表：

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

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

访问（读）和更新（写）

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

比如：

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

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

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

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

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

• 插入节点 E：

• 删除节点 C：

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

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

计算机是咋运行的：冯诺依曼结构

以约翰·冯·诺伊曼为代表的一批数学家、计算机科学家在使用 ENIAC 和 Mark I 等计算机时发现了存储的重要性。

1945 年 6 月 30 日，ENIAC 机密计划的安全官戈德斯坦发表了一篇由冯·诺伊曼撰写的 101 页报告，史称《EDVAC 报告书的第一份草案》。其中提出了“冯·诺伊曼结构（Von Neumann architecture）”这个术语。

冯·诺伊曼结构一种设计计算机的概念结构，具体见下图：

冯·诺依曼结构的要点主要包括：

1. 计算机硬件由运算器、控制器、存储器、输入设备和输出设备五大部分组成，其中运算器和控制器组成了中心处理单元（CPU）；

2. 指令——指令是单个的 CPU 操作，一款 CPU 能够进行哪些操作是在设计时就确定了的，和数据都以二进制编码；

3. 存储器中既存储数据又存储指令。

这一结构将存储设备与处理单元（运算器、控制器）分开，依此结构设计出的计算机又称存储程序型计算机。

存储程序型计算机改变了若要改变程序，就要改变计算机线路的情况。它将运算操作转化成一串程序指令，又将程序指令当成一种特别类型的数据和其他数据一起存储在存储器中。这样，一台存储程序型计算机就可以像变更数据一样改变程序了。

存储空间的地址和内容

存储空间

存储器在逻辑上是一个空间，这个空间被叫做存储空间。

存储空间被分为若干存储单元，每个存储单元又分为两个部分：

• 地址：每个存储单元对应的序号，标识内容在存储空间中位置的编码；

• 内容：存储单元中存放的信息。

无论地址还是内容均以二进制的形式表示：

换言之，存储空间线性编址，按地址访问，存储在其中的每一条指令或数据，都是空间里存放的内容，它们都拥有自己的地址。

类比仓库

我们可以将存储空间类比成一个仓库，里面有许多的货架，相当于一个个的存储单元，每个货架都有自己的编号（存储单元地址），货架上还会有相应的货物（存储单元的内容），就像下面这样：

当我们想要拿到其中某一个货物的时候，我们首先要知道该货物所在的货架编号，然后根据编号找到货架，从上面把货物取下来。比如：告诉我们去拿 001 号货架上的货物，我们就去把小红盒拿下来就是了。

反之放置货物，就是将货物放到对应编号的货架上去。

总结一下：

• 在这些货架上的“货物”，可能是指令，也可能是数据；

• “拿货”就是读操作，而“放置”则对应写操作；

• 指令和数据一样可以被读、被写、被修改（用新“货物”替代旧“货物”）；变更指令或者数据，都只要修改存储空间内的内容就好了，无须变更硬件设置。

一条指令是怎么被执行的？

计算机运行的过程，就是一条条执行指令的过程。

由运算器和控制器组成的 CPU，是计算机的“执行机构”。可以类比于我们人脑的神经中枢，“思维”专用。CPU 负责顺序执行程序的每一条指令。

每一条指令的执行过程，大致是这样的：

1. 取指令（Instruction Fetch，IF）：根据指令地址，从存储器里取出相应指令；

2. 指令解码（Instruction Decode，ID）：分析指令的操作类型（读/写操作，输入/输出操作，或者算术逻辑运算操作等）和获取操作数的方法；

3. 执行（Execute，EX）：完成指令功能（例如控制运算器对操作数进行运算），并控制数据在 CPU、存储器和输入/输出设备之间流动；

4. 写回（Writeback，WB）：将运算结果写入 CPU 或存储器。

一个完整的指令执行过程所需要的时间，称作一个指令周期。

在一条指令被执行完毕，结果数据写回之后，若无意外事件（如结果溢出等）发生，则计算机根据程序的控制结构（顺序结构、条件结构、循环结构）确定下一步要执行的指令，开始新一轮执行指令的循环。

冯诺依曼结构的直观解释

我们打个形象的比于：冯诺依曼结构的计算机就像一家餐厅——

【1】 存储器相当于仓库：

仓库（存储空间）里的货架都有编号，货架上，要么放着食谱（指令），要么放着食材（数据）。

【2】 CPU 则相当于厨师（控制器）和炊具（运算器）：

【3】 执行一条指令的过程就像做一道菜：

1.从仓库里拿食谱——取指令；

2.阅读食谱，搞清楚要烹调的方式和要使用的食材——指令解码；

3.根据食谱拿食材，并烹饪制作——执行；

4.把做好的菜放回到货架上——回写。

这道菜做完，再去做下一道菜。

【4】 程序更新类似于换菜单：

假设，今天这顿饭总共做了两道菜：炒萝卜和烤鱼。

明天客人不想吃烤鱼了，想吃蒸鱼，那只要把仓库中“第 1 格“的食谱换成”蒸“就可以了，餐厅的所有硬件，包括厨师，都不会受影响，其他位置的食谱和食材也不会受影响。

这就是冯诺依曼结构的直观解释。

冯诺依曼结构的应用

现代计算机，大部分都基于冯诺依曼结构。

下图是一台普通 PC 的硬件结构图，我们可以来看一下其中不同部件和冯诺伊曼结构的对应：

• 红框里的 CPU——运算器、控制器；

• 黄框里的内存条——存储器；

• 绿框里的键盘接口和显卡——输入设备和输出设备。

这是一个典型的冯诺依曼结构。

冯·诺依曼结构的瓶颈

导致瓶颈的原因

冯·诺依曼结构在运行中会导致一个瓶颈，叫做冯·诺伊曼瓶颈（von Neumann bottleneck），其产生原因是现实当中不同计算机部件的客观性能：

• CPU 的处理速度特别快

• CPU 与存储器之间的数据传输速率与存储器的容量相比起来相当小

这个瓶颈的表现就是：CPU 的高效工作与低速的数据传输之间不平衡，CPU 不得不在数据输入输出的时候闲置，因而严重影响了整体效率。

通过直观例子理解瓶颈

还用餐厅的例子来说明：

我们的 Hello Kitty 厨师是个超级快手，她的平底锅也是厨界神奇，任何食材无论煎炒烹炸全都能一秒钟完成：

偏偏负责给她拿食谱和食材的助手是个慢吞吞：

每次往返一趟厨房和仓库得半个小时，而且能拿的东西还特别少，每次只能拿 50g 以下的东西，食谱还可以一次拿完，要是拿食材，得往返个百八十回的。

这种情况下，Hello Kitty 只能整天闲着，慢吞吞先生却累得要死。这个问题会越来越严重，而餐厅的整体运行效率则受限于慢吞吞先生的工作效率。

缓解瓶颈的办法

针对冯诺依曼瓶颈，人们想了很多办法来缓解它，这些法子包括：

• 在 CPU 与存储器之间加入高速缓存;

• 采用分支预测（branch prediction）算法;

• 通过编程方式的改变（现代的函数式编程以及面向对象编程），在宏观上减少将大量数值从存储器搬入搬出的操作；

• 等等

这些方法的确大幅缓解了瓶颈问题。

哈佛结构

上面我们提到了一台和 ENIAC 同时期的电子计算机 Mark I，它虽然不如 ENIAC 那样通用，却是美国第一部大尺度自动数位电脑，由 IBM 制造出来之后被哈佛大学接管。

它将指令和数据区别对待，将它们分开存储，这种结构被称为 “哈佛结构（Harvard architecture）”。

因为指令和数据分别放在不同的存储器中，可以在同时读取两者，因此哈佛结构相对冯·诺依曼结构，效率会更高。

但是这种高效的代价很大：

• 哈佛结构比冯诺依曼结构要复杂得多；

• 在动态加载程序时，哈佛结构需要先将静态程序代码作为数据读入数据存储器，再将其传输到指令存储器中去——这样既增加了存储负担又增加了传输负担，还使得过程非常复杂。

过高的复杂度限制了哈佛结构的推广。

现在，我们日常使用的计算机，在整体体系结构上基本上都采用冯诺依曼结构。不过许多 CPU 内核，会采取类哈佛结构的设计，在 CPU 内的缓存中区分指令缓存和数据缓存。这也可以说是在现实应用中冯诺依曼结构和哈佛结构的一种折中。

---

即日起至 5 月 19 日，专栏《编程算法同步学》限时特惠 ￥49 ￥69。现在订阅，不仅可以加入专属读者群，还可以获赠 《亲子算法课》演示 PPT (9 讲) 一份！