I may be missing something here, but your example seems to be a textbook case for big-O analysis. Writing in a vector is O(1), while linked list is O(n), isn’t it?

It's about inserting in the middle of a vector, which requires to shift every element after that one (so, O(n)), and for a linked list it can be done by allocating a new element, which, if you have the pointer to the place where you want to insert, is O(1) - and really, just a few operations.

However, in practice, the O(n) operation will be faster - since doing a hundred reads and a hundred writes to shift a hundred numbers within a single cache line will be much faster than reading a single byte to an out-of-cache memory in the linked list case; the processor can do a lot while waiting for any new data from RAM.

Writing into a vector is O(n), writing into a LL is O(1), assuming you have an iterator to the location to write to. If you don't, then it becomes O(n), and writing into a vector can be O(1) if you're writing to the end.

C++ stl, LL appending is always O(1) and writing into a vector is O(n). There are plenty of caveats to this and the documentation should be referenced.

He's right btw that insert into a vector is generally faster in the C++ stl than insert into a LL. I don't recall off the top of my head why that is, just remember it's the case.

Data locality is a big reason. Sure, it's O(N) writes, but those writes are neatly lined up in such a way that the likelihood of a cache miss is low. As opposed to a linked list, where just traversing to the middle may entail multiple round trips to main memory.

Yeah -- O(1) and O(n) are definitely simplifications and never tell the whole story.

It's not strictly related to C++ and/or STL. This is how computers work nowadays.

Well, my comments were specifically based on C++ and the STL. There are so many implementations that one has to define the discussion.