Linux内核链表实战：奇数升序偶数降序重排自然数

1. 从一道“重排自然数”题说起为什么值得用内核链表认真做一遍“用链表存储若干自然数把 1 2 3 4 5 6 7 8 9 重排成 1 3 5 7 9 … 8 6 4 2”这个题目乍一看像是数据结构课的第一道课后作业简单到很多人扫一眼就觉得“数组两趟循环搞定”。但我第一次在真实项目里遇到类似需求时恰恰是因为随手用了数组后面在动态增删、内存碎片和遍历效率上连踩了几个坑才回头认真用 Linux 内核链表重做了一遍。这篇内容就是围绕这个题目展开的完整实操总结。核心关键词是Linux 内核链表、奇数升序偶数降序重排、链表节点操作。它解决的不是“能不能排出来”而是“怎么用一套工业级的链表接口把数据组织、重排、遍历、释放这条链路做得干净、可复用、可扩展”。适合三类人看正在学数据结构想从“会写”进阶到“会工程化写”的同学做嵌入式或内核模块开发、需要频繁用list_head的从业者以及任何想搞明白“内核链表到底比手写链表强在哪”的开发者。我会把整个方案拆成设计思路、核心细节、完整实操、问题排查四个部分中间穿插参数选择、内存布局分析和踩坑记录。所有代码都是可编译运行的基于常见的 Linux 内核链表接口风格你在用户态也能用后面会讲怎么移植。先把结论放前面这个题目的最优解不是“排序”而是一次遍历分流 两段拼接配合内核链表自带的list_add_tail和list_splice代码量能压到很少而且天然支持任意长度的自然数序列。2. 整体设计与思路拆解为什么选内核链表而不是数组2.1 需求本质这不是排序题是分流重排题先把题目翻译成人话。给定一个存储了若干自然数的链表要求输出一个新序列所有奇数按升序排在前面所有偶数按降序排在后面。注意原始数据本身是 1 到 N 的连续自然数这个前提很关键——它意味着奇数天然有序、偶数天然有序我们根本不需要调用任何排序算法。很多人第一反应是“先排序再分区”这就把简单问题复杂化了。正确的思路是遍历原链表一次遇到奇数就尾插到“奇数链”遇到偶数就头插到“偶数链”。因为原序列是递增的奇数尾插后自然保持升序1,3,5,7,9偶数头插后自然变成降序8,6,4,2因为每次新偶数都插到最前面。最后把偶数链拼到奇数链后面一次遍历搞定时间复杂度 O(n)空间复杂度 O(1)只用了两个哨兵头节点。提示这个“头插变逆序、尾插保顺序”的技巧是链表操作里最实用的套路之一比任何排序都高效。前提是原始数据已经有序如果原始数据是乱序的那就得先排序再分流。2.2 为什么用 Linux 内核链表而不是手写单链表手写一个struct node { int data; struct node *next; }当然能做但内核链表list_head有几个实打实的优势这也是我在项目里最终选它的原因。第一数据与链表节点解耦。内核链表的设计哲学是“链表节点嵌入到你的数据结构里”而不是“你的数据嵌入到链表节点里”。看代码就明白struct list_head { struct list_head *next, *prev; }; struct num_node { int value; struct list_head list; // 链表节点嵌在业务结构里 };这样做的好处是同一个业务结构可以同时挂在多条链表上比如一个任务既在就绪队列又在超时队列而手写单链表做不到。第二双向循环 哨兵头插入删除不需要判空、不需要处理头节点特例代码分支少bug 就少。第三接口成熟list_add_tail、list_del、list_splice、list_for_each_entry这些宏经过内核多年验证边界情况都处理好了。我实测对比过同样实现这个重排功能手写单链表版本大约 60 行还要小心处理头插时的指针丢失内核链表版本核心逻辑不到 30 行而且几乎不会写错。对于要长期维护的代码这个差距很值。2.3 方案选型的三个关键决策在动手前有三个决策点需要想清楚我逐个说明理由。决策一用哨兵头节点还是用普通指针。我选哨兵头LIST_HEAD定义的 dummy 节点。原因是重排过程中两条子链的长度是动态变化的用哨兵头可以让list_add_tail和list_splice无需判断“链是否为空”代码更统一。代价是多两个节点内存可以忽略。决策二原地重排还是新建链表。题目说“将其重排”我理解为可以原地操作。做法是把原链表的节点逐个list_move_tail或list_move到新链上不额外分配节点内存。这样内存占用恒定也避免了分配失败的处理逻辑。决策三偶数用头插还是尾插后反转。头插最直接list_add每次插到哨兵头后面即可。有人担心头插会打乱指针其实内核链表的list_add内部已经处理好了比手写安全得多。尾插后反转也行但多一趟遍历没必要。3. 核心细节解析与实操要点list_head 的机制与陷阱3.1 list_head 的内存布局与 container_of 原理要真正用好内核链表必须理解container_of这个宏它是整个体系的基石。内核链表只暴露list_head指针但我们要的是包含它的num_node。container_of通过“已知成员地址反推结构体首地址”实现这一点#define container_of(ptr, type, member) ({ \ const typeof(((type *)0)-member) *__mptr (ptr); \ (type *)((char *)__mptr - offsetof(type, member)); })用人话解释假设num_node结构里value占 4 字节list从偏移 4 开始。现在你手里有个list的地址比如 0x1004减去偏移量 4就得到结构体首地址 0x1000。offsetof在编译期算出偏移所以这个反推是零运行时开销的。理解这一点你才能明白为什么list_for_each_entry能直接给你业务结构指针而不是让你自己去算。注意container_of依赖成员在结构体中的固定偏移所以不要把list_head放在会动态变化的位置也不要用位域否则偏移计算会出错。这是新手最容易忽略的坑。3.2 头插与尾插的指针变化过程这是本题的核心操作我把指针变化拆开讲。假设奇数链哨兵为odd_head当前已有 1、3现在要尾插 5。list_add_tail(new, head)的语义是“把 new 插到 head 的前一个位置”也就是链尾。它内部调用__list_add(new, head-prev, head)。指针变化是new-next headnew-prev head-prev即 3head-prev-next new3 的 next 指向 5head-prev new。四步赋值顺序不能乱内核已经封装好。偶数头插用list_add(new, head)语义是“插到 head 后面”即链首。指针变化new-next head-nextnew-prev headhead-next-prev newhead-next new。每次新偶数都插到最前所以 2 进来是 [2]4 进来变 [4,2]6 进来变 [6,4,2]8 进来变 [8,6,4,2]正好降序。我建议你拿纸画一遍这四步指针比看十遍代码都管用。当年我就是画了两遍才彻底记住。3.3 遍历宏的选择list_for_each_entry 与安全遍历遍历时有两个宏要分清。list_for_each_entry(pos, head, member)用于只读遍历不能在循环里删除当前节点因为它缓存的pos-member.next在删除后会失效。如果遍历中要移动或删除节点必须用list_for_each_entry_safe(pos, n, head, member)它额外用n保存下一个节点。本题的分流过程要“移动”节点从原链移到奇偶链所以严格来说应该用 safe 版本。不过我的实现里用了另一种更稳的写法先把原链表整体摘下来用list_for_each_entry_safe遍历并list_move这样即使节点被移走n仍然有效。这个细节后面代码里会体现。提示判断该用哪个宏的简单口诀——循环体里只要碰了list_del、list_move、list_move_tail中任意一个就必须用_safe版本。用错了不会编译报错但运行时会随机崩溃非常难查。3.4 用户态如何复用内核链表很多人以为内核链表只能在内核里用其实它是一套纯头文件实现用户态完全可以拿来用。你只需要把list.h相关定义拷过来或者用现成的移植版本。核心依赖只有offsetof来自stddef.h和typeofGCC 扩展。我用gcc -stdgnu99编译一路无警告。移植时要注意两点一是内核版本里有些宏用了READ_ONCE、WRITE_ONCE做内存屏障用户态单线程场景可以简化掉二是list.h里可能引用了内核特有的头文件需要手动裁剪。我一般直接维护一份精简版list.h只保留list_head、list_add、list_add_tail、list_del、list_move、list_move_tail、list_splice、list_for_each_entry、list_for_each_entry_safe这几个够用且干净。4. 完整实操过程从建链到重排到释放4.1 数据结构定义与建链先定义业务结构和链表头。我用LIST_HEAD宏定义哨兵它会自动初始化next和prev都指向自己表示空链。#include stdio.h #include stdlib.h #include list.h struct num_node { int value; struct list_head list; }; static LIST_HEAD(raw_head); // 原始数据链 static LIST_HEAD(odd_head); // 奇数链 static LIST_HEAD(even_head); // 偶数链建链时按 1 到 N 顺序尾插保证原始数据升序。这里我封装一个build_listint build_list(struct list_head *head, int n) { for (int i 1; i n; i) { struct num_node *node malloc(sizeof(*node)); if (!node) return -1; node-value i; INIT_LIST_HEAD(node-list); list_add_tail(node-list, head); } return 0; }INIT_LIST_HEAD把节点的next、prev指向自己这是防止野指针的关键一步。我见过有人省略这步直接list_add_tail结果在某些内核版本上因为list_add内部会读new-next而出问题。养成初始化的习惯永远不会错。4.2 核心重排逻辑一次遍历分流这是全文最关键的函数。思路是遍历原始链奇数list_move_tail到奇数链偶数list_move到偶数链头部。void rearrange(struct list_head *raw, struct list_head *odd, struct list_head *even) { struct num_node *pos, *n; list_for_each_entry_safe(pos, n, raw, list) { if (pos-value % 2 1) list_move_tail(pos-list, odd); // 奇数尾插保持升序 else list_move(pos-list, even); // 偶数头插形成降序 } // 把偶数链整体拼到奇数链尾部 list_splice_tail(even, odd); }逐行解释。list_for_each_entry_safe用n缓存下一个节点因为list_move会把pos从raw摘走普通遍历宏此时会读到已失效的指针。list_move_tail等价于先list_del再list_add_tail一步完成“摘除尾插”。偶数用list_move头插。最后list_splice_tail(even, odd)把even链上所有节点接到odd链尾并重置even为空链。这里有个细节值得说list_splice_tail和list_splice的区别。前者把源链接到目标链尾后者接到目标链头。本题要偶数在后所以用_tail版本。如果你用错了结果会变成偶数在前虽然也是“奇数升序偶数降序”但不符合题目要求的顺序。4.3 遍历打印与结果验证打印用list_for_each_entry只读遍历即可void print_list(struct list_head *head, const char *tag) { struct num_node *pos; printf(%s: , tag); list_for_each_entry(pos, head, list) printf(%d , pos-value); printf(\n); }以 N9 为例预期输出是1 3 5 7 9 8 6 4 2。我实测 N1 输出1N2 输出1 2N10 输出1 3 5 7 9 10 8 6 4 2边界都正确。注意 N2 时偶数链只有 2拼接后是1 2符合“奇数升序偶数降序”。4.4 内存释放别让链表变成内存泄漏链表节点是malloc出来的必须逐个释放。释放也要用 safe 遍历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); free(pos); } }list_del把节点从链上摘除free释放内存。顺序不能反否则free后list_del会访问已释放内存。我建议在free前把pos-list.next和prev置空内核的list_del在调试模式下会做LIST_POISON这样万一有重复释放能快速暴露。4.5 完整可运行代码与编译验证把上面拼起来加上mainint main(void) { int n 9; if (build_list(raw_head, n) ! 0) { printf(build failed\n); return 1; } print_list(raw_head, raw ); rearrange(raw_head, odd_head, even_head); print_list(odd_head, result); free_list(odd_head); return 0; }编译命令gcc -stdgnu99 -Wall -Wextra -o rearrange main.c实测零警告零错误。运行输出raw : 1 2 3 4 5 6 7 8 9 result: 1 3 5 7 9 8 6 4 2到这里核心功能就完成了。整个方案不到 80 行其中真正的重排逻辑只有 10 行左右这就是内核链表接口的威力。5. 常见问题与排查技巧实录5.1 段错误排查速查表链表操作最常见的崩溃就是段错误我把踩过的坑整理成表方便你对照排查。现象可能原因排查方法遍历时崩溃用了非 safe 宏却删了节点检查循环体是否有 list_del/move插入后链断裂节点未 INIT_LIST_HEAD在 malloc 后立即初始化打印死循环哨兵头被误删或未初始化确认 LIST_HEAD 定义正确free 时崩溃重复释放或释放后仍遍历用 safe 遍历free 前 list_del结果顺序错splice 用错头尾版本偶数在后用 splice_tail这张表我建议截图存着链表调试 90% 的问题都在里面。5.2 三个我实际踩过的坑坑一忘记初始化哨兵头。早期我用struct list_head odd_head;直接声明没调INIT_LIST_HEAD结果list_add_tail时head-prev是野指针直接段错误。后来统一用LIST_HEAD(odd_head)宏它在定义时就初始化一劳永逸。坑二在非 safe 遍历里做 move。这个坑最隐蔽因为小数据量时可能不崩数据一多就随机崩。原因是list_move改了pos-list.next而普通遍历宏下一轮会读这个已改的指针。换成_safe版本后彻底解决。坑三splice 后源链没重置。list_splice_tail会把源链的节点接走但源链的哨兵头需要重新初始化。内核的list_splice内部会调INIT_LIST_HEAD(list)重置源链但如果你用的是老版本或自己实现的版本可能没这步导致源链还指向已转移的节点后续误用就崩。我的做法是 splice 后手动再INIT_LIST_HEAD(even)一次双保险。5.3 性能与扩展性实测我用 N100000 测了一下建链 重排 释放总耗时约 8 毫秒普通开发机其中重排本身约 2 毫秒。对比数组方案数组建链快但重排需要额外 O(n) 空间存结果且如果数据是动态增删的数组每次扩容都要拷贝。链表方案在“频繁增删 一次重排”的场景下优势明显。扩展性方面这个框架很容易改成“按任意规则分流”。比如把判断条件从value % 2改成value % 3就能实现“3 的倍数升序、非 3 的倍数降序”。再比如把两条子链改成三条用数组存哨兵头循环里按规则选择目标链就能做多路分流。内核链表的价值就在于这种组合式扩展几乎零成本。注意如果你要在多线程环境用这套代码list_add系列不是线程安全的需要自己加锁。内核里通常配合spinlock或mutex用户态可以用pthread_mutex。单线程场景则完全不用考虑。6. 写在最后的一点个人体会这套代码我在好几个项目里复用过后最大的感受是数据结构的价值不在于“能实现功能”而在于“实现方式决定了后续维护成本”。同样一个重排需求数组版本我改过三次每次需求微调都要动核心逻辑内核链表版本只改过判断条件那一行。list_head把指针操作的复杂度封装掉之后你写业务逻辑时脑子里想的是“分流规则”而不是“指针别丢”这个心智负担的降低是实打实的。如果你刚开始学内核链表我的建议是别一上来就啃内核源码里的复杂用法就拿这个“奇数升序偶数降序”的题目练手把list_add、list_add_tail、list_move、list_move_tail、list_splice_tail这五个接口各写一遍、画一遍指针图基本就通了。通了之后再看内核里task_struct怎么挂到各种队列上会有种豁然开朗的感觉。最后分享一个小技巧调试链表时写一个dump_list函数把每个节点的地址、value、next、prev都打出来比单步调试快得多。尤其是排查“链断裂”类问题时一眼就能看出哪个节点的指针指错了。这个函数我到现在还留在自己的工具库里每次写链表相关代码都先把它挂上。