I don't think you can really get around linked lists having bad cache locality even if they're intrusive. The point of arrays usually being faster is that they're much more cache friendly, and fitting data in cache and avoiding branch mispredictions is usually much more important than o(1) insert/delete.

If you allocate all the nodes of a particular list from one arena, the cache performance should be OK.

IDK if this is the case for device drivers, but AFAICT device drivers tend to preallocate memory on loading and manage it locally.

Linked lists fare worse than arrays only for sequential iteration in tight loops. That includes many/most cases, but not all. As for O(1) insertion/deletion: It's not always about amortized cost, sometimes you actually do care about worst case execution time.

Look, I'm not saying that linked lists can replace arrays. In fact, I almost always use arrays instead of linked lists. What I'm arguing against is the notion that arrays always trump linked lists, which is false, and repeating that meme shows a lack of deeper understanding.

I don't think I've heard anyone seriously suggest never using a linked list -- the advice usually just ends up being "are you really sure?" which seems appropriate.

Then let me quote the post I originally replied to:

> The way modern memory works linked lists are practically a denial of service attack on system performance.

and

> IMO, like goto’s it’s better to just forget they exist.

That's as close to "never use a linked list" as you can get without saying that literal sentence.

Linked lists require you to be on the node in order to do an insertion so it’s generally not O(1) it’s O(n) with sky high constants. Thus for random inserts arrays are actually faster.

If you have a degenerate case and are never traversing nodes, you’re still likely better of with a rung buffer, array list, 2 different stacks, or various other options. And frankly you’re never going to endlessly just insert data without reading it.

> Linked lists require you to be on the node in order to do an insertion so it’s generally not O(1) it’s O(n) with sky high constants.

Re-read my original post: "[...] especially if you have callbacks which store a pointer to a list element [...]"

This happens all the time in kernel code or bare-metal programming.

What else can I say? Open the Linux source code [1] and see for yourself.

[1] https://elixir.bootlin.com/linux/latest/source

Look we can all agree if you’re writing ASM your going to use goto’s. Further if linked lists are tiny or rarely used, it’s not a problem. If you can ensure the data stays in L2 cache it’s far less of an issue. If any number of things they don’t create problems, but frankly the general case encountered by most programmers are not that.

PS: If you don’t feel like pointing to a concrete example, I am going to counter with 99% of the stuff you can find here: www.google.com.

Arn't there hybrid array lists? Like where instead of growing the array when it goes beyond bound, the last slot is reserved to create a link to the next array chunk?

Linked lists are O(N) random insertion as you need to traverse the tree to locate the correct node. The only way that they are always O(1) are a degenerate case better suited for another data structure. Aka if you want a queue then use a ring buffer not a linked list.

Doubly-linked lists have problems with concurrent mutability, FYI. It's really better to aim for non-circularity and to avoid the need for locks.

> Doubly-linked lists have problems with concurrent mutability, FYI.

So do arrays, FYI.

> It's really better to aim for non-circularity and to avoid the need for locks.

How does an array avoid the need for a lock where a linked list needs one?