I was surprised to see the main benefit of intrusive linking mentioned as a bit of a side note: The ability to move data around between lists (and within a list) without copying. You also get O(1) removal from the middle of the list, assuming you have a pointer to the object somewhere else. As a result, when you have large state structs and you don't do a lot of list scans, intrusive linking makes things a lot faster than use of packed structures like vectors.
Data is generally read more often than written and data is read in locally spatial way.
That’s why having elements laid out next to one another is often more important than the algorithmic complexity of occasionally doing an O(n) or O(n log n) operation updating the layout.
It’s not always the case of course but it is the case more often than you’d think.
You can do this with non intrusive lists too. See c++’s merge/splice/etc. You can store the iterators in some other place as you do this, making it quite handy on occasion.
I'm pretty sure the author there means to compare the intrusive linked list to a non-intrusive linked list (such as C++ std::list), not to vectors etc. that aren't "linked" at all. As described e.g. in https://news.ycombinator.com/item?id=49549542 .
Comments
I was surprised to see the main benefit of intrusive linking mentioned as a bit of a side note: The ability to move data around between lists (and within a list) without copying. You also get O(1) removal from the middle of the list, assuming you have a pointer to the object somewhere else. As a result, when you have large state structs and you don't do a lot of list scans, intrusive linking makes things a lot faster than use of packed structures like vectors.
Data is generally read more often than written and data is read in locally spatial way.
That’s why having elements laid out next to one another is often more important than the algorithmic complexity of occasionally doing an O(n) or O(n log n) operation updating the layout.
It’s not always the case of course but it is the case more often than you’d think.
The main benefit is that adding/removing items to/from a list requires no heap operations. All control elements are basically preallocated.
You can do this with non intrusive lists too. See c++’s merge/splice/etc. You can store the iterators in some other place as you do this, making it quite handy on occasion.
I'm pretty sure the author there means to compare the intrusive linked list to a non-intrusive linked list (such as C++ std::list), not to vectors etc. that aren't "linked" at all. As described e.g. in https://news.ycombinator.com/item?id=49549542 .