怎么运用linux内核函数提供的双向循环链表

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

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

在单链表中，从一已知结点出发，只能访问该结点及其后续结点，无法找到该结点之前的其他结点。而在单循环链表中，虽然从任一结点出发都可访问表中所有结点，但访问该结点的直接前驱结点的时间复杂度为O（n）。另外，在单链表中，若已知某结点的存储位置p，则将一新结点s插入p之前（称为前插），不如插入p之后方便，因为进行前插 *** 作必须知道p的直接前驱位置。同理，删除p本身不如删除p的直接后继方便。因此，由于单链表的缺点，引入了双向链表。

1.双向链表（DoubleLinkedList）的概念双向链表指的是构成链表的每个结点中设立两个指针域：一个指向其直接前驱的指针域prior，一个指向其直接后继的指针域ne*t。这样形成的链表中有两个方向不同的链，故称为双向链表。

2.双向循环链表将双向链表的头结点和尾结点链接起来也能构成循环链表，其称为双向循环链表。

2.双向链表C语言实现的类型定义4.双向链表示意图双向链表示意，如图1所示。

图1双向链表示意

66037663626

---