The advantage of extrusive linked lists is that you don't need to modify the data layout of Member at all. All the linked list manipulation happens on ListNodes, which have a pointer to the actual member, which can be accessed with just a cast. That's why they're so well-suited to class libraries: you can easily write a generic ExtrusiveLinkedList that works with any data that can be represented with a pointer, hide all the traversal (and the existence of individual ExtrusiveListNodes) in accessor functions, and present a simple API with no codegen or modifications to Member.
The advantages of intrusive linked lists are 1) performance 2) no heap allocations 3) easy traversal when given a Member*. It's only a single indirection rather than a double, and usually that indirection is necessary anyway to avoid copies. Insertion and deletion are just pointer manipulation; you don't need to allocate new space for the nodes. Oftentimes your functions will take Member* anyway, and it's nice not to take or traverse the container if you just need to peek at the next element coming up.
The point of this subthread is that intrusive linked lists have very clear use cases in the kernel & embedded spaces, where these advantages are often critical. Extrusive linked lists, however, have very few advantages over vectors (which also require heap allocation but are more cache & locality friendly). In a common business app responding to user input, the difference between O(1) amortized and O(1) is negligible; you can eat the occasional pause for a vector resizing, because the user isn't going to care about a few milliseconds. They both require heap allocation. The vector will give you much faster traversal, because subsequent reads all hit cache. The vector takes less memory (1 pointer per element, with a max of 50% overhead, while an extrusive doubly-linked list is 3 pointers per element). There's just little reason to use an extrusive linked list because the use-cases where intrusive linked lists are not better are precisely the same ones where vectors are better.
In the real world of application development when choosing between Vector and LinkedList the answer is almost always Vector. There are, of course, certain problems where LinkedList is always the correct answer.
However for all problem that have chosen either Vector or LinkedList as their container of choice a super majority should choose Vector.
Coopies are not free. Not in terms of stack, neither in terms of memory or its bandwidth. Both of which are in demand there.
For an example, look into how most of Zephyr RTOS is implemented. It's mostly intrusive lists (called queues there for some reason, but they support iteration) or ring buffers (msgq or mpsc_pbuf or pipe). For bigger systems you can use red-black trees.
There is no vector data structure, you can allocate a block from the heap and manage its size manually, but it's rarely done as most sizes are static and many data structures are preallocated by the bootloader or loaded directly from flash memory. Cache locality of these is of course possible to manipulate manually by use of memory sections.
A list does not copy by default, which is an extremely important performance characteristic. And it does not require overallocation like a vector of pointers, plus has a fast remove, especially at head or tail.
Feel free to replace the term “Vector” with “Contiguous Memory”. The relevant distinction in this conversation is “contiguous vs node pointers”. Embedded loves contiguous blocks.
A dynamic array copies memory if it regrows, inserts, removes. The cost of that operation depends on numerous factors. But it doesn’t result in “extra copies” laying around.
Oh wait maybe you mean array operations perform extra copies, not that they persist. In which case it comes down to which is more expensive: memcpy some bytes or cache inefficient pointer traversal.
It depends! But most problems for most programs are MUCH faster if they avoid LinkedList. Many people, especially new programmers, radically underestimate the penalty of pointer chasing.
Quite the opposite. When you have no dynamic allocations, vectors are out of the question, while pool of nodes is fine and sound.
And quite often you can't copy elements from one place to another in embedded or operating systems, since many consumers can store a pointer to this element. Of course this could be solved by usage of vector of pointers, but this completely ruins the ``cache locality'' argument.
His statement wasn't a generalization to repeating this back does not make sense.
As any generalization this one too is, of course, incorrect.
Outside of the realm of academia, the need to keep data pieces in several containers at the same time, with no heap operations on insertion or removal and O(1) removal is very common, especially in the kernel space and embedded contexts. The only option that fits the bill - you guessed it - are the linked lists.