非侵入式鏈表

非侵入式鏈表是一種鏈表數據結構，其中每個元素（節點）并不需要自己包含指向前后節點的指針。鏈表的結構和節點的存儲是分開的，鏈表容器會單獨管理這些指針。

常見的非侵入式鏈表節點可以由以下所示，即，在鏈表節點中包含數據：

其中每個節點都形如：

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);

參考鏈接

1. https://hcoona.github.io/Data-Structure/instrusive-linked-list-summary/
2. https://zhiqiang.org/coding/boost-intrusive-containers.html