数据结构笔记第四章（链表）

type

status

date

slug

summary

👉 推荐学习资料

《大话数据结构》——程杰

数据结构与算法基础（青岛大学-王卓）_哔哩哔哩

数据结构（浙江大学-陈越、何钦铭）_哔哩哔哩

📝 正文

第四章链表

4.1 链表的定义与表示

前面我们讲的线性表的顺序存储结构。它是有缺点的，最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。能不能想办法解决呢? 要解决这个问题，我们就得考虑一下导致这个问题的原因。为什么当插入和删除时，就要移动大量元素，仔细分析后，发现原因就在于相邻两元素的存储位置也具有邻居关系。它们编号是1,2,3…n,它们在内存中的位置也是挨着的，中间没有空隙，当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补。问题就出在这里。

那如何解决这个问题呢？

如果要让相邻的元素中空出位置来让新元素更好的插入，这中间的空位多了浪费空间，少了又不行。于是一个新想法出现了，那干脆所有的元素都不要考虑相邻位置了，哪有空位就到里，而只是让每个元素知道它下一个元素的位置在哪里，这样，我们可以在第一个元素时，就知道第二个元素的位置(内存地址), 而找到它；在第二个元素时，再找到第三个元素的位置(内存地址)。这样所有的元素我们就都可以通过遍历而找到。这便是线性表的链式存储，下面让我们看看它的概念。

线性表的链式存储:是指用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。

为了表示每个数据元素 ai 其直接后继数据元素 ai+1 之间的逻辑关系，对数据元素 ai 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。因此，我们可以引出数据域、指针域、结点的概念。

数据域：存储数据元素信息的域。

指针域：存储其直接后继存储位置的域。而指针域中存储的信息称为指针或链。

节点：由指针和链组成数据元素 ai 的存储映像。

n个节点(a的存储映像)链结成一个链表，即为线性表(ar,az,·…,an)的链式存储结构，因为此链表的每个节点中只包含一个指针域，所以叫做单链表。单链表正是通过每个节点的指针域将线性表的数据元素按其逻辑次序链接在一起，如图4-1-1所示。

在链表中，存储第一个数据元素a₁的结点称为首元结点。空表的首元结点为空指针NULL。头结点是在首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域可以不存储任何信息，也可存储与数据元素类型相同的其他附加信息。比如，当数据元素为整型时，头结点的数据域中可存放该线性表的长度 n。头结点的引入是为了操作的统一和方便，使得对链表的第一个数据元素的操作和其他结点相同，而无须特殊处理。

头指针是指向链表中第一个结点的指针。若链表设有头结点，则头指针指向该链表的头结点。若链表不设头结点，则头指针指向该链表的首元结点。整个链表的存取必须从头指针开始进行。之后的每一个节点，其实就是上一个的后继指针指向的位置。

不管是否设有头结点，链表的最后一个结点都没有后继，其指针域中存放一个空指针NULL。

4.2 单链表的操作

4.2.1 单链表的存储结构

单链表的存储结构的类型可定义如下：

4.2.2 单链表的初始化

初始化操作，构造一个空单链表。 List本身是结构体指针类型，因此形参l是二级指针类型。标准C语言不支持引用调用，否则形参可定义为List &l，这样程序代码会更加简洁。

4.2.3 单链表的销毁与清空

销毁操作，销毁单链表：

将单链表清空：

4.2.4 判断单链表是否为空

判断单链表是否为空，若单链表为空，则返回TRUE，否则返回FALSE：

4.2.5 单链表的长度

返回单链表的长度：

4.2.6 单链表的插入

单链表第1个数据插入节点的算法思路：

声明一节点p指向链表第一个节点，初始化j从1开始；

当i时，就遍历链表，让p的指针向后移动，不断指向下一节点，i累加1;

若到链表末尾p为空，则说明第1个元素不存在；

否则查找成功，在系统中生成一个空节点s;

将数据元素e赋值给s->data;

单链表的插入标准语句s->next = p->next;

返回成功。

插入操作。在单链表的第pos个位置之前插入新的数据元素e，成功则返回TRUE；否则返回FALSE：

4.2.7 单链表的删除

单链表第1个数据删除结点的算法思路：

声明一结点p指向链表第一个结点，初始化i从1开始；

当i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，i累加1;

若到链表末尾p为空，则说明第1个元素不存在；

否则查找成功，将欲删除的结点p->next赋值给q;

单链表的删除标准语句p->next = q->next;

将q结点中的数据赋值给e，作为返回；

释放q结点；

返回成功。

删除操作。删除单链表的第pos个位置的元素，成功则返回TRUE；否则返回FALSE：

4.2.8 单链表的取值

获取单链表的第pos个位置的元素，用e返回其值，成功则返回TRUE；否则返回FALSE：

4.2.9 单链表的查找

查找单链表的首个元素值等于e的元素位置，成功则返回其位置序号；否则返回NotFound。

4.2.10 单链表的遍历

遍历输出单链表中各个数据元素的值

4.3 单链表的性能分析

4.3.1 单链表的时间复杂度

查找：与待查找元素位置有关，因此平均时间复杂度为O(n)

插入：必须先定位到其前驱结点，因此时间复杂度为O(n)

删除：与插入相同，时间复杂度也为O(n)

4.3.2 单链表的优点和缺点

优点：

插入和删除元素方便，只要直接修改链中结点指针域的值，无需移动表中的元素，就能高效地实现插入和删除操作。

数据元素的个数可以自由扩充。

缺点：

存储密度小

存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问

4.3.3 单链表与顺序表的对比

4.4 循环链表

4.4.1 循环链表的定义

上一章我们已经学习了单链表，那么这时候有人就提出了一个疑问了，如果我已经知道我想要的数据在链表的后半段，难道我也要从头开始一个个查找吗？这是一件很悲哀的事情，明知道从中间开始查找可以剩一半的时间，但是单链表怎样都只能从头开始遍历。

这时候，循环链表就出现了，它完美的解决了这个问题，下面是它的定义：

循环链表（Circular Linked List）：是另一种形式的链式存储结构，它的结点结构与单链表相同，不同的是链表中表尾结点的指针域不是NULL，而是指向头结点，整个单链表形成一个环，从表中任一结点出发均可以找到其他任意结点，包括该结点的前驱结点。

4.4.2 循环链表的合并

合并操作仅需改变两个指针值即可，主要代码段如下：

4.4.3 循环链表与单链表的区别

4.5 双向链表

4.5.1 双向链表的定义

这个是时候有人提出问题了：单链表只能从前往后查找，不能从后往前查找，我就喜欢反过来遍历，应该怎么办呢？（真就一身反骨呗 😅）

不管是单链表还是单循环链表，表中结点中只有一个指示其直接后继的指针域，因此，从某个结点出发只能循链向后寻查其他结点。若要寻查结点的直接前驱，则必须从表头指针出发。也就是说，在单链表中，查找结点直接后继的时间复杂度为O(1)，查找结点直接前驱的时间复杂度则为 O(n) 。为了克服单链表这种单向性的缺点，可以采用双向链表。

这时候我们的双向链表就登场了，下面是它的概念：

双向链表(double linked list):是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

4.5.2 双向链表的类型定义

4.6 链表的应用：一元多项式的运算

4.6.1 为什么用链表解决一元多项式的运算

如果让你用代码去解决一元多项式的运算，你会怎么去解决。

第一种办法便是使用数组去解决，建立一个数组，就代表着常数项，代表着一次项的系数，代表着二次项的系数等等。

这种办法看似合理，但是有一种情况它解决不了，那便是稀疏多项式。就如下面这个例子：

如果还是用第一种方法的话，岂不是你的数组大小得有10000项，但这10000项却又只使用了两项，你不心疼计算机浪费了这么多空间，计算机自己都心疼呢！

所以这时候链表的用处就体现出来了，链表就擅长这种项少的活，所以下面就让我们来看看如何用链表来解决一元多项式的运算。

链表解决一元多项式的办法：只存储非零元素，通过改变线性表中的元素设定，对多项式的每一个非零项，可用系数和指数唯一确定。因此，就可以用线性表((1, 0), (3, 10000), (5, 20000))来表示。这种表示方法将大大节省空间。

其对应的数据结构：

那么让我们来举个例子，对于下面两个多项式：

对于这两多项式的单链表存储结构如图：

4.6.2 一元多项式的求和

假设头指针为polyA和polyB的单链表分别为一元多项式A和B的存储结构，链表中结点均按升幂排列，指针pa和指针pb分别指向A和B中当前进行比较的某个结点，则逐一比较两个结点中的指数项：

对于指数相同的项，应该合并同类项，对应系数相加，若和不为零，则作为“和多项式”中的一项插入到“和多项式”链表中去；

对于指数不相同的项，则通过比较先将指数值较小的项插入到“和多项式”链表中去，指数值较大的项继续参与后续比较。“和多项式”链表中的所有结点无需重新生成，而应该从两个多项式的链表中摘取。

📎 参考文章