I googled it and got the response that Bjarne Stroustrup first used “intrusive” in his 1985 C++ book. He was adding a new distinction between the older intrusive kind and the new ‘non-intrusive’ kind, because some people had started using C++ to allocate the list nodes and the payload structs separately.
Now with std::list and college classes often teaching non-intrusive linked lists, and intrusive lists only being used in deep dark places like the OS kernel, maybe it’s easy to assume the ‘regular’ kind is non-intrusive.
What Stroustrup called ‘intrusive’ had been the default understanding of linked lists since around 1955, and what people used most often. A ‘regular’ linked list to most people back then was the intrusive kind, and the term ‘non-intrusive’ might have been an attempt to sell people on the benefits of abstracting and separating node types from payloads, but that maybe papers over the disadvantages a little.
The only kind of linked list I’ve ever used in my professional career is the intrusive kind. There are very few good reasons to ever use non-intrusive lists outside of the classroom. At least, not if you care about performance at all. They might be convenient & easy, but it’s usually the case that either an array or an intrusive list would be a better engineering choice.
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.)
It really depends on the ecosystem you’re working in. For a good while, most developers have been working with managed runtimes, where “non-intrusive” linked lists are generally the default and “intrusive” linked lists correspondingly rare.
(Actually, in many cases arrays are the default (like ArrayList in Java), because lists tend to only get assembled once and then passed around without further modification.)
"Intrusive" may be a C++ speak, but I wouldn't say that one or the other type of lists is necessarily much older or more "normal". After all, a cons cell embeds data and not the other way around and lisp is one of the oldest programming languages in existence
Back in the day what is being called out here as an "intrusive" linked list was just a linked list, since you didn't have the luxury of having memory and CPU cycles to waste with extra allocations and indirection.
In the C++ world the STL introduced generic data types such as linked lists, which became the default, but "instrusive" linked lists still have their place in specialized list-heavy use cases where performance matters. In a previous job I wrote a widely adopted XML/JSON library using instrusive lists to link child elements, and the performance benefit was considerable, with my DOM API basically hiding this implementation detail from the user.
You have it backwards, an intrusive linked list is a linked list that is embedded in another data structure. The classic example is a linked list whose elements live on the stack.
The article is wrong too, or at least using the term over-specifically.
GP points out that what the article calls "intrusive linked list" is a regular linked list. Wikipedia for instance gives the canonical linked list example of a struct with one embedded integer and a next link and of course does not call it "intrusive linked list".
"Intrusive" got popular with C++ intrusive pointers, and that is where the article gets is misinformation from.
And of coursed the web jockeys downvote the correct objection since they have no clue about data structures, history, logic or basic reading skills.
"Intrusive" got popular with C++ intrusive pointers
It got popular with C++'s attempts at type safety. In particular, std::list lets you accomplish the machinery without macros, and allowing for polymorphism (heterogeneous lists of derived instances) without weird type casts and overallocation tricks, but at the cost of another level of indirection.
I came to this relatively late (2013-ish, windows kernel development, scouring OSDev, etc) so I thought that was always the right name for them. Prior experience was mostly... higher-level langs.
I concur. I recall being a student and when implementing LL for the first time, you did it this way (mix your data and ptr to next node). It is baby's first linked list.
Comments
I think this article rewrites history and it is unfortunately already cited by the clankers.
"Intrusive" is C++ speak. The regular linked lists always had embedded data or a mix of embedded data and pointers to outside data in a C struct.
I googled it and got the response that Bjarne Stroustrup first used “intrusive” in his 1985 C++ book. He was adding a new distinction between the older intrusive kind and the new ‘non-intrusive’ kind, because some people had started using C++ to allocate the list nodes and the payload structs separately.
Now with std::list and college classes often teaching non-intrusive linked lists, and intrusive lists only being used in deep dark places like the OS kernel, maybe it’s easy to assume the ‘regular’ kind is non-intrusive.
What Stroustrup called ‘intrusive’ had been the default understanding of linked lists since around 1955, and what people used most often. A ‘regular’ linked list to most people back then was the intrusive kind, and the term ‘non-intrusive’ might have been an attempt to sell people on the benefits of abstracting and separating node types from payloads, but that maybe papers over the disadvantages a little.
The only kind of linked list I’ve ever used in my professional career is the intrusive kind. There are very few good reasons to ever use non-intrusive lists outside of the classroom. At least, not if you care about performance at all. They might be convenient & easy, but it’s usually the case that either an array or an intrusive list would be a better engineering choice.
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.)
It really depends on the ecosystem you’re working in. For a good while, most developers have been working with managed runtimes, where “non-intrusive” linked lists are generally the default and “intrusive” linked lists correspondingly rare.
(Actually, in many cases arrays are the default (like ArrayList in Java), because lists tend to only get assembled once and then passed around without further modification.)
"Intrusive" may be a C++ speak, but I wouldn't say that one or the other type of lists is necessarily much older or more "normal". After all, a cons cell embeds data and not the other way around and lisp is one of the oldest programming languages in existence
Back in the day what is being called out here as an "intrusive" linked list was just a linked list, since you didn't have the luxury of having memory and CPU cycles to waste with extra allocations and indirection.
In the C++ world the STL introduced generic data types such as linked lists, which became the default, but "instrusive" linked lists still have their place in specialized list-heavy use cases where performance matters. In a previous job I wrote a widely adopted XML/JSON library using instrusive lists to link child elements, and the performance benefit was considerable, with my DOM API basically hiding this implementation detail from the user.
You have it backwards, an intrusive linked list is a linked list that is embedded in another data structure. The classic example is a linked list whose elements live on the stack.
The article is wrong too, or at least using the term over-specifically.
It's not really tied to C++isms at all.
Regular linked lists were implicitly 'intrusive' long before C++ existed and introduced 'extrusive' lists in the stdlib.
GP points out that what the article calls "intrusive linked list" is a regular linked list. Wikipedia for instance gives the canonical linked list example of a struct with one embedded integer and a next link and of course does not call it "intrusive linked list".
"Intrusive" got popular with C++ intrusive pointers, and that is where the article gets is misinformation from.
And of coursed the web jockeys downvote the correct objection since they have no clue about data structures, history, logic or basic reading skills.
It got popular with C++'s attempts at type safety. In particular, std::list lets you accomplish the machinery without macros, and allowing for polymorphism (heterogeneous lists of derived instances) without weird type casts and overallocation tricks, but at the cost of another level of indirection.
This was my reaction exactly. I was surprised by the diagram of a "normal" linked list.
I came to this relatively late (2013-ish, windows kernel development, scouring OSDev, etc) so I thought that was always the right name for them. Prior experience was mostly... higher-level langs.
I concur. I recall being a student and when implementing LL for the first time, you did it this way (mix your data and ptr to next node). It is baby's first linked list.