On Saturday, 10 December 2022 at 15:59:07 UTC, Ali Çehreli wrote:
There isn't a single point in favor of linked lists.
Yes there is, there are still special cases where linked lists
can be a better alternative. Especially a version with intrusive
members (with next/prev pointers as members in your object)
The intrusive linked list doesn't need any extra allocation apart
from the object itself which means less fragmentation and small
container allocations.
The double linked list has O(1) insert and delete, arrays has not.
The single linked list offer completely lockless variants, which
is also completely unbounded.
The intrusive linked list has better performance with everything,
except random access.
You can move/splice entire lists without copying.
The linked list performs equally well regardless of number of
objects or object size. The performance of arrays depend on this.
As CPUs has progressed the array has become more favorable than
the linked list type that is being offered by most standard
libraries (the one that must allocate container objects, not
intrusive). For most programming practices the array is usually
the best. However, there are occasions where the linked list can
be worth to be considered.
