[bumeye]

The author does an insertion sort in a linked list, of course that's going to be slow.

For a sorted insert you need to do 2 things: find the right spot for insertion and the insert itself. An insertion sort does this n times.

For a simple array/vector that's:

search: O(n)

insert: O(1)

total takes (O(n) + O(1)) x O(n) = O(n^2)

For a linked list:

search: O(n)

insert: O(n)

total takes (O(n) + O(n)) x O(n) = O(n^2)

There we go, the algorithm takes O(n^2) for both data structures. The theory already proves that a linked list has absolutely no advantage over an array when using this algorithm. On top of that, iterating over a linked list is slower than over an array for various reasons, even thought they are both O(n). So that's where the difference is coming from.

The example he uses is clearly a wrong use case for a linked list, it's plain wrong to conclude that the whole data structure should never be used.

[mdwrigh2]

I believe you have linked list and vectors flipped. vectors have O(n) insert, and linked lists have O(1) insert. Regardless, your point still stands.

[bunderbunder]

In the basic case, linked lists are O(n) for inserting at position n, on account of having to follow n elements' worth of pointer trail to get to that position. When you're inserting at the first position (as should normally be the case for most applications to which linked lists are well suited), n happens to be 1.

For certain applications where you already have a pointer to position n by the time you find out you need to insert there, then insertion does end up taking constant time as long as it's not a persistent linked list. But big-O is for describing the worst case, not the ideal case that you can achieve given certain optimizations.

[bumeye]

Note that this is such a case where you've already got the pointer.

mdwrigh2 is totally right. I flipped the O(1) for linked list insertion with the O(n) for verctor insertion :).