This article reminds me of performance advice I was starting to see in the 2000s decade. Basically it was to not introduce a bunch of pointer heavy data structures to get lower algorithmic complexity. Stuff it all into a vector. You will use some algorithms that the computer science textbook will say it's slower, but if it fits all in cache it doesn't matter. The cache misses following pointers all over town hurts you more.
This is partly because the C++ stdlib looks like they've given you all the basic tools you need - unlike the C standard library - yet in fact many of these tools are hopelessly obsolete. It's not quite PHP's "fractal of bad design", these are all reasonable tools... if it's 1985. The linked lists make sense on hardware where five pointer fetches and five consecutive memory reads cost roughly the same - 1985 hardware.
The growable array type std::vector<T> is least impacted by these archaic choices out of the tools in the box you're likely to reach for. So it will make sense very often to choose this type first.
Linked lists are great data structures for the use cases where you need their properties. It’s just that you don’t encounter those scenarios very often in most kinds of software.
You say not very often, but the true usefulness is almost never. Extremely little. One in a trillion times. Even when you think linked lists would be faster, they usually aren't.
This is wildly overstating it. Yeah, I agree, they're much less often the right choice compared to a good-ol' growable array, but they have lots of uses in high-performance code and concurrent code, and they're building blocks in lots of other data structures. Like, in a bucket hash-table, the buckets are linked lists, in a LRU cache you interleave a hash table and linked list, std::hive is a linked list of chunks of elements, etc. Anything that has ever had to deal with memory pooling/allocation uses free-lists which are linked lists. And on and on and on.
asveikau · · focus · HN ↗
tialaramex · · focus · HN ↗
The growable array type std::vector<T> is least impacted by these archaic choices out of the tools in the box you're likely to reach for. So it will make sense very often to choose this type first.
adrianN · · focus · HN ↗
someonebaggy · · focus · HN ↗
OskarS · · focus · HN ↗
This is wildly overstating it. Yeah, I agree, they're much less often the right choice compared to a good-ol' growable array, but they have lots of uses in high-performance code and concurrent code, and they're building blocks in lots of other data structures. Like, in a bucket hash-table, the buckets are linked lists, in a LRU cache you interleave a hash table and linked list, std::hive is a linked list of chunks of elements, etc. Anything that has ever had to deal with memory pooling/allocation uses free-lists which are linked lists. And on and on and on.