Hacker News Reader

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.

View on HN

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.

>"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.

Reply on news.ycombinator.com