# 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!

• Insertion on a linked list doesn't imply that the list is sorted. Dec 24 '20 at 22:21
• One issue here is that the notion of a "given position" is ambiguous. If it means an index, you do need to traverse the list to get there, giving you an O(n) complexity. If the position is given by something like an iterator, you just have the actual O(1) insertion operation. Dec 27 '20 at 22:29

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.