Hacker News Reader

It's an average. Sometimes you insert at 0, sometimes at 1, sometimes at 2, ... sometimes at n. On average it's O(n).

In this case it's the worst-case performance.

Who said you insert at different locations?

Nobody. But who said you insert at the head? And who said the whole thing is list-backed? Insert is just insert--not a lot to work with there.

Performance complexity is spoken to general cases and averages unless indicated otherwise.