[DougBTX]

Yes, then it would be a discussion about append performance instead of insert performance. Might be handy to do if you know that all the changes to an array will be inserts at the front, then you can just write the array in reverse and also read in reverse.

But it is helpful to keep the terminology clear, because an insert in the middle of a linked list is still O(1), but inserting into the middle of an array will require moving some fraction of the data.

The OP is discussing inserts at the start just because it is the worst-case scenario for arrays, then a positive result will still be true if some of the inserts are in the midddle or even near the end.

[thaumasiotes]

> But it is helpful to keep the terminology clear, because an insert in the middle of a linked list is still O(1), but inserting into the middle of an array will require moving some fraction of the data.

This is true if you already have a reference to the middle of the list. If you don't (say, because you want to insert while preserving the fact that the list is sorted), then inserting into a linked list is O(n) just like the array is.

[wolf550e]

Memory reads and memory writes are not the same. Linked list insert in the middle needs to do only O(1) writes. But because linked lists preclude memory prefetch, they should not be used these days.

[fixerfrasse]

Afaik, if you read in reverse, then you will miss cache optimization since it only works forward.

[Danieru]

Intel cache prediction will detect both forward, backward, and some odd movement patterns. It has not been only forward prediction for a very long time.

[dottrap]

Do you know how the popular ARM based chips fare in comparison?

[hinkley]

Stay strong.