linux内核 为什么大量使用双向链表

在linux内核中，有大量的数据结构需要用到双循环链表，例如进程、文件、模块、页面等。若采用双循环链表的传统实现方式，需要为这些数据结构维护各自的链表，并且为每个链表都要设计插入、删除等 *** 作函数。因为用来维持链表的next和prev指针指向对应类型的对象，因此一种数据结构的链表 *** 作函数不能用于 *** 作其它数据结构的链表。

最典型的，就是task_struct中，进程的相互关系。

每个进程都有自己的task_struct，同胞进程之间task_struct就是用双向链表连接起来的。

去查下内核编程指南，里面有说到

双联就是双向的链表，每一个节点有一个void *prev和void *next。数据结构的书上都有。

双向链表的插入和删除 *** 作很快，如果是单向的，需要从头节点遍历。

prev和next还有一些变种，都是用来寻找前后的节点的。

---