[bfstein]

The nuance you're missing here is that the author is always inserting at the front of the arraylist. So even though the list grows dynamically, it still needs to move every value one spot over.

e.g. arraylist: [0][1][2][3][ ]

Even though there is space left in the array, we still need to move all the values one index to the right to be able to insert at the front, which takes O(n) time. In contrast, inserting at the front of a linked list is simply a matter of moving pointers and therefore constant time.

[SapphireSun]

Some languages, such as Perl, start the array in the middle to avoid exactly this situation.

[gens]

Can't you just imagine it is reversed, where the_array[num_things-1] is the first ?

[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.

[hinkley]

The awful thing about writing benchmarks is that if you don't give the worst case example, people give you shit for coming up with metrics that say whatever you want to say.

If you give metrics for the case that should be worst for your argument, people give you shit about using such a stupid example.

There's no way to avoid someone giving you grief no matter what you do.

[andrewflnr]

Um, give both?

[hinkley]

Then both groups agree that your examples are terrible ;)