【算法与数据结构 04】多图讲解——线性表、顺序表、链表

大家好！我是【AI 菌】。本篇文章适用于数据结构初学者，可帮助你快速理解线性表、顺序表、链表。如果想更加深入的学习 list 类的用法，可戳戳这篇实战样例讲解：数据结构——链表list（Day11）

1. 什么是线性表

之前我们已经了解过，数据结构，就是数据组织的方式。那么，线性表作为一种数据结构，它有哪些特点呢?下面我们就一起来了解下！

简单来说，线性表是 n 个数据元素的有限序列。当采用顺序存储结构时，称为顺序表；更一般地，采用链式存储结构时，称为线性链表或者链表。

所谓顺序存储结构，就如同数组一样，所有元素按照其逻辑顺序依次存储到一块连续的内存空间中。链式存储结构是通过一个个结点链接而来，存储空间可以任意安排，不需要连续。下面主要来谈谈链表~

(1) 结点

在链表中存储的数据元素也叫作结点，一个结点存储的就是一条数据记录。每个结点的结构包括两个部分：

• 数据域，存储的是具体的数据值。
• 指针域，存放的是指向下一个结点的地址。

对指针不太熟悉的同学，建议先加个餐：指针就应该这么学！

在链表的最前面，有一个头结点，头结点的指针唯一地标识该链表，头结点的头指针用来指向第一个结点。对于链表的最后一个结点（尾结点），由于在它之后没有下一个结点，因此它的指针是个空指针NULL。

(2) 链表

了解了头结点、尾结点和普通的中间的结点，我们就能串联起一个链表，如下图所示：

像上面这种一个结点连着下一个结点的形式，称为链式存储结构。在这个链表中，有效元素有3个：12、66和18。其中，头结点的-1是默认值，头指针0x250指向第一个结点；第一个结点存储的元素值是12，指针0x480指向第二个结点；同理，第二个结点存储的元素值是66，其指针0x960指向下一个结点；以此类推，直到尾结点。尾结点的指针是NULL，标志着链表的结束。

仔细观察上图，你会发现这个链表只能通过上一个结点的指针找到下一个结点，反过来则是行不通的。因此，这样的链表也被称作单向链表。

因此，为了弥补单向链表的不足，又提出了循环链表、双向链表、双向循环链表：

• 循环链表。对于一个单向链表，将它最后一个元素的指针指向第一个元素。
• 双向链表。对结点的结构进行改进，除了有指向下一个结点的指针以外，再增加一个指向上一个结点的指针。
• 双向循环链表。将双向链表和循环链表的结构进行融合。

(3) 链表与数组的比较

链表和数组在存储结构上的差别：

• 数组可看作是一种顺序表，它必须占用一整块连续的存储空间，不利于存储空间的管理。
• 而链表中元素的存储位置通过指针来连接，因此每个结点的存储位置可以任意安排，不要求连续。

存储方式上的差异，使得链表更易于进行插入、删除操作：

• 在数组中，元素存储的位置是相邻的，所以当进行插入、删除操作时，通常要移动后面所有的元素，这是非常耗时的。
• 在链表中，元素的存储位置不相邻，相邻元素之间是通过指针来链接。所以当进行插入、删除操作时，只需修改相关结点的指针域即可，这样既方便又省时。

除此之外，由于链表的每一个结点需要额外的存储一个指针，所以存储密度会下降。比如，数组的一个内存单元存放一个值，所以它的存储密度是100%；链表的一个内存单元要同时存放一个值和指针，所以它的密度<100%。

注：存储密度是指：数据本身的存放空间 / 整个结点结构的存放空间。一般存储密度越大，存储空间的利用率越大。

2. 链表中的增删查

下面主要介绍单向链表的增删查操作，其他类型的链表与此相似，就不一一赘述。

(1) 增

增操作：假设有一个链表，按顺序存储了4个同学的考试成绩。突然发现小明的成绩忘记录入了，需要将小明的成绩插入第3个位置。如下图所示：

在原有4个学生的基础之上，需要增加小明的成绩到第三个位置。过程如上图：

1. 第一步，我们需要找到学生2的位置，将学生2的指针P1更改为小明的内存地址。
2. 第二步，将小明的指针P2指向学生3的内存地址。

仅仅这两步就完成了一个增加操作。可见通过链表增加数据，并不会导致后面的元素移动。

(2) 删

删操作：老师在登记成绩的过程中，发现误把别班的小红的成绩登进来了，现在需要删掉小红的成绩。如下图所示：

在原来的5个学生中，要删除小红的成绩，过程如下：

• 将学生2 的指针P1 更改为学生3的内存地址。使得学生2的结点和学生3的结点相连，跳过了小红。

仅仅通过这一步就完成了一个删除操作。可见通过链表删除数据，也不会改变后面元素存放的位置。

(3) 查

查操作：查操作有两种：第一种是按索引查，比如查第3个学生的成绩；第二种是按值去查找，比如查出成绩是88分成的学生。

• 对于第一种查操作。由于链表中结点的内存地址不是相邻的，所以不能像数组一样，直接用过索引来查找。必须从头结点开始一个一个往后遍历，直到找到对应序号为3的学生的成绩。因此时间复杂度是O(n)。
• 对于第二种查操作。当要查找具体成绩是88分的学生时，也只能从头结点开始，一个个往后遍历查找，直到找到结点存储值为88的学生。因此时间复杂度也是O(n)。

由此可见，链表对于查操作并不友好。不管是按照位置的查找还是按照数值条件的查找，都需要对全部数据进行遍历，时间复杂度是O(n)。

3. 总结与体会

到此我们不难总结，在链表中：

• 增、删操作比较容易，通过更改指针的指向就能完成，时间复杂度为O(1)。
• 查找操作并不友好，需要从前往后逐一遍历，时间复杂度为O(n)。

虽然链表在新增和删除数据上有优势，但是仔细想想，其实这个优势并不太实用。这主要是因为，在新增数据时，通常会伴随一个查找的动作。

比如，在上面的增操作中，要将小明的成绩插入第3个位置。那么首先我们需要找到第二位置，才能将第2个结点的指针指向小明。同理，当我们要删除小红的成绩时，也需要找到小红的前一个位置，再更改前一个位置的指针指向。

由此可见，增、删操作通常会伴随一个查操作。所以整体的复杂度就是：O(1) + O(n)。根据【代码优化方法论01】衡量程序运行效率——复杂度 中的复杂度计算方法可知，O(1) + O(n) = O(n)。因此整体的复杂度还是O(n)，可见增、删操作也并不是很友好。

因此，线性表真正的价值在于，它对数据的存储方式是按照顺序的存储。如果数据的元素个数不确定，且需要经常进行数据的新增和删除时，那么链表会比较合适。如果数据元素大小确定，删除插入的操作并不多，那么数组可能更适合些。

由于水平有限，博客中难免会有一些错误，有纰漏之处恳请各位大佬不吝赐教！

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/106523294