想象一下，你正在开发一个简单的游戏，需要存储玩家的角色列表，比如从1号玩家到100号玩家。如果用数组来存，删除中间某个玩家时，后面的所有玩家都要往前挪位置，很麻烦。这时候，链表就派上用场了——每个玩家的信息（数据）旁边只需要记住下一个玩家是谁（指针），不需要连续的内存空间，插入删除只需要改几个指针，就像调整糖葫芦的竹签一样方便。
什么是链表？¶
链表是一种线性数据结构，每个元素（称为“节点”）由两部分组成：数据域（存具体信息）和指针域（存下一个/前一个节点的地址）。和数组不同，链表的节点在内存中不是连续的，就像散落的珠子用线串起来，线就是指针。
单链表：只能“单向”走的糖葫芦串¶
单链表是最简单的链表，每个节点只有一个指针，指向下一个节点。我们可以把它想象成一串糖葫芦，每颗山楂（节点）只知道下一颗山楂在哪里，不知道上一颗。
单链表的节点结构：¶
数据 | 指针 → 下一个节点
比如，存储“玩家1→玩家2→玩家3”的单链表：
玩家1数据 | → 玩家2
玩家2数据 | → 玩家3
玩家3数据 | → null（表示结束）
单链表怎么用？¶
- 遍历：只能从第一个节点（头节点）开始，顺着指针一直走到最后一个节点（next为null）。比如查第5个玩家，必须从头开始数到第5个。
- 插入/删除：要在中间插入一个节点，得先找到“目标节点的前一个节点”，然后修改指针。比如在玩家2和玩家3之间插入玩家4：
1. 先找到玩家2（原链表：玩家1→玩家2→玩家3）
2. 新建玩家4节点，让玩家4的指针指向玩家3
3. 把玩家2的指针从指向玩家3，改为指向玩家4
这样就完成了插入，不需要移动其他节点。
但如果要删除玩家3，必须先找到玩家2（前驱节点），把玩家2的指针直接指向玩家3的下一个节点（null）。
双链表：能“前后”走的糖葫芦串¶
双链表比单链表多了一个指针，每个节点不仅知道下一个节点是谁，还知道前一个节点是谁。现在每颗山楂不仅能被下一颗牵着，还能被上一颗牵着，像带了双向挂钩的糖葫芦。
双链表的节点结构：¶
前指针 ← 数据 → 后指针
比如，同样存储“玩家1→玩家2→玩家3”的双链表：
null ← 玩家1数据 → 玩家2
玩家1 ← 玩家2数据 → 玩家3
玩家2 ← 玩家3数据 → null
双链表怎么用？¶
- 遍历：可以从任意节点开始，既能向前走（通过prev指针），也能向后走（通过next指针）。比如从玩家2开始，能直接找到玩家1（用prev）或玩家3（用next）。
- 插入/删除：在已知节点处插入或删除时，双链表更方便。比如在玩家2和玩家3之间插入玩家4：
1. 新建玩家4节点，把玩家4的prev指向玩家2
2. 把玩家4的next指向玩家3
3. 把玩家2的next从指向玩家3，改为指向玩家4
4. 把玩家3的prev从指向玩家2，改为指向玩家4
这样一步到位，不需要再找“前驱”，因为玩家2的prev已经是玩家1，玩家4可以直接和前后节点建立联系。
单链表 vs 双链表：核心区别大总结¶
| 对比项 | 单链表 | 双链表 |
|---|---|---|
| 节点结构 | 只有一个指针（next） | 两个指针（prev + next） |
| 遍历方向 | 只能单向遍历（从头到尾） | 双向遍历（可前可后） |
| 插入/删除 | 需要先找到“前驱节点”，修改指针 | 直接通过prev/next指针操作，更简单 |
| 内存占用 | 少一个指针，节省内存 | 多一个指针，内存占用稍高 |
| 适用场景 | 简单单向数据存储（如队列） | 需要双向操作（如浏览器历史、双向链表队列） |
为什么要学双链表？¶
如果你的游戏只需要“从头到尾”显示玩家列表，单链表足够。但如果要实现“同时显示历史记录和未来记录”（比如浏览器的前进后退），或者在链表中间频繁插入删除节点，双链表更灵活。比如在手机通讯录中，想在已知联系人处同时向前和向后添加联系人，双链表能快速完成。
总结¶
- 单链表：像一串糖葫芦，只能从左到右吃，简单省空间，适合单向操作。
- 双链表：像一串带双向挂钩的糖葫芦，能从左到右也能从右到左吃，功能更全但稍占内存，适合需要双向移动的场景。
初学者不用急着记复杂的操作，先记住“指针数量”和“遍历方向”的区别，以后遇到实际问题（比如实现一个双向链表队列）再慢慢熟悉细节~