Linux 内核双链表的实现太精妙了
通过设计前驱和后继两个指针域，双链表可以从两个方向遍历。如果打乱前驱、后继的依赖关系，就可以构成"二叉树"；如果再让首节点的前驱指向链表尾节点、尾节点的后继指向首节点（图中虚线部分），就构成了循环链表；如果设计更多的指针域，就可以构成各种复杂的树状数据结构。
这是 Linux 内核双链表，这个设计真是太牛了！
想了解一下，在操作系统内核具体实现中，还有哪些精妙的思想？站内各位大牛欢迎讨论
败走少年之歌
9 years, 1 month ago
Answers
在Linux内核里，中断处理用到了二分查找，垃圾收集用到了归并排序，字符串匹配用KMP，任务调度用红黑树。给你一个链接，你看看就知道了 http://cstheory.stackexchange.com/questions/19759/core-algorithms-deployed/
为了福利..
answered 9 years, 6 months ago
在Linux内核里，中断处理用到了二分查找，垃圾收集用到了归并排序，字符串匹配用KMP，任务调度用红黑树。给你一个链接，你看看就知道了 http://cstheory.stackexchange.com/questions/19759/core-algorithms-deployed/
影子dē逆袭
answered 9 years, 4 months ago
