Even if we completely eliminate all caching effects, so that every memory access is uniform, regardless of past access history, then arrays are still going to be faster in many cases than linked lists. Obviously, in the random access case: fetching the n-th element. Pointers are metadata; a linked list has metadata for every node, and that requires memory bandwidth to suck through the processor. If every list node has a word of pointer for a word of data, then it means scanning through a million word list means we are loading two million words. If the data is aggregated into an array, then scanning it means we are loading only one million words. That's half the cycles. Likely fewer instructions executed in the loop and so on.

Note that arguments like, "but in year 20XX, such a case now fits into my Ln cache" work toward arguing that caching is less relevant. The more cache you have, the less relevant it is. As a cache gets bigger, more and more situations that previously exhibited "poor locality" now have "good locality" of reference.

Your 2016 machine can cache much more of a given linked list than your 1995 machine; it performs relatively better with linked lists than the 1995 machine, even if we account for basic differences of instruction issue rate (pipelining, branch prediction, etc).

I guess an size(array)+1 is a pathological case. Shame it seems to happen in every code base I've looked at.

Like, every codebase I've worked on had some array sorting at some point in it... but the frequency of needing to sort something vs having to loop over all the X makes it a completely not-relevant thing.

If the only time you add an element to an array is as a result of the user clicking somewhere, then I'd say it's definitely not worth taking into account if your array isn't 5000000 elements (which it will likely won't be if you are giving the user the ability to just add something to it).