1
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ Insertion on a linked list doesn't imply that the list is sorted. $\endgroup$
    – theDoctor
    Dec 24 '20 at 22:21
  • $\begingroup$ 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. $\endgroup$ Dec 27 '20 at 22:29
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.