Speed isn't the only performance metric that matters. I probably should have said explicitly that I'm referring to uses where it makes sense to use a linked list. But unfortunately I didn't specify because that wasn't the point I really wanted to make.
There's a lot of things to learn that appear to to not makes sense... until suddenly they do.
> There are valid uses of linked lists, that's why they exist, but most people don't have those use cases.
Isn't that pretty much what I said?
I'm pretty sure we agree that they're useful, but their usefulness isn't as universal nor as common as the pattern is.
Linked lists are worse than flat arrays in every single performance metric other than ordered removal. They use more memory (the links), have inferior cache locality, cause more allocations (unless you're allocating anyway, in the case of intrusive lists).
Their one benefit - O(1) ordered removal - is easily achieved with a flat array, in at least two common ways: swap in the last element if you don't care about the order, or mark the index as vacant if you do care about the order, or if you care about the stability of references.
I mean, I agree that they're kind of neat from a certain perspective, but they're almost never the right choice.
About the ordered removal, if it's not very common, using tombstones (a constant to denote no element) is fine. Too many tombstones would need a compaction phase and still it'd work way better than a linked list.
Personally I have not met a case where a random removal in the middle of a list is common -- b/c finding the needle is slow to begin with O(n). In such case linked hash sets are O(1) but way more memory intense (which is a very advanced linked list)
That being said linked queues are great for concurrent lock free cases.
Dynamic arrays often use doubling as a resize strategy. This means that on average about 25% of capacity is "wasted". Depending on element size and element count it may lead to larger memory usage compared to linked list.