链表进阶：双向链表、循环链表、内核链表实现
说实话，单链表就像一根绳子，只能从头摸到尾。你想想看，要是我想从某个节点往回走，或者想快速找到前一个节点，单链表就抓瞎了。我在做嵌入式协议栈的时候，就吃过这个亏——一个数据包解析到一半，发现需要回退到上一个节点重新处理，结果只能从头遍历，效率低得让人抓狂。
所以今天咱们聊聊链表的进阶玩法。双向链表、循环链表，还有Linux内核里那种“变态”的链表实现。这些东西，说白了就是让链表变得更灵活、更高效。
一、双向链表：能进能退
双向链表比单链表多了一个指针——prev，指向前一个节点。结构体长这样：
typedef struct dnode {
int data;
struct dnode *prev;
struct dnode *next;
} dnode_t;嗯，多了一个指针，内存开销大了点，但换来的是操作上的便利。比如删除节点，单链表需要遍历找到前驱节点，双向链表直接通过prev指针就拿到了。
核心操作对比
| 操作 | 单链表 | 双向链表 |
|---|---|---|
| 删除已知节点 | O(n) 需找前驱 | O(1) 直接prev |
| 反向遍历 | 不支持 | O(n) 从尾向前 |
| 插入到节点前 | O(n) 需找前驱 | O(1) 直接操作 |
我在项目中遇到过一个问题：一个实时数据采集系统，需要频繁地在链表中间插入和删除节点。用单链表，每次操作都要从头遍历，CPU占用率直接飙到80%。换成双向链表后，配合一个节点索引表，插入删除基本是常数时间，CPU占用降到了15%。
个人习惯：我写双向链表时，喜欢用一个哑节点（dummy node）作为头节点。这样不管链表是不是空的，操作逻辑都一样，省去了很多边界判断。
二、循环链表：首尾相连
循环链表就是把最后一个节点的next指向头节点。如果是双向循环链表，头节点的prev也指向尾节点。这玩意儿在需要轮询的场景下特别好用。
举个例子，嵌入式系统里的任务调度器。每个任务一个节点，调度器不停地循环遍历，给每个任务分配时间片。用循环链表，遍历到尾部自动回到头部，不需要判断NULL。
// 循环链表的遍历
void traverse_circular(dnode_t *head) {
if (!head) return;
dnode_t *cur = head;
do {
printf("%d ", cur->data);
cur = cur->next;
} while (cur != head);
}注意看，这里用的是do-while而不是while。为什么？因为一开始cur就是head，如果用while，循环体一次都不执行。我曾经在这个坑里栽过跟头——调试了半天，发现链表明明有数据，遍历却什么都没打印。
我曾经犯过的错：在循环链表中做删除操作时，忘记处理只剩一个节点的情况。如果链表只有一个节点，删除后head应该置为NULL，否则next指向自己，形成死循环。这个bug在测试环境跑了三天才被发现，因为那个场景很少触发。
三、内核链表：把链表嵌入到结构体里
Linux内核的链表实现，说实话我第一次看到的时候觉得“这什么鬼”。它不把数据放在链表节点里，而是把链表节点放在数据结构里。看代码：
struct list_head {
struct list_head *next, *prev;
};
// 使用方式
struct my_data {
int value;
char name[32];
struct list_head list; // 链表节点嵌入到结构体中
};这样做的好处是什么？一个结构体可以同时属于多个链表！比如一个网络数据包，既在接收队列里，又在超时重传队列里。你只需要在结构体里放两个list_head成员就行。
内核提供了container_of宏，通过链表节点的地址反推出结构体的地址：
#define container_of(ptr, type, member) \
((type *)((char *)(ptr) - offsetof(type, member)))这个宏的原理很简单：用链表节点的地址减去它在结构体中的偏移量，就得到了结构体的起始地址。嗯，说白了就是指针的加减法。
内核链表的核心API
INIT_LIST_HEAD：初始化链表头list_add：在头部插入list_add_tail：在尾部插入list_del：删除节点list_for_each：遍历链表list_entry：通过节点获取结构体
我在做嵌入式Linux驱动时，大量使用了内核链表。比如管理多个SPI设备，每个设备一个结构体，用链表串起来。驱动加载时动态添加，卸载时逐个删除。代码干净利落，比我自己手写的链表稳定多了。
避坑指南：使用内核链表时，遍历过程中删除节点一定要用list_for_each_safe，它会保存下一个节点的指针。直接用list_for_each删除当前节点，next指针就失效了，程序直接崩溃。我因为这个bug被同事笑话了好几天。
四、三种链表的选型建议
你可能会问，到底该用哪种？我个人的经验是这样的：
- 只需要正向遍历，很少插入删除：单链表就够了，简单省内存
- 需要频繁插入删除，或者需要反向遍历：双向链表，多花8字节换效率
- 需要轮询访问，或者环形缓冲区：循环链表，注意处理空链表
- 写Linux内核模块或驱动：直接用内核链表，别自己造轮子
- 一个结构体需要属于多个链表：内核链表是唯一选择
最后说一句，链表这东西，看着简单，用好了不容易。我见过太多人把链表指针指来指去，最后把自己绕晕了。我的建议是：画图。每次操作前，先在纸上画出指针的变化，确认无误再写代码。这个习惯帮我省了无数调试时间。