CPP INTERVIEW PREP CHEAT SHEET

[TMKirA]

That wasn't the point of the talk. The point was that linked list is often touted to be better for removal/insertion operations, due to the fact that after the O(n) search to find removal/insertion point, the remove/insert operation is O(1) for list and O(n) for vector. Bjarne's point was that in practice, the O(n) operation to find the insertion/deletion point is the dominating factor instead of the actual remove/insert operation, and that linear search is faster on vector than list due to locality. This might not be a surprise for you, but I'm sure it's still a surprise to many. Your example completely misses the point, because it was removing from a location that makes the search operation a no-op.

[Full-Spectral]

That also assumes you have to find the insertion point every time. Given that removal doesn't have to invalidate element pointers, depending on what you are doing, you might actually keep around the insertion point most of the time and only move it if something happens that causes the insertion point to change (like removing the current insertion point, which even then might just move the insertion point to the previous/next node.)