benefits of abstracting and separating node types from payloads
If you mean being able to a generic `list<foo>` type (whether by C++ templates, macros, or good old void* casts), it's more than that.
The benefit of non-intrusive is being able to create/manipulate/pass around multiple collections pointing to same payloads, without disturbing the payloads or the other collections in any way¹. That makes it easier to return and manipulate collections functionally (both in the narrow immutable sense, but also in the wider "treat collections like _values_ sense)... The deepest benefit arising from that I suppose is code modularity: different code areas need not be aware of each other's existence.
That all obviously comes at some tradeoff to performance. By definition, not having a full picture of the pathways your data travels means you can't choose the fastest representation!
¹The cheat is GC. For multiple unconnected collections to point to same payload, you need ref counting, or mark&sweep or similar to control its lifetime. Technically, GC does disturb the objects it's tracking (though that's well abstracted from other code).
However, you're largely right that specifically linked lists are rarely a good choice for non-intrusive collections => Arrays usually beat them, and if not then hash sets.
(LISP & ML & Haskell do stick to lists for tail sharing — a choice which is arguably outdated by growing CPU / mem random access gap. I suppose Clojure's persistent vectors are an improvement.)
Comments
If you mean being able to a generic `list<foo>` type (whether by C++ templates, macros, or good old void* casts), it's more than that. The benefit of non-intrusive is being able to create/manipulate/pass around multiple collections pointing to same payloads, without disturbing the payloads or the other collections in any way¹. That makes it easier to return and manipulate collections functionally (both in the narrow immutable sense, but also in the wider "treat collections like _values_ sense)... The deepest benefit arising from that I suppose is code modularity: different code areas need not be aware of each other's existence.
That all obviously comes at some tradeoff to performance. By definition, not having a full picture of the pathways your data travels means you can't choose the fastest representation!
¹The cheat is GC. For multiple unconnected collections to point to same payload, you need ref counting, or mark&sweep or similar to control its lifetime. Technically, GC does disturb the objects it's tracking (though that's well abstracted from other code).
However, you're largely right that specifically linked lists are rarely a good choice for non-intrusive collections => Arrays usually beat them, and if not then hash sets. (LISP & ML & Haskell do stick to lists for tail sharing — a choice which is arguably outdated by growing CPU / mem random access gap. I suppose Clojure's persistent vectors are an improvement.)