【梦幻联动】链表与双链表：如何才能最快地从队伍中找出一个人？

欢迎收看我和站长第3次梦幻联动！这次我来讲关于数据结构的基础概念，对面站长放代码。（希望大家投4个币支持）

那么大家不要怕——数据结构这个东西，我会尽量讲得通俗易懂一些。（有一说一啊，这玩意儿和算法没啥关系，只是个工具，而且也不会让你入坑计算机）

那么文如其名，我今天就从链表和双链表的大坑中跳出来，让各位跳过这个大坑。

 

先引一个笑话，来自《How to Ace Calculus: The Streetwise Guide》：

话说在一个不便透露校名的某大学里，举办了一系列的演讲，由学校的教授们主讲，对象是校外普通老百姓。这个系列显然非常受欢迎，举办了好多年。美中不足的是，自从开办以来，未曾有数学系的教授上过台，原因是主办方害怕数学家无法和缺乏数学底子的大众做良性沟通。但是这个缺陷总不免招人非议，在舆论的压力下，主办人终于邀请了一位数学教授，安排好演讲日期，并且特别提醒他说：“请注意！来听讲的人都是最普通的老百姓，他们连微积分课都没上过，所以不知道什么是导数和积分。”

“没问题。”教授回应道，“我懂你的意思。”

到了演讲那天，主办人作过例行介绍之后，教授走到讲台上，一开口就说：“诸位女士先生，在下我今天要讲的题目，是如何求f(x)在a到b这段区间上求定积分。”坐在第一排的主办人闻言大惊失色，而整个大教室里的听众个个一脸惊讶。教授望了主办人一眼，叫他放心，然后继续说：“在座如果有任何人对定积分不熟悉，不要紧，你只要把定积分想成是一个‘黎曼和’的极限……”

（注意粗体：是主办人没讲清楚，还是教授理解有问题？）

我希望我不像那个教授一样——虽然主办人并没有跟我说过要有多简单。因此我尽量往简单里讲。

 

废话少说，我们开始。说到链表，（用过Scratch的）大家一定不陌生，毕竟人家就有链表模块。但是大家不是把它当显示器用，就是把它当输入框用——只有少数人用在了点子上。我们必须把链表和另一个结构——顺序表，进行比较。

通俗来讲，顺序表就是我们平时所说的列表——也就是整整齐齐排成列的表格，而链表就是每一项用“链”连起来的不整齐的表格。大概长这样：

其中，null的意思是“无”。

（图片来自CSDN博客文章）

 

或者这样更贴切一点（我自己画的）

 

我们假设Bob Voyager在L中学的某处，而L中学的走廊里有一支非常整齐的队伍（整齐到你光靠测量距离就知道一个人排在第几个）。

如果我们只是想确认这支队伍的第14个人是不是Bob Voyager，我们只需要将第14个人所在的位置找出来，再看一下他是不是Bob Voyager就行了。

那么假如我们想知道Bob Voyager是否在队伍里，假如在的话又在第几个位置：我们就需要从头至尾报出名字，要是报的人中有Bob Voyager，数一下这个人是第几个报数的即可。

我们想把Andy Zhou放到队伍的18号位，这时我们要让18号位的人到19号位，19号位的人往后再挪一个，一个一个挪下去——显然后面重排了一次队伍，效率很低。

上面的整齐的队伍，也就是所谓的顺序表，顺序表的空间利用率高（显然排得密一些，而且也不会浪费别的队伍的空间），而且访问单个项（我们称为元素）的效率更高。

 

后来我们找到了教导处的老师，他调监控抓住了Bob Voyager，并且把整个校园弄得惶恐不安（原因是他到处找Bob），现在，队伍里的人都到了操场上。虽然队伍不见了，但是由于刚才排队的印象过于深刻，所有人都记住了当时排在自己前面的人是谁，并且有能力找到他。

我们把Bob Voyager交给了体育老师，现在体育老师想知道Andy Zhou是否在队伍的第18个位置。

那么他显然不能靠量了——队伍已经成了一盘散沙，不过体育老师的经验告诉他，只要知道队伍的1号是谁，问题就好办了。

1号将2号的名字喊出来，于是2号听到后喊出3号的名字……每个人只要听到自己的名字，就喊出下一个人的名字。假如第17个人喊出的名字不是Andy Zhou，那么说明Andy不在18号位。这个过程比上面繁琐的多。

结果Andy果真不在，我们要将Andy找出来，只能继续让他们报名字，结果终于找到了Andy。

现在我们要将Bob放在离体育老师最近的位置，于是体育老师抓来了离他最近的Wind，问他：“你后面的人是谁？”

Wind答道：“Taylorswiftie。”

于是体育老师对wind说：“以后你后面的人是Bob。”再对Bob说：“你后面的人是Taylorswiftie。”

显然这个队伍还没垮，但是效率很高。

上面的队伍就是链表。链表像一盘散沙，每个元素的位置也是随机的。但是访问单个项没有顺序表快，然而，要是我们想插入或删除一个元素，只要更改相关元素指向的下一项（我们称为指针）就可以了。

 

列表和链表的共同点和主要区别在哪里？

• 列表有一段专属的申请空间，与链表同样储存在内存条中。
• 链表的空间随机且自由。
• 链表的空间虽然自由，但是随机性很大——会产生不完整的空内存，有时列表太长，无法储存，所以这俩在一起很难弄。
• 列表容易溢出。
• 链表有指针，六、七个链表放在一起也不会乱。
• 它们都属于线性表。

 

把上面的例子转成抽象的语言，大概就是这样：

我们定义一个数据类型，命名为节点（node），节点的定义包含以下2项：

1. 一个任何类型的值（如3, 0.5600, 'Hello World'等等）。
2. 一个指针（cursor），指向另一个节点的地址或一个空值（null）。有时，在某些语言里，我们直接指向Node或空值，这样可以通过引用第一个Node引用整个链表

也就是说，我们定义一个叫做Node的东西，它大概长这样：

Node(value: any, cursor: Node|null)

（冒号的后面表示类型，为了帮助理解，这里可能杂烩了各类语言，请不要抬杠）

那么如何串起这个链表呢？我们设有这样一种情况：

a为地址，储存了一个Node，值为1，指向空值。

b为地址，储存了另一个Node，值为2，指向地址a。

这样我们就串起了一个最简单的链表：2----1----(null)（null不用管，长度为2）。理论上，这个链表可以无限串。另外，地址的储存位置是随机的。

那么我们如何修改这个链表呢？很简单。

假如我们要将存储在地址c的Node（值为3）存储在a与b中间（我们希望弄出的链表为2----3----1----(null)），我们只需修改b与c储存的数据就行了。

我们知道，转换为一个Node类型的话，b和c分别储存着Node(2, a)和Node(3, null)。

我们修改一下，将b变成Node(2, c)，将c变成Node(3, a)。这样地址就接上了，我们做出了一条有3项的新链表——不得不说名字很贴切——松开b与a，连接b与c、c与a。

抽象来说，假如我们在任意项数的链表a中把i插入x与y之间（x在y之前），只要修改x的指针为i的地址，将i的指针修改为y的地址即可，与a没有关系。

现在我们把c从三项链表中删除，有两种方式：

1. 只改指针不删除c，这通常是临时的。
2. 更改b的指针至a，删除c，这通常是永久的。

我们不如认为，该操作是上一步的逆操作。理论上，我们需要松开c与a、b与c，连上b与a，但实际上，我们只需松开bc，连上ba即可——很简单，链子上多了几个不接东西的环，似乎没什么大不了。

等等！你可能会问：链表的节点啥都能接是吗？

没错。所以有没有Y型的链表？答案是肯定的。两个独立的链表各有一项的指针指向相同的值时，两个链表就能合并。

一个简单的例子：

地址	节点的值	指针方向
a	10	c
b	8	c
c	3	d
d	1	null

在这两个链表中，我们不难发现：a----c----d----(null)与b----c----d----(null)有两项重合

另外还有更秀的：又有一些天才在想——要是链表是个环会怎么样？（我用环造了一个环？）

地址	节点的值	指针方向
a	10	b
b	8	c
c	3	d
d	1	a

就像这样。这个链表理论上有无限项，而且最小正周期为4。

 

留给大家一个数学问题：A表从a开始，B表从m开始，下列哪个链表更长？（如果A长投2个币加收藏，B长投2个币加关注，我看看大家想法如何）

地址（A）	节点的值（A）	指针方向（A）	地址（B）	节点的值（B）	指针方向（B）
a	1	b	m	10	p
b	2	c	n	5	p
c	3	d	p	6	q
d	4	e	q	7	r
e	5	a	r	8	n

 

那么接下来有请一个更nb的东西出场：双链表！

双链表不是两条并联的链表，也不是两条串联的链表。实际上，双链表是指双向的链表，也就是说，每个节点指向前面和后面两个地址。

我们重新回到L学校的操场。我们把操场上每个人都领到走廊上，排好队，每个人记住自己前面和后面的人分别是谁。

我们顺便把Andy Zhou再次抓出来（辛苦您嘞！），交给体育老师。

不久之后，体活课开始了，同学们在做好力量练习后开始自由活动，这时我们想把Andy Zhou放进wind和taylorswiftie之间（也辛苦您二位了）。

于是我们可以告诉wind：“你后面的人换成Andy。”，再对taylorswiftie说：“你前面的人换成Andy。”

最后再告知Andy：“你后面是taylorswiftie，前面是wind，知道了吗？”于是这个双链表就又填了一项。

 

（抽象代码部分留给zhou）

 

那么前面说的奇形怪状的双链表呢？别急别急。

我们假设Admin在第一位，CXL在最后一位（辛苦二位了）。

我们想把Bob Voyager（你们都很辛苦）接在Admin和CXL之间，如法炮制，我们就弄出了环形的双链表。

 

再留给大家一个小问题：你能利用双链表弄出上海90路公交车的往返地图吗？（欢迎评论区回复）

 

（4个币更新下期）

我的分享到这里，希望大家投币、收藏、加精、关注素质四连，谢谢朋友们！

附：zhou的模块正在烘烤中，还有1个小时就要新鲜出炉了，到时一定，一定，一定要看哦！