I don't get why the time complexity of insertion on a linked list is O(1) I was watching the algoritmhs course by mycodeschool and he said that when we add a new item on a given position the worst case would be $O(n)$. Everywhere I look says insertion is $O(1)$...
Now I understand that insertion itself might be $O(1)$, but if I have the following interface (this is something I made up, not a real thing I'm working):
insertAtIndex(any item, int index)

Would this be $O(n)$? Since I will search $O(n)$ and then insert $O(1)$?
Thanks!
That is correct. There is no random indexing in a linked list so you will have to traverse it from the start until you reach the right index, requiring a $O(n)$ search. After that you have $O(1)$ reference/pointer bookkeeping for the insertion operation.