【数据结构与算法】(4)：链表是什么？头结点和头指针的区别？

🤡博客主页：

🥰 本文专栏：

😻 欢迎关注： 感谢大家的点赞评论+关注，祝您学有所成！

**✨✨💜💛想要学习更多

点击专栏链接查看💛💜✨✨**

目录

一. 链表的认识和定义

链表是由许多 相同数据类型 的元素按照特定顺序排列而成的 线性表 ，其特性是在计算机 内存 的位置是 不连续与随机(Random)存储 的。

优点 ： 数据的插入或删除都相当方便，有新数据加入就向系统要一块内存空间，数据删除后，就把空间还给系统，不需要移动大量数据。

缺点： 设计数据结构时较为麻烦，另外在查找数据时，也无法像静态数据一样可随机读取数据，必须按顺序找到该数据为止。

日常生活中有许多链表的抽象运用，例如可以把 “单向链表” 想象成火车，有多少人就只挂多少节的车厢，当假日人多需要较多车厢时可多挂些车厢，人少了就把车厢数量减少。游乐场中的摩天轮也是一种 “环形链表” 的应用，可以自由增加坐厢数量。

定义： 链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。

3.顺序表和链表存储结构的区别：

二. 链表的分类

实际中链表的结构非常多样，按照大类分有以下3种，以下3种情况还可以两两组合或者三三组合。

1. 带头或者不带头链表

2. 单向链表或者双向链表

3. 循环或者非循环链表

虽然有这么多的链表的结构，但是我们实际中 最常用 还是两种结构：

无头单向非循环链表 和 带头双向循环链表

无头单向非循环链表 ：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

带头双向循环链表 ：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都 是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，后面我们代码实现了就知道了。

三. 头结点和头指针的区别

先看一下有无头结点的单链表图。

头指针 ：上图两个链表中的指针L都是头指针，首先它是一个指针！其次它是

指向链表第一个结点(头结点或首元结点)的指针。(如果链表有头结点则头结点就是第一个结点，无头结点则首元结点就是第一个结点)

头结点定义 ：头结点通常叫作Dummy Head或者”哑头“，是

在链表第一个有效结点的前面额外附加的一个结点。

头结点的数据域 ：可以不记录信息，也可以记录表长等信息(推荐前者),计算单链表长度时不计算头结点。

头结点的指针域 ：指向链表的首元结点。（看图）

头结点和头指针的区分：

头结点 是链表中通常不存储有效信息的第一个结点（一般是为了方便处理正常链表的操作才会加上）。

头指针是

不管链表带不带这个特殊头结点，头指针都始终指向链表的第一个结点

（所以有头结点就指向这个特殊的头结点，无头结点就指向正常链表的第一个结点）。

如何判断链表是否为空表？

无头结点： if (L==NULL)

带头结点： if (L->next==NULL)

引入头结点的优点：

1. 使对链表的第一个位置上的操作和在表的其他位置上的操作一致，无须特殊处理。

2. 无论链表是否为空，其头指针始终是一个指向头结点的非空指针，使得对空表和非空表的操作处理变得统一。

对头结点的思考：

尽管有的时候头结点的加入非常便捷，但是我们不能依赖于带头结点的链表操作。因为无论是LeetCode刷题还是去公司笔试的时候很多题目都是不带头结点的，所以我们一定要学会对不带头结点的链表的操作，之后遇到的题目中如果带头结点更方便解决，再手动增加头结点进行合理使用。

下面是常用的两种链表的详细操作和完整代码实现，配有超多图解，感兴趣的话可以深入学习：

四. 链表的存储方式

了解完链表的类型，再来说一说链表在内存中的存储方式。

顺序表、数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

如图所示，

这个链表起始节点为2， 终止节点为7， 各个节点分布在内存的不同地址空间上，通过指针串联在一起。

五. 链表和顺序表的区别

链表和顺序表的区别

总结：

本文介绍了链表的特点和定义以及常见的各种链表，对链表的结构有个大体的了解和认识。后续若想学习各种链表的详细操作和原理的深入，可以点击本篇文章的专栏学习整个数据结构与算法的体系，例如 。如果觉得本篇文章对你有帮助，麻烦点个赞吧~