2 ms·
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
by packetlost 1mo ago
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.
- ahgas 1mo agoGP 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.
- zahlman 1mo ago>"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.
- flohofwoe 1mo agoRegular linked lists were implicitly 'intrusive' long before C++ existed and introduced 'extrusive' lists in the stdlib.