本课时有配套视频讲解，购买后即可观看（永久有效）
链表基础
一、课上练习
编程练习
- 单向链表的增删改查：L3181
二、知识总结
✨ 核心思想
单向链表是一种基础的数据结构，广泛用于实现各种算法和程序。在单向链表中，每个元素称为"节点"，每个节点包含数据部分以及指向下一个节点的链接或指针。
✨ 结构和组成
单向链表的每个节点通常由两部分组成：
- 数据域：存储实际的数据（如整数、字符串或任何其他类型的数据）。
- 指针域：包含一个指针，指向列表中的下一个节点。这使得节点之间形成一个链条。
链表的起始点称为"头节点"，它不包含数据，仅用作指向第一个实际数据节点的指针。链表的末尾节点的指针域为 nullptr，标志着链表的结束。
✨ 基本操作
单向链表支持多种基本操作，包括但不限于：
- 插入：可以在链表的头部、尾部或指定节点之后插入新节点。头部插入是最简单的，因为只需更改头节点的指针即可；尾部或中间位置的插入需要更多的步骤，因为需要找到正确的位置并更新相应的指针。
- 删除：从链表中删除节点涉及找到该节点及其前一个节点，然后调整前一个节点的指针以跳过要删除的节点。
- 搜索：遍历链表来查找含有特定值的节点。
- 遍历：从头节点开始，逐个访问链表中的每个节点，直到达到链尾（
nullptr）。
下面的代码展示了单向链表的完整实现，包括插入、删除、更新和打印操作：
单向链表代码示例
1#include<iostream>
2using namespace std;
3
4// 定义链表的节点结构
5struct Node {
6 int value; // 节点存储的值
7 Node *next; // 指向下一个节点的指针
8};
9
10// 打印链表的函数
11void print(Node *head) {
12 Node *current = head->next; // 从头节点的下一个节点开始遍历，跳过头节点
13 while (current) { // 当当前节点非空时继续遍历
14 cout << current->value; // 输出当前节点的值
15 current = current->next; // 移动到下一个节点
16 if (current) { // 如果下一个节点存在
17 cout << " "; // 在值之间输出空格
18 }
19 else {
20 cout << endl; // 在链表末尾输出换行符
21 }
22 }
23}
24
25// 向链表中插入节点的函数
26void insert(Node *head, int i, int j) {
27 Node *current = head;
28 int count = 0;
29 // 寻找插入位置的前一个节点
30 while (count < i && current->next) {
31 current = current->next;
32 count++;
33 }
34 // 如果找到了正确的插入位置
35 if (count == i) {
36 Node *node = new Node; // 创建新节点
37 node->value = j; // 设置新节点的值
38 node->next = current->next; // 新节点指向当前节点的下一个节点
39 current->next = node; // 当前节点指向新节点，完成插入
40 }
41}
42
43// 删除链表中的节点的函数
44void deleteNode(Node *head, int i){
45 Node *current = head;
46 int count = 0;
47 // 寻找要删除的节点的前一个节点
48 while (count < i - 1 && current->next) {
49 current = current->next;
50 count++;
51 }
52 // 如果找到了正确的位置，并且确实有节点可以删除
53 if (count == i - 1 && current->next) {
54 Node *dn = current->next; // 暂存要删除的节点
55 current->next = dn->next; // 将当前节点指向要删除节点的下一个节点
56 delete dn; // 释放要删除节点的内存
57 }
58}
59
60// 更新链表中节点的值的函数
61void update(Node *head, int i, int j) {
62 Node *current = head;
63 int count = 0;
64 // 寻找要更新的节点
65 while (count < i && current->next) {
66 current = current->next;
67 count++;
68 }
69 // 如果找到了正确的位置
70 if (count == i) {
71 current->value = j; // 更新节点的值
72 }
73}
74
75int main() {
76 freopen("list_oeprations1.in", "r", stdin); // 重定向标准输入
77 freopen("list_oeprations.out", "w", stdout); // 重定向标准输出
78 Node *head = new Node; // 创建头节点
79 head->next = NULL; // 初始化头节点的next为NULL
80
81 int n = 0;
82 string op;
83 int i = 0;
84 int j = 0;
85 cin >> n; // 读取操作数量
86 for (int k = 0; k < n; k++) {
87 cin >> op; // 读取操作类型
88 if (op == "insert") {
89 cin >> i >> j; // 读取插入操作的参数
90 insert(head, i, j); // 执行插入操作
91 }
92 else if (op == "delete") {
93 cin >> i; // 读取删除操作的参数
94 deleteNode(head, i); // 执行删除操作
95 }
96 else { // "update"操作
97 cin >> i >> j; // 读取更新操作的参数
98 update(head, i, j); // 执行更新操作
99 }
100 }
101 print(head); // 打印最终链表的状态
102 return 0;
103}✨ 执行示例
以下通过一系列操作，展示单向链表的内部状态变化。初始状态为空链表（只有头节点）：
初始状态：head → null操作1：insert(0, 10) — 在位置0后插入值10
创建新节点 node(10)
node->next = head->next (null)
head->next = node
结果：head → [10] → null操作2：insert(1, 20) — 在位置1后插入值20
1从head开始，移动1步到达节点[10]
2创建新节点 node(20)
3node->next = [10]->next (null)
4[10]->next = node
5
6结果：head → [10] → [20] → null操作3：insert(1, 15) — 在位置1后插入值15
1从head开始，移动1步到达节点[10]
2创建新节点 node(15)
3node->next = [10]->next ([20])
4[10]->next = node
5
6结果：head → [10] → [15] → [20] → null操作4：delete(2) — 删除位置2的节点
1从head开始，移动到位置2的前一个节点（位置1，即[10]→[15]中的[10]... 不对）
2实际：count从0走到 i-1=1 步，到达节点[15]
3dn = [15]->next = [20]
4[15]->next = [20]->next = null
5delete dn // 释放[20]的内存
6
7结果：head → [10] → [15] → null操作5：update(1, 12) — 将位置1的值更新为12
从head开始，移动1步到达节点[10]
[10]->value = 12
结果：head → [12] → [15] → null插入操作的指针变化（重点理解）
在节点 A 和节点 B 之间插入新节点 C 的两步操作顺序不能颠倒：
1正确顺序：
2 步骤1：C->next = A->next (B) // 先让C指向B
3 步骤2：A->next = C // 再让A指向C
4 结果：A → C → B ✓
5
6错误顺序：
7 步骤1：A->next = C // 先让A指向C
8 步骤2：C->next = A->next (C) // 此时A->next已经是C了！
9 结果：A → C → C → C → ...（无限循环）✗✨ 算法评价
优点
- 动态大小：链表的大小不是固定的，可以根据需要进行扩展。
- 内存效率：不需要在内存中预分配空间，只在需要添加新数据时分配内存。
- 简单插入和删除：相较于数组，链表在非末端位置的插入和删除操作不需要移动其它元素。
缺点
- 内存消耗：每个节点需要额外的存储空间来存储指针。
- 访问时间：链表不支持随机访问，访问任何位置的数据都需要从头开始遍历。
- 性能问题：大量的插入和删除操作可能导致内存碎片。
✨ 应用场景
单向链表在许多实际应用中都非常有用，例如实现队列、栈（通过链表的变种如链栈）、符号表以及其他数据结构。由于其灵活性和简单的内存管理，链表尤其适合于实现需要频繁插入和删除操作的应用场景。
✨ 解题步骤详解
遇到链表相关问题时，按以下步骤思考：
- 画图：链表问题最重要的技巧就是画图。在纸上画出节点和指针的关系，标记每一步操作后指针的变化，可以大大减少出错概率。
- 确定是否需要头节点：使用虚拟头节点（dummy head）可以统一处理"在链表头部插入/删除"和"在链表中间插入/删除"的情况，避免大量特判。
- 找到操作位置的前一个节点：插入和删除操作都需要修改"前一个节点"的 next 指针，所以遍历时要停在目标位置的前一个节点。
- 注意操作顺序：先处理新节点的 next 指针，再修改前一个节点的 next 指针（先接后断）。
- 释放被删除节点的内存：在 C++ 中，用
new创建的节点在删除时必须用delete释放，否则会造成内存泄漏。
✨ 常见错误
- 插入时指针操作顺序错误：如上所述，必须先让新节点指向后继节点，再让前驱节点指向新节点。顺序反了会导致链表断裂或产生循环。
- 删除节点后仍然访问它：
delete释放内存后，该指针变为悬空指针，继续通过它访问数据是未定义行为。 - 忘记释放删除节点的内存：每次
delete操作后应该delete被移除的节点，否则会造成内存泄漏。 - 遍历时丢失指针：如果修改了
current->next后还试图通过current->next继续遍历，会走到错误的位置。需要提前保存 next 指针。 - 没有处理空链表或边界情况：在空链表上删除节点、在只有一个节点的链表上操作等边界情况容易出错。写代码时应该考虑链表为空、只有一个节点、操作首尾节点等特殊情况。
- 链表遍历死循环：如果链表中不小心产生了环（某个节点的 next 指向前面的节点），遍历时会陷入死循环。
三、课后练习
编程练习
- 排队接水：L3182