Re:Zig's new LinkedList API (it's time to learn fieldParentPtr)
by _huayra_ on Monday April 14, 2025 @05:11PM
(#43686385)
At the byte level, it's quite possible the layouts are the same. However, an "intrusive data structure" means that the nodes themselves are the data.
In other words, intrusive is like this:
struct T : NodeType<T>
{
// T data
NodeType<T> next, prev;
};
whereas non-intrusive data structures the T's are not the nodes themselves
struct NodeType<T>
{
NodeType<T> next, prev;
T t;
};
Doing non-intrusive means you need to own the lifecycle of the nodes (and make them copyable, move-constructible, or some combo thereof). Intrusive means that the caller can manage the nodes' lifecycles and just say "here's a node, I promise it'll live while the list is still alive" and have that node be on the stack, heap, static, etc.
In other words, intrusive is like this:
struct T : NodeType<T> { // T data NodeType<T> next, prev; };
whereas non-intrusive data structures the T's are not the nodes themselves
struct NodeType<T> { NodeType<T> next, prev; T t; };
Doing non-intrusive means you need to own the lifecycle of the nodes (and make them copyable, move-constructible, or some combo thereof). Intrusive means that the caller can manage the nodes' lifecycles and just say "here's a node, I promise it'll live while the list is still alive" and have that node be on the stack, heap, static, etc.