非侵入式链表
非侵入式链表是一种链表数据结构,其中每个元素(节点)并不需要自己包含指向前后节点的指针。链表的结构和节点的存储是分开的,链表容器会单独管理这些指针。
常见的非侵入式链表节点可以由以下所示,即,在链表节点中包含数据:
其中每个节点都形如:
struct Node {
T data;
Node* prev;
Node* next;
};
STL标准库就使用的是非侵入式容器。
侵入式链表
侵入式链表是一种链表数据结构,其中每个元素(节点)本身就包含了指向前后节点的指针(prev 和 next)。也就是说,链表的结构是“侵入”到节点内部的,节点必须事先包含这些指针。
侵入式list与STL标准库中的list不同.STL标准库中的list容器将data与prev指针和next指针紧耦合,这就导致每向list中插入一个新元素就要涉及到内存的分配,这对于在堆上分配的内存而言是一种时间浪费。
template <typename T>
struct IntrusiveListNode {
IntrusiveListNode* prev;
IntrusiveListNode* next;
T* owner;
};
struct UserData {
// ...
InstruiveListNode list;
};
优点:
- 更好的data locality:非侵入式结构std::list<T*>遍历过程中需要对T*解引用才能访问T内部数据,但侵入式结构的next和T内部的数据结构是放在一起的,无需额外解引用。
- 更友好的API:拿到数据后就可以直接将这个节点从链表去除
- 需要用户自己管理数据节点生命周期
应用举例:Linux源码的侵入式链表结构:
struct list_head {
struct list_head *next, *prev;
};
//使用list_head的调度模块
struct task_group {
// 省略一些业务逻辑
struct list_head list;
};
/*
* Default task group.
* Every task in system belongs to this group at bootup.
*/
struct task_group root_task_group;
LIST_HEAD(task_groups);
list_add(&root_task_group.list, &task_groups);
参考链接
- https://hcoona.github.io/Data-Structure/instrusive-linked-list-summary/
- https://zhiqiang.org/coding/boost-intrusive-containers.html