🚃 链表
想象一列火车：每节车厢装着货物，还靠钩子钩住下一节。链表就是这样的「数据火车」——每个节点存自己的数据，再用一个「钩子」（指针）指向下一个节点。想在中间加一节车厢？只要把钩子重新钩一下就行，不用把整列车搬走。这一页把单链表、双链表、循环链表都认个遍。
考纲知识点：单链表、双链表、循环链表的创建、插入、删除、遍历、查找的基本操作
📖
考纲 · 知识点详述
摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 五级
- (3)掌握链表的创建、插入、删除、遍历和反转操作，理解单链表、双链表、循环链表的区别。
📚
先学一学
花 5 分钟读完下面 5 课，再去闯关就不慌啦
1
🎒 一个节点 = 一截车厢 = 数据 + 钩子
链表的每一节叫节点（node），像一截火车车厢，里面有两样东西：数据（车厢里装的货）和指向下一个节点的钩子（next 指针，记住下一节在哪）。链表的第一节叫头节点 head，最后一节的钩子指向空（nullptr），表示「后面没车了」。
💻 读代码：节点的模样
看得懂就好，不用背（四级学过指针，正好用上）：
struct Node {
int data; // 车厢里的货物
Node* next; // 钩子：指向下一节车厢
};
int data; // 车厢里的货物
Node* next; // 钩子：指向下一节车厢
};
Node* next 就是指针——存的是下一节节点的地址，正好用四级学的「记门牌号」来理解。
💡 口诀：节点两件宝：一个装数据，一个指下家；头节点带头，尾节点指空。
2
⚖️ 数组像连坐，链表像火车
🏠 数组 = 电影院连坐
数组是一排紧挨着的座位，下标就是座位号。想看第 5 个，直接报号 a[4] 立刻找到（随机访问快）。但想在中间插一个人，后面所有人都要挪位子，很费劲。
💡 口诀：数组报号快、挪位慢；按下标一步到位，中间插入要搬家。
🚃 链表 = 火车车厢
车厢不要求挨着放，靠钩子连成一条线。想中间加一节，把钩子断开、重新钩两下就完成，其它车厢纹丝不动（插入快）。但想找第 5 节，只能从车头一节一节数过去（查找慢）。
💡 口诀：火车加挂快、找第几节慢；链表适合「经常中间增删」的数据。
3
🚉 单链表、双链表、循环链表：三兄弟各有绝活
1️⃣ 单链表
每节车厢只有一个钩子朝后，只能从车头往车尾走，不能回头。
💡 口诀：单链表 = 单行线，只能往前开。
2️⃣ 双链表
每节车厢有两个钩子：一个指向前一节（prev），一个指向后一节（next）。这样既能往前也能往后走，删除某节时不用从头找它的「前一节」。代价是每节要多记一个钩子，占更多内存。
💡 口诀：双链表 = 双车道，前后都能走；前后都能指，删除更方便。
3️⃣ 循环链表
把最后一节车厢的钩子接回头节点，整条链变成一个环（像环形的过山车轨道），可以从任何位置出发绕一圈回到原地。常用于「轮流排队」这种转圈场景。
💡 口诀：循环链表 = 环形轨道，尾又接回头；转圈轮流的场景正好用它。
4
🔗 插入与删除：断链、重接，别把链子弄丢
想在 B 车厢和 C 车厢之间加一节新车厢 X：① 先把 X 的钩子指向 C；② 再把 B 的钩子改成指向 X。顺序特别重要——如果先把 B 的钩子改掉，C 就找不到了（链子断在半路）。
🗑️ 删除节点：让前一个钩子跳过它
删除中间的 X：找到 X 的前一个节点 B，把 B 的钩子直接指向 X 的后一个节点 C，X 就被「跳过去」了。X 虽然还在内存里，但已经不在链上。
💡 口诀：删除是「跳过」，插入是「先指后改」；单链表里找前一个节点最费劲，双链表就好办。
⚠️ 先想后写：别把链子弄断
改动链表前先在纸上画出「谁指着谁」；尤其是插入时，先接好新节点自己的钩子，再动旧节点的钩子，顺序一错整条链就断了。
💡 口诀：加车厢先让新车指后车，再让前车指新车；换钩子要留「备用指路牌」。
5
🧭 遍历、查找、反转
🚶 遍历：从 head 开始一路 next 到底
遍历就是「从车头走到车尾」，把每个节点的数据都看一遍。查找某个值也靠遍历，找到就停。看得懂就好，不用背：
Node* p = head;
while (p != nullptr){
cout << p->data << " "; // 看看这节车厢
p = p->next; // 顺着钩子去下一节
}
while (p != nullptr){
cout << p->data << " "; // 看看这节车厢
p = p->next; // 顺着钩子去下一节
}
p->data 是「顺着指针拿数据」的写法（指针那页学过）。
💡 口诀：遍历 = 从 head 顺着 next 走到底；查找某个值，只能一节一节问。
🔄 反转：把整列火车掉个头
反转就是把 head 变 tail、每一节的 next 都指回前一个节点。做法是准备三个「手指」：prev（前一节）、cur（当前节）、next（下一节），边走边把 cur 的钩子改指 prev，再把三根手指一起往前挪。
💡 口诀：反转三指禅：先存 next，再让 cur 指 prev，然后一起往前走。
🌟 行业实际：链表藏在哪里
浏览器的「后退」靠双链表记住访问历史；音乐播放列表「上一首/下一首」像循环双链表；操作系统的任务队列、内存的空闲块管理也常靠链表——因为任务会不断插入和删除，火车式结构最合适。
🎯
闯关小锦囊 · 考点提醒
- 节点 = 数据 + next 钩子；链表有头节点 head，尾节点 next 指向 nullptr。
- 数组按下标访问快、中间插入慢；链表中间插入删除快、按下标找第几个慢。
- 单链表只能往后走；双链表有 prev + next 能前后走；循环链表尾接回头成环。
- 插入：先让新节点指后节点，再改前节点的钩子；删除：让前节点跳过被删节点。
- 遍历 = 从 head 顺着 next 走到底；反转用三个指针边走边改方向。
- 链表每个节点要多存一个「钩子」，所以存同样多的数据比数组更占内存；带头结点的循环单链表可用「头结点的 next 是否指向自身」判空。
🎮
学完了？来闯关！
下面 15 个小挑战，点一点就能玩
Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。