须弥零一

认识数据结构之【链表】

上篇文章介绍了数组，并且在文章末尾也简单的提了一句，有个东西和数组比较像 —— 链表。那么今天就接着来简单说说链表，错过往期文章的朋友可以点击下面列表的链接查阅。

认识数据结构系列往期文章：

回顾数组元素的访问

上期文章中介绍了数组是一组相同类型的元素集合，并且这些元素在内存中是按照下标的先后顺序连续存放的。我们也已经知道，比如要访问数组 name 的第5个元素，我们可以使用下标来获取，例如 name[4]。

那么往微观的角度看看，计算机是怎么通过这个下标来获取我们想要的元素呢？OK！咱们看以下的代码片段：

#include <stdio.h>int main(){    unsigned int numbers[] = {100, 200, 300, 400, 500};    printf("单个unsigned int所占字节数：%d\n", sizeof(unsigned int));    printf("numbers数组所占字节数：%d\n", sizeof(numbers));    printf("数组numbers的元素个数：%d\n\n", sizeof(numbers) / sizeof(unsigned int));    printf("numbers的指针地址：0x%x\n\n", &numbers);    printf("元素numbers[0]的指针地址：0x%x\n", &numbers[0]);    printf("元素numbers[1]的指针地址：0x%x\n", &numbers[1]);    printf("元素numbers[2]的指针地址：0x%x\n", &numbers[2]);    printf("元素numbers[3]的指针地址：0x%x\n", &numbers[3]);    printf("元素numbers[4]的指针地址：0x%x\n", &numbers[4]);       return 0;}

上面代码的某一次执行结果如下：

单个unsigned int所占字节数：4numbers数组所占字节数：20数组numbers的元素个数：5numbers的指针地址：0xc48df320元素numbers[0]的指针地址：0xc48df320元素numbers[1]的指针地址：0xc48df324元素numbers[2]的指针地址：0xc48df328元素numbers[3]的指针地址：0xc48df32c元素numbers[4]的指针地址：0xc48df330

注：您自己运行的结果地址应该和上面是不一样的。

不管你自己的代码运行了几次，你如果观察仔细的话，应该已经看出来规律了：

•每个 unsigned int 占四个字节•numbers 数组所占字节数 = 单个 unsigned int 所占字节 * numbers 数组元素个数•数组 numbers 的内存地址和其第一个元素 numbers[0] 的地址相同•numbers 每两个相邻元素的地址相差一个 unsigned int 的长度

根据上面的运行结果可知，numbers 数组在内存中应该是如下图的样子：

综上所述，因为数组是相同类型数据的集合在内存中顺序存放的，并且我们已知某一个数组变量的内存指针地址，则第N个元素的指针地址 = 数组的指针地址 + 单个元素所占的字节数 * N 。知道了第N个元素的指针地址，则向后获取单个元素所占字节的长度，就获取了这个元素的值。

以上面的示例，如果我们想获取 numbers[2] 的值，则可以通过如下方式获取：

numbers指针地址0xc48df320 + 单个unsigned int的长度4 * 2 = 0xc48df320 + 8 = 0xc48df328
内存 [0xc48df328 , 0xc48df32c) 之间的数据就是 number[2] 的值

OK！数组通过下标取值就复习到这了，下面看看今天的主角——链表。

链表

链表的定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表的特点

链表相比于数组的顺序结构，操作复杂。但由于链表不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比数组快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而数组相应的时间复杂度是O(1)。

链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。

链表的分类

线性链表（单链表）和非线性链表

•由分别表示结点1，结点2，…，结点N的N个结点依次相链构成的链表，称为线性表的链式存储表示。由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表。•非线性的链表，可以参见相关的其他数据结构，例如树、图。对比线性链表的定义可知，非线性链表的每个结点可能会包含多个指针域。

双向链表

双向链表其实是单链表的改进。

当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。

在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。

循环链表

循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。

循环链表的运算与单链表的运算基本一致。所不同的有以下几点：

1.在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。2.在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。

循环链表的举例：约瑟夫还问题，感兴趣的朋友可以自己查找相关资料了解一下。

问题来源：
据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

链表的操作

遍历

•对于线性链表的遍历很容易。因为每个结点上有指向下一个结点的指针域，通过指针可以很容易的遍历完整个链表。•对于非线性链表的遍历稍微复杂一些，因为每个结点指向下一个结点的指针域有多个，这些多个指针域的遍历顺序不一样则遍历出来的结果也不一样。此处不多说了，关于树的遍历可以点击文末关于树的文章链接查看•对于循环链表来说，需要注意的是如何决定终止条件，而使遍历不会变成一个死循环

插入结点

链表上插入结点的操作实际上就是操作指针域的。比如要在 结点A 和 结点C 之间插入 结点B，则仅仅需要把 结点A 的指针域指向 结点B，并且把 结点B 的指针域指向 结点C 即可。

删除结点

删除结点同插入结点一样也是对指针域的操作。比如要将 A -> B -> C 这样的链表中的 结点B 删除仅仅需要将 结点A 的指针域指向 结点C 即可。结点B 指向 结点C 的指针域可以根据你的需要来决定是否删除，不管删除与否这都不影响在原来的链表中已经移除了结点B。

最后

本篇文章从介绍数组的取值方式切入，对比介绍了链表的一些基本知识。但是对于链表的操作并没有给出具体的示例，但这也是认识数据结构系列的宗旨：不过多的添加示例，希望通过抽象的模型来理解数据结构。感兴趣的你可以用自己擅长的编程语言来实际实现一下如何操作链表，这样你会记得更牢固，理解的更深入。

大家下期见~(●ˇ∀ˇ●)

---- END ----

往期文章：

•认识数据结构之【树】•认识数据结构之【数组】

欢迎关注我的公众号“须弥零一”，原创技术文章第一时间推送。