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