侵入式链表是什么？它和普通链表有什么区别？
简化版
侵入式链表把 next、prev 这类链表指针直接放进业务对象内部，而不是额外创建包装节点。它减少分配和间接访问，常见于内核、游戏引擎等底层场景，但会让业务对象和链表结构强耦合。
详细版
普通链表通常是 Node { value, next }，业务对象作为 value 被包在节点里。侵入式链表则是业务对象自己携带链表指针，例如 Task { id, state, listNode }。
区别：
- 普通链表：容器拥有节点，节点引用业务对象。
- 侵入式链表：业务对象本身就是链表节点的一部分。
- 优点：少一次节点分配，少一层间接引用，删除已知对象更直接。
- 缺点：对象结构被链表污染，一个对象加入多个链表时要有多组链接字段。
面试中可以把它理解成“把链表节点嵌进对象里”，适合性能敏感和生命周期可控的系统。
完整版教学
一、普通链表的节点包装模型
常见链表会定义一个节点对象：
Node {
value: User
next: Node
}业务对象 User 不知道自己在链表里。链表容器负责创建 Node，把 User 包进去。这种设计解耦好，业务对象干净，适合大多数应用层代码。
代价是多了一层对象。访问业务数据时要先访问 Node，再访问 node.value。如果链表操作非常频繁，额外分配和间接访问可能成为成本。
二、侵入式链表如何把链接放进对象
侵入式链表把链接字段嵌入业务对象：
Task {
id
priority
prev
next
}或者更通用一点：
Task {
id
runQueueLink { prev, next }
}这样 Task 自己就能被挂进链表。容器不需要再创建额外 Node，已知 Task 时也能直接通过内部链接摘下它。Linux 内核里的 list_head 就是经典思想：结构体里嵌一个链表节点，通过偏移从链表节点反推出外层对象。
三、为什么它适合底层和高性能场景
侵入式链表的收益主要来自三点。第一，减少内存分配；第二，减少一层指针间接访问；第三，对象生命周期由外部系统控制，不需要容器单独管理包装节点。
数字化看：
普通链表：业务对象 100000 个 + Node 100000 个
侵入式链表：业务对象 100000 个，链接字段在对象内少 100000 个 Node 分配，对内核、游戏实体系统、实时系统可能很重要。尤其在内存分配昂贵或必须避免碎片的场景，这种结构很有价值。
四、强耦合是它的主要代价
侵入式链表会让业务对象知道链表存在。一个原本纯粹的 Task，现在多了 prev、next 或 runQueueLink 字段。对象模型不再完全和容器解耦。
如果同一个对象要同时加入多个链表，就不能只放一组 prev/next。例如一个任务既在“运行队列”，又在“超时队列”，就需要两组链接字段：
| 需求 | 需要的链接字段 |
|---|---|
| 只加入一个链表 | 一组 prev/next |
| 同时加入两个链表 | 两组独立链接 |
| 动态加入任意多个链表 | 侵入式方式会变复杂 |
这就是侵入式链表适合系统级代码、不一定适合业务 CRUD 代码的原因。
五、删除和生命周期为什么要格外小心
侵入式链表中，链表节点就是业务对象的一部分。对象被释放前，必须确认它已经从所有链表中摘除。否则链表里会留下指向已释放对象的悬挂引用。
普通托管语言里这个问题可能表现为旧引用导致对象无法回收；非托管语言里则可能是 use-after-free。侵入式结构换来性能，也换来更严格的生命周期纪律。
安全顺序：
1. 从链表摘除对象
2. 清空链接字段或标记未入链
3. 再释放或复用对象六、和普通链表如何选择
应用层代码通常优先普通链表或语言内置容器，因为解耦、易维护、安全。侵入式链表适合性能敏感、对象生命周期清晰、需要频繁 O(1) 摘挂的底层系统。
记忆钩子：普通链表是“节点包对象”，侵入式链表是“对象长出链表指针”。
七、常见误区与追问
- 误区：侵入式链表是一种新的链表算法。 它更多是节点所有权和对象布局设计，基本操作仍是指针重连。
- 误区：侵入式链表一定更好。 它牺牲解耦和安全性，只有在性能或底层控制需求明显时才值得。
- 误区：一个对象只能进一个侵入式链表。 可以进多个，但需要多组独立链接字段。
- 追问：为什么内核喜欢这种结构？ 内核重视少分配、低开销、可控生命周期，侵入式链表正好匹配。
- 追问：普通业务系统要用吗？ 通常不用，除非有非常明确的性能和对象生命周期控制需求。
八、加强记忆
侵入式链表的关键词是“链接字段内嵌”。它把容器节点塞进业务对象，少分配、少间接、摘挂快；但对象被链表结构侵入，耦合更强，生命周期也更难管。面试里能讲出收益和代价，比只说“Linux 用它”更有含金量。