Comment by cma
5 years ago
Depends on element size and some other stuff, but if it is a singly linked list, and truely random insertion location, iterating to that location is N/2 on average, where inserting and copying the rest of the array is also N/2. Small elements and the array could still be much faster since they are all prefetched during the copy, vs jumping all over memory during the list iteration and potentially stalling on each for ~200 instructions waiting on main memory.
You can imagine a linked list whose “API” is “take this node and insert after it”.
If a bunch of insertions happen like that, based on some other data structure, and then a periodic iteration eventually happens at some point, you could also imagine an array version being batching together all the array inserts in another simple array and applying them all at once before iteration.