Linux内核链表实战：从自然数重排掌握list_head核心操作

1. 从一道内核链表题说起：为什么值得认真拆解

第一次看到“用链表存储若干自然数，把 1 2 3 4 5 6 7 8 9 重排成 1 3 5 7 9 8 6 4 2”这个题目时，很多人第一反应是“这不就是个数组排序题吗，开个数组分奇偶两半，奇数正着放、偶数倒着放，两分钟搞定”。如果只是应付一道普通作业，这么想没错。但题目里明明白白写着“Linux内核链表”，这就把问题的性质完全改变了——它考的不是排序算法，而是你对内核链表这套基础设施的理解和运用能力。

Linux内核链表是内核源码里使用频率最高的数据结构之一，进程管理、设备驱动、文件系统、网络协议栈，几乎无处不在。它和教科书上那种“数据域+指针域”的链表长得完全不一样，核心思想是把链表节点嵌入到业务数据结构内部，让链表只负责“串起来”，不负责“存什么”。这个设计带来的最大好处是：同一套链表操作代码可以复用到任何结构体上，不需要为每种数据类型重写一遍增删改查。

这道题的实际价值在于，它用一个极简的场景（存储自然数并重排）逼着你去实践内核链表的三件核心事情：怎么定义节点、怎么遍历、怎么在遍历过程中安全地移动节点。尤其是最后一步“重排”，涉及节点摘除和重新插入，是内核链表操作里最容易出错的地方，也是面试和实际开发中区分“会用”和“用对”的分水岭。

这篇文章适合三类人看：正在学操作系统或内核模块开发的学生、想从应用层转向底层开发的工程师、以及工作中需要维护内核态代码但链表操作总是写不利索的从业者。我会从设计思路讲到具体实现，把每个关键决策背后的原因说清楚，再把我自己踩过的坑和排查经验一并分享出来。整篇内容基于常见的内核链表实践展开，代码可以直接参考复现。

2. 内核链表到底和普通链表差在哪

2.1 普通链表的痛点：每换一种数据就得重写一遍

先回忆一下教科书上的单链表长什么样。通常是这样的结构：

struct node { int data; struct node *next; };

这个结构把数据域和指针域绑死在一起。如果现在要存一个字符串，就得再定义一个struct string_node，把int data换成char *data，然后增删查改的函数全部重写一遍。数据种类一多，代码里就充斥着一堆功能重复、只是类型不同的链表实现。这是典型的代码冗余，维护起来非常痛苦。

更麻烦的是，当业务结构体本身很复杂时，你没法把一个已经存在的结构体“变成”链表节点。比如你有一个表示进程的结构体，里面几十个字段，你不可能为了把它挂到链表上，就在里面塞一个next指针然后到处传递这个结构体的指针——因为一旦你要把同一个进程同时挂到“就绪队列”和“等待队列”两个链表上，一个next指针根本不够用。

2.2 内核链表的解法：把“钩子”嵌进结构体

内核链表换了个思路。它定义了一个纯粹的链表节点，里面只有前后指针，没有任何数据：

struct list_head { struct list_head *next, *prev; };

注意这是双向循环链表，next和prev都有，而且头节点的prev指向尾节点，尾节点的next指向头节点，形成一个环。这个设计的好处后面会讲。

用的时候，你把它作为一个成员嵌入到自己的业务结构体里：

struct my_data { int value; struct list_head list; };

这样一来，链表节点和业务数据是“包含”关系，而不是“绑定”关系。同一个struct my_data里可以放多个list_head成员，就能同时挂到多个链表上。链表操作函数只认list_head，不关心外面包的是什么，通用性直接拉满。

2.3 最关键的宏：container_of 和 list_entry

嵌入式的设计带来一个新问题：我手里拿到的是一个struct list_head *指针，怎么反推出包含它的那个struct my_data *？答案就是内核里大名鼎鼎的container_of宏。它的原理是根据成员在结构体中的偏移量，用指针减法算出结构体的起始地址。

内核链表在此基础上封装了list_entry（新版本叫list_first_entry等系列），用法是：

struct my_data *p = list_entry(ptr, struct my_data, list);

意思是：ptr是一个指向list成员的指针，list是struct my_data里的成员名，请帮我算出整个struct my_data的地址。这个宏是理解内核链表的钥匙，不理解它，后面遍历和重排都会看得很懵。

提示：container_of依赖编译器对结构体成员偏移的计算，所以成员名必须写对，写错了编译能过但运行时会拿到错误地址，这是新手最常见的坑之一。

2.4 为什么是循环链表而不是单链表

很多人会问，双向循环链表是不是过度设计了。实际用下来，循环结构带来两个实打实的便利。第一，头节点的prev直接指向尾节点，要在尾部插入元素时不需要从头遍历到尾，O(1) 就能拿到尾指针。第二，遍历的终止条件是“回到起点”，不需要额外判断 NULL，代码更统一。对于这道重排题来说，我们需要频繁地在头部和尾部之间搬移节点，循环双向结构让这些操作都变得非常顺手。

3. 重排需求拆解：奇数升序偶数降序怎么落地

3.1 先明确目标序列的规律

原始序列是 1 到 9 的自然数升序排列。目标序列是 1 3 5 7 9 8 6 4 2。拆开看，前半段是所有奇数，保持升序；后半段是所有偶数，但是降序。所以本质上要做两件事：按奇偶把节点分成两组，奇数组保持原序，偶数组反转顺序，最后把偶数组接到奇数组后面。

这里有个容易忽略的点：题目说的是“若干自然数”，不一定非得是 1 到 9 连续。可能是任意一组自然数，比如 3 1 4 1 5 9 2 6。所以算法不能假设输入是连续递增的，得按通用情况处理。不过为了和题目示例对齐，我们后面用 1 到 9 来演示，同时说明通用处理方式。

3.2 三种可行思路的对比

面对这个需求，脑子里至少能冒出三种做法，各有取舍。

第一种是新建两个链表，遍历原链表，奇数尾插到奇数链表，偶数头插到偶数链表，最后拼接。头插天然实现逆序，所以偶数链表自动就是降序。这种做法逻辑最清晰，但需要额外的头节点，内存开销略大。

第二种是原地重排，不新建链表，直接在原链表上把偶数节点摘下来，重新插入到合适位置。这种做法省内存，但指针操作复杂，容易断链。

第三种是先全部摘下来再按规则重建，相当于把原链表拆散，然后按目标顺序一个个重新挂上去。这种做法介于前两者之间，逻辑比原地重排简单，又比新建链表省一点。

考虑到这是内核链表练习题，我倾向于选第二种原地重排，因为它最能锻炼对list_del和list_add系列函数的掌握，也最贴近真实内核代码的风格。但我会在实现里把关键步骤拆细，避免断链。

3.3 关键操作函数速查

在动手之前，先把要用到的内核链表函数列清楚，这些是后面代码的基础。

这张表建议存下来，写内核链表代码时对着看，能省很多查文档的时间。

4. 完整实现：从建表到重排的每一步

4.1 数据结构定义与初始化

先定义业务结构体和头节点。为了演示清晰，业务数据就存一个整数。

#include <linux/list.h> #include <linux/kernel.h> #include <linux/slab.h> struct num_node { int value; struct list_head list; }; static LIST_HEAD(num_list); // 定义并初始化全局头节点

LIST_HEAD宏等价于定义一个struct list_head并调用INIT_LIST_HEAD，一步到位。如果是在函数内部用，就写成：

struct list_head head; INIT_LIST_HEAD(&head);

初始化这一步千万别省。未初始化的list_head里是垃圾值，直接list_add进去会导致指针指向随机内存，轻则数据错乱，重则内核崩溃。我见过有人图省事跳过初始化，调试了半天才发现问题出在这里。

4.2 建表：把自然数挂上去

假设我们要插入 1 到 9，用尾插保持升序：

int i; for (i = 1; i <= 9; i++) { struct num_node *n = kmalloc(sizeof(*n), GFP_KERNEL); if (!n) return -ENOMEM; n->value = i; INIT_LIST_HEAD(&n->list); // 单个节点也要初始化 list_add_tail(&n->list, &num_list); }

这里有两个细节值得说。第一，每个新节点的list成员也要INIT_LIST_HEAD，虽然list_add_tail会覆盖next和prev，但养成初始化的习惯能避免很多隐蔽问题。第二，kmalloc分配的内存不会自动清零，所以value必须显式赋值，不能指望它是 0。

建完表后，链表里就是 1 2 3 4 5 6 7 8 9，头节点的next指向 1，prev指向 9。

4.3 遍历打印：先确认建表正确

在重排之前，先写个打印函数验证一下链表内容，这是排查问题的基本习惯。

static void print_list(struct list_head *head) { struct num_node *pos; list_for_each_entry(pos, head, list) { printk(KERN_INFO "%d ", pos->value); } printk(KERN_INFO "\n"); }

list_for_each_entry是遍历的常用宏，它内部自动做了list_entry转换，用起来比手动list_for_each加list_entry方便。打印出来应该是1 2 3 4 5 6 7 8 9，如果顺序不对或者缺元素，说明建表阶段就有问题，先别往下走。

4.4 重排核心逻辑：摘偶数、头插、拼接

现在进入正题。我的思路是：遍历原链表，遇到偶数就把它从当前位置摘下来，头插到一个临时的偶数链表里。因为头插是逆序的，遍历完原链表后，偶数链表自然就是降序。最后把偶数链表整体接到奇数链表（也就是原链表剩下的部分）后面。

static void rearrange(struct list_head *head) { struct list_head even_head; struct num_node *pos, *n; INIT_LIST_HEAD(&even_head); list_for_each_entry_safe(pos, n, head, list) { if (pos->value % 2 == 0) { list_del(&pos->list); // 从原链表摘除 list_add(&pos->list, &even_head); // 头插到偶数链表 } } // 把偶数链表整体拼到奇数链表尾部 list_splice_tail(&even_head, head); }

这段代码不长，但每一行都有讲究。先说list_for_each_entry_safe，它比普通遍历多了一个n参数，用来暂存下一个节点。为什么需要？因为我们在循环体里对pos执行了list_del，摘除后pos->list.next就不可靠了，如果还用普通遍历，下一轮就会访问到错误地址。_safe版本提前把下一个节点存到n里，保证遍历安全。这是内核链表操作里最重要的一个习惯，凡是遍历中可能删除节点，就必须用_safe版本。

再说list_del和list_add的配合。list_del只是把节点从链表里摘出来，节点本身的内存还在，list_add再把它挂到新链表上。这两个操作合起来就是“移动节点”。注意list_del之后节点的next和prev会被设成特殊值（在开启调试时会指向毒药地址），所以摘除后不要再去读它的前后指针。

最后list_splice_tail把even_head里的所有节点接到head的尾部，并重新初始化even_head。这个函数比手动遍历一个个搬要高效，也更不容易出错。

4.5 验证结果与内存释放

重排完再调用一次print_list，应该输出1 3 5 7 9 8 6 4 2。如果结果对了，别忘了释放内存：

static void free_list(struct list_head *head) { struct num_node *pos, *n; list_for_each_entry_safe(pos, n, head, list) { list_del(&pos->list); kfree(pos); } }

释放同样要用_safe版本，因为循环体里删除了当前节点。这个函数写不好会导致内存泄漏或者释放后访问，是内核模块里常见的资源管理问题。

5. 踩坑记录与排查经验

5.1 遍历中删除节点导致崩溃

这是最经典的坑。我早期写类似逻辑时，用了list_for_each_entry而不是_safe版本，结果在摘除偶数节点后，下一轮循环访问pos->list.next拿到的是已经被改写的指针，直接触发内核 oops。排查这类问题有个技巧：看崩溃地址是不是一个很奇怪的值（比如0xdead000000000000这种），如果是，基本可以确定是访问了已删除节点的指针。解决办法就是无脑用_safe版本，养成肌肉记忆。

5.2 忘记初始化头节点

另一个高频问题是头节点没初始化。表现是插入第一个节点时看起来正常，插入第二个就乱套，或者遍历时死循环。原因是未初始化的head->next指向随机地址，list_add_tail会试图去修改那个随机地址的prev，行为完全不可预测。用LIST_HEAD宏或者显式INIT_LIST_HEAD都能避免，关键是别偷懒。

5.3 头插和尾插用反导致顺序错误

这道题里，奇数要保持升序，所以遍历时不能动它们，让它们留在原链表里自然保持顺序。偶数要降序，所以用头插。如果偶数也用尾插，结果就会变成1 3 5 7 9 2 4 6 8，偶数部分顺序反了。判断用哪种插入方式，就看你要的顺序和遍历顺序是一致还是相反：一致用尾插，相反用头插。这个规律记住，能省很多试错时间。

5.4 常见问题速查表

5.5 一个容易被忽略的调试技巧

内核代码不像用户态程序那样能随便加printf，但printk配合日志级别很好用。我习惯在关键步骤后打印链表状态，比如建表后打一次、摘除循环每轮打一次、拼接后再打一次。虽然日志会多，但定位问题时能一眼看出是哪一步开始不对。另外，如果是在可加载模块里调试，记得用dmesg -w实时看输出，比反复dmesg | tail高效得多。

6. 从这道题延伸出去的实际应用

6.1 内核里真实的重排场景

这道题看着像玩具，但“按条件分组再重组”在内核里非常常见。比如进程调度器需要把进程按优先级分组，网络协议栈需要把数据包按类型分流，设备驱动需要把请求按方向排队。它们的共同点是：数据节点本身已经在某个链表上，需要根据某个字段的值把它们重新组织到不同的队列里。这时候list_del加list_add的组合就是标准操作，和这道题的偶数摘除逻辑本质相同。

6.2 多链表挂载的实战价值

前面提到一个结构体可以嵌多个list_head，从而同时挂在多个链表上。这个特性在实际开发中非常有用。比如一个任务节点，既要在“待处理队列”里，又要在“按优先级排序的队列”里，就可以定义两个list_head成员，分别挂到两个链表。操作时要注意，从其中一个链表摘除不影响另一个，但释放内存前必须确保从所有链表都摘干净，否则会出现悬空指针。这是比单链表复杂的地方，也是内核链表灵活性的代价。

6.3 性能上的考量

有人可能担心list_del加list_add这种“摘了再挂”的操作会不会很慢。实际上这两个操作都是 O(1) 的，只改几个指针，不涉及数据搬移。整道题的时间复杂度是 O(n)，遍历一遍就完成重排，空间上除了一个临时头节点没有额外分配。这比“新建两个数组再拷贝”的做法在内存受限的内核环境里优势明显。当然，如果数据量极小，两种做法差别不大，但养成 O(1) 移动节点的习惯，在处理大规模链表时收益很大。

6.4 如果要支持任意自然数序列

题目示例是 1 到 9，但真实场景里输入可能是乱序的。如果输入是3 1 4 1 5 9 2 6，要求奇数升序、偶数降序，那就不能只靠“保持原序”了，得在插入时做排序。一种做法是插入奇数时用list_add找到合适位置插入，保持升序；偶数头插到偶数链表后，再对偶数链表做一次排序。另一种做法是先把所有节点摘下来，用两个临时链表分别收集奇偶，奇数链表排序后拼接偶数链表。具体选哪种看数据规模和性能要求，但核心的链表操作函数还是那几个，万变不离其宗。

7. 几个让代码更稳的实操建议

写内核链表代码，我总结了几个能显著降低出错率的习惯，分享出来。

第一，任何可能修改链表的遍历都用_safe版本。不要试图判断“这次循环应该不会删节点”就省掉n参数，需求一变就容易出事，统一用_safe最省心。

第二，摘除节点后立刻处理，不要留着悬空指针。list_del之后要么马上list_add到新位置，要么马上kfree，中间不要插入可能出错的逻辑。悬空指针是内核 bug 的头号来源。

第三，头节点永远用宏初始化。LIST_HEAD一行搞定，比手动写两行赋值不容易漏。局部变量用INIT_LIST_HEAD，别嫌麻烦。

第四，调试时先验证链表结构再验证数据。先打印节点个数和顺序，确认链表本身没问题，再看value对不对。如果链表结构都乱了，纠结数据没意义。

第五，拼接操作用list_splice系列而不是手动遍历。内核提供的拼接函数已经处理好了边界情况，手动搬容易在头尾衔接处出错，尤其是空链表的情况。

这道题我前后用不同思路实现过三四遍，每次都能发现之前没注意的细节。内核链表这套东西，看文档觉得简单，真动手写才会发现坑都在细节里。把这道题吃透，再去写进程队列、设备请求队列之类的代码，会顺畅很多。后续如果想继续深入，可以试试把单链表版本改成支持多链表挂载，或者加上按值查找和删除的功能，都是很好的练手方向。