<blockquote> 讯享网
🤡博客主页：醉竺
🥰本文专栏：
😻欢迎关注：感谢大家的点赞评论+关注，祝您学有所成！
✨✨💜💛想要学习更多数据结构与算法点击专栏链接查看💛💜✨✨
目录
一. 链表的认识和定义
二. 链表的分类
三. 头结点和头指针的区别
四. 链表的存储方式
五. 链表和顺序表的区别
链表是由许多相同数据类型的元素按照特定顺序排列而成的线性表，其特性是在计算机内存的位置是不连续与随机(Random)存储的。
优点：数据的插入或删除都相当方便，有新数据加入就向系统要一块内存空间，数据删除后，就把空间还给系统，不需要移动大量数据。
缺点：设计数据结构时较为麻烦，另外在查找数据时，也无法像静态数据一样可随机读取数据，必须按顺序找到该数据为止。
日常生活中有许多链表的抽象运用，例如可以把“单向链表”想象成火车，有多少人就只挂多少节的车厢，当假日人多需要较多车厢时可多挂些车厢，人少了就把车厢数量减少。游乐场中的摩天轮也是一种“环形链表”的应用，可以自由增加坐厢数量。
定义：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。
3.顺序表和链表存储结构的区别：
实际中链表的结构非常多样，按照大类分有以下3种，以下3种情况还可以两两组合或者三三组合。
1. 带头或者不带头链表
2. 单向链表或者双向链表
3. 循环或者非循环链表
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
无头单向非循环链表 和 带头双向循环链表
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都 是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了，后面我们代码实现了就知道了。
先看一下有无头结点的单链表图。
头指针：上图两个链表中的指针L都是头指针，首先它是一个指针！其次它是指向链表第一个结点(头结点或首元结点)的指针。(如果链表有头结点则头结点就是第一个结点，无头结点则首元结点就是第一个结点)
头结点定义：头结点通常叫作Dummy Head或者”哑头“，是在链表第一个有效结点的前面额外附加的一个结点。
头结点的数据域：可以不记录信息，也可以记录表长等信息(推荐前者),计算单链表长度时不计算头结点。
头结点的指针域：指向链表的首元结点。（看图）
头结点和头指针的区分：头结点是链表中通常不存储有效信息的第一个结点（一般是为了方便处理正常链表的操作才会加上）。
头指针是不管链表带不带这个特殊头结点，头指针都始终指向链表的第一个结点（所以有头结点就指向这个特殊的头结点，无头结点就指向正常链表的第一个结点）。
如何判断链表是否为空表？
无头结点：if (L==NULL)
带头结点：if (L->next==NULL)
引入头结点的优点：
1. 使对链表的第一个位置上的操作和在表的其他位置上的操作一致，无须特殊处理。
2. 无论链表是否为空，其头指针始终是一个指向头结点的非空指针，使得对空表和非空表的操作处理变得统一。
对头结点的思考：
尽管有的时候头结点的加入非常便捷，但是我们不能依赖于带头结点的链表操作。因为无论是LeetCode刷题还是去公司笔试的时候很多题目都是不带头结点的，所以我们一定要学会对不带头结点的链表的操作，之后遇到的题目中如果带头结点更方便解决，再手动增加头结点进行合理使用。
了解完链表的类型，再来说一说链表在内存中的存储方式。
顺序表、数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。
链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
如图所示，
这个链表起始节点为2， 终止节点为7， 各个节点分布在内存的不同地址空间上，通过指针串联在一起。
总结：
本文介绍了链表的特点和定义以及常见的各种链表，对链表的结构有个大体的了解和认识。后续若想学习各种链表的详细操作和原理的深入，可以点击本篇文章的专栏学习整个数据结构与算法的体系，例如。如果觉得本篇文章对你有帮助，麻烦点个赞吧~
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/150409.html