一、引言
链表，作为计算机科学中的基础数据结构，以其独特的非连续存储方式和高效的插入、删除操作而备受青睐。无论是数据结构、算法还是实际系统开发中，链表都扮演着不可或缺的角色。
为了深入理解和掌握链表，我们需要从基本概念出发，通过实践来加深理解。
本文旨在为读者提供一个理论与实践相结合的链表学习指南，帮助大家系统地掌握链表的核心知识，并在实际编程中灵活运用。让我们一起踏上这场链表探索之旅吧！
二、链表的基础概念
🍃链表的概念
链表（Linked List）是一种常见的数据结构，用于存储一系列有序的元素。与数组不同，链表中的元素在内存中并不是连续存储的，而是通过指针或引用链接在一起。以下是链表的一些基础概念：
- 节点（Node）：
- 链表中的每一个元素都称为一个节点。
- 一个节点通常包含两部分：数据部分和指针部分（或称为链接部分）。
- 数据部分用于存储实际的数据。
- 指针部分（或链接部分）用于指向链表中的下一个节点。
- 头节点（Head Node）：
- 链表的第一个节点通常被称为头节点。
- 在某些实现中，链表可能包含一个哑节点（dummy node）或哨兵节点（sentinel node）作为头节点，其数据部分不存储实际的值，仅用于简化边界条件的处理。
- 尾节点（Tail Node）：
- 链表的最后一个节点被称为尾节点。
- 尾节点的指针部分通常设置为
null或None（取决于编程语言），表示链表的结束。
🍃顺序表和链表的对比
顺序表与链表是两种常见的线性数据结构，它们在存储方式、操作性能等方面存在显著的差异。以下是它们之间的详细对比：
1. 存储方式
- 顺序表：
- 将元素一个接一个地存入一组连续的存储单元中，存储空间连续。
- 存储密度高，因为每个数据元素只占用一个空间。
- 长度固定，必须在分配内存之前确定数组的长度。
- 链表：
- 节点在物理存储单元上非连续、非顺序的存储，通过指针或引用链接在一起。
- 存储空间不连续，每个节点除了存储数据元素外，还需要存储指向下一个节点的指针。
- 长度不固定，可以动态地添加或删除节点。
2. 操作性能
- 插入和删除：
- 顺序表：在顺序表中插入或删除元素时，需要移动大量元素以保持连续性，因此效率较低，时间复杂度为O(N)。但在末尾插入或删除数据比较方便，时间复杂度为O(1)。
- 链表：在链表中插入或删除元素时，只需修改相关节点的指针，时间复杂度为O(1)（如果知道要处理节点的前一个位置）或O(N)（如果不知道要处理节点的前一个位置）。头插、头删的效率高，时间复杂度是O(1)。
- 查找：
- 顺序表：支持随机访问，查找效率高，时间复杂度为O(1)（按索引查找）。如果顺序表的数据按序排列，还可以使用二分查找法进一步提高效率。
- 链表：不支持随机访问，查找效率低，需要遍历节点，时间复杂度为O(N)。
- 空间性能：
- 顺序表：需要预先分配足够大的存储空间，如果估计过大，可能会导致空间浪费；如果估计过小，又会造成溢出。
- 链表：动态分配存储空间，无需预先估计存储规模，可以根据需要动态地添加或删除节点。
3. 适用场景
- 顺序表：适用于需要频繁访问元素、且元素数量基本不变的场景，如大量访问元素的而少量增添/删除元素的程序。
- 链表：适用于需要频繁插入、删除元素，且对访问元素无严格要求的场景，如管理动态数据、实现文件系统、排序等。
4. 总结
顺序表和链表各有优缺点，选择哪种数据结构取决于具体的应用场景和需求。如果需要频繁访问元素且元素数量基本不变，可以选择顺序表；如果需要频繁插入、删除元素，且对访问元素无严格要求，可以选择链表。
🍃 链表的分类
链表的结构⾮常多样，按照单向或双向，带头节点或不带头节点，循环或不循环分类
以下情况组合起来就有8种（2x2x2）链表结构：
虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构：单链表和双向带头循环链表
1.⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。
2.带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实现反⽽简单了，后⾯我们代码实现了就知道了。
三、链表的实现
🍃无头单向非循环链表的实现
🍃带头双向循环链表的实现
四、链表的应用
🍃基于单链表实现通讯录
五、链表相关习题解析
初阶：
🍃求链表的中间节点
【数据结构与算法 刷题系列】求链表的中间结点_求结点-CSDN博客
🍃合并两个有序链表
🍃环形链表的约瑟夫问题
【数据结构与算法 刷题系列】环形链表的约瑟夫问题-CSDN博客
🍃移除链表元素
🍃反转链表
【数据结构与算法 经典例题】反转链表(图文详解)-CSDN博客
🍃相交链表求交点
【数据结构与算法 经典例题】相交链表求交点_相交链表求相交节点-CSDN博客
🍃返回单链表的倒数第k个节点
【数据结构与算法 经典例题】返回单链表的倒数第 k 个节点-CSDN博客
进阶：
🍃链表的回文结构
【数据结构与算法 经典例题】链表的回文结构（图文详解）-CSDN博客
🍃随机链表的复制
【数据结构与算法 经典例题】随机链表的复制（图文详解）-CSDN博客
🍃判断链表是否带环
【数据结构与算法 刷题系列】判断链表是否有环（图文详解）-CSDN博客
