[rakoo]

Yes it does: vectors are good for random access, linked-lists are good for doing stuff in the front/back of the list. The performance bug we have here is solved by finding a way to insert stuff at the front/back (and also going through each item in the list); there is no need for random access.

[kaeluka]

If I remember Bjarne's talk correctly, vectors (in C++) are even fast at inserting because they have densely packed representation which rhymes well with modern computer architecture. Inserting in a linked list is slow, as walking the list to find the element at which to insert will already incur O(N) cache misses, whereas in vectors it's only O(1) cache misses. Moving the elements in the vector one to the right is fast due to computer architecture dealing well with predictable patterns.

The allocations here (ruby) are reduced because the implementation of appending is horribly slow in the first place, using defensive cloning (I'm taking jph's word here).

[herewego]

Yes, but FWIW most linked list implementations have a reference or pointer to the tail, making appends not O(n), but O(1). However, there is a threshold, depending on use case, where a small vector being resized multiple times larger than the original will be faster than many linked list appends. Point being, either can accel depending on use case.

[vbezhenar]

Vectors are good at inserting in the back and deques are good in inserting both in the front and in the back (or course if capacity grows exponentially, but that's how they should be implemented). Linked lists are almost always wrong choice because they don't play well with memory caches. They might be better with inserting in the middle and that might matter only with really huge lists (millions of items). At least that's how it works with languages close enough to the hardware.