The reason manipulating linked lists in the middle is faster than arrays is so you can save the O(n) work of moving elements. But you lose that if you still do O(n) worth of seeking. There is no big-O difference between inserting and deleting in the middle of an array and a plain linked list, if the linked list is forced to seek.
I'm sure this is as obvious to you as it is to me, but perhaps the perspective it comes from explains why people are thinking that your described operations on the list are a dodgy benchmark for judging linked lists vs arrays; absent constant factors, they should perform the same. (And yes, for reasonable input on modern machines, the constant factors will dominate.)
I'm sure I agree with everything you're saying here, but it carries a whiff of tautology. You lose the benefit of middle-insertion in a list if you have to seek, but part of the point of using an array is not having to seek ever.
Anyways the only thing that moved me to comment is the general inferiority of linked list data structures compared to arrays, which are what Ruby (sensibly) uses.
I'm reading this thread and kind of tearing my hair out.
One theoretical case where lists beat arrays is seeking to the middle (once) and inserting 1000000 items in that one spot.
If you want to test if lists can ever be useful in Ruby then you want to test the case that they are theoretically useful. Your test is a theoretical dead heat as arrays and lists both perform O(n) in it. All you learn is that arrays are faster in Ruby for the same complexity, which we knew already.
I probably shouldn't have replied and dragged it out, and I apologise for my tone but you seem to be almost wilfully missing the point.
There are problems where a linked list is theoretically better suited than an array. Your test is a problem where they are theoretically evenly matched. The interesting question is: do the benefits of native code etc, that you get when using an array outweigh the costs that you incur for using a non-optimal data structure for a given problem? To answer this you would need to come up with a situation where a list should be faster if the array and list were both native or both higher level ruby implementations. Then compare the actual running times to see what impact native code vs ruby code has.
All your test shows is that in a problem where neither data structure has an advantage in complexity, i.e. they both perform in O(n), the one backed by native code is faster. My assertion is that is a pretty boring thing to discover and "we", or most people, would guess that anyway.
I think we're not communicating well because we're deep in a tangential subthread.
I take your point that repeated insertion at a specific held reference to the middle of a list is faster than insertion into the middle of an array.
I'm just saying that in Ruby, where every list node incurs object overhead and where list iteration is done by tree walking and array referencing is done by pointer dereferencing in the background, lists underperform arrays even in cases where you'd expect the algorithmic complexity of a list to yield a big win.
I'm sure this is as obvious to you as it is to me, but perhaps the perspective it comes from explains why people are thinking that your described operations on the list are a dodgy benchmark for judging linked lists vs arrays; absent constant factors, they should perform the same. (And yes, for reasonable input on modern machines, the constant factors will dominate.)