This is true for the kind of programmin most people do. Linked Lists make no sense in JS, Python, Rust, etc. But they are without a doubt still an incredibly useful pattern with unmatched performance characteristics. Especially if you're trying to be memory efficient. It's a systems programming pattern, rarely useful if you're just a web developer.
But then again... I never thought I'd need to know music waveform theory while I was watching the magic school bus as a kid... Turns out that was incredibly useful when I needed to implement a music note generator for a VoIP client... You never know when something might actually be really useful.
This comment makes no sense.
1. You have linked lists in Rust. They're in the standard library.
2. Linked lists do not have "unmatched performance" - they are slower than almost anything, outside of highly specialized use cases. Even moreso for intrusive linked lists. Worst of all, they are horrible for cache locality.
There are valid uses of linked lists, that's why they exist, but most people don't have those use cases.
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.
>Especially if you're trying to be memory efficient
Linked list have higher const cost memory wise compared to array backed structures. Even when an array back structure is half empty it's still takes less memory.
> Even when an array back structure is half empty it's still takes less memory.
uh... what?