3
$\begingroup$

I am struggling to understand why linked lists seem to be accepted to have better big-O performance than arrays for in-middle insertion/deletion. The performance differences between lists and arrays for front-of and end-of operations make sense intuitively, but for operations in the middle, not so much.

I see why the middle insert is O(n) for a dynamic array - half the elements need to be shifted one by one.

But, when it comes to linked lists, don't half the elements need to be traversed one by one starting from the head to find the insertion point? And if so, why doesn't that also make linked lists O(n) for middle insertion? And if it does, why is it not represented that way in the Wikipedia article?

$\endgroup$
2
$\begingroup$

You are right: if we have to find a particular place and then insert a value there (for example, insert an element in a sorted list), it is $O(n)$ for a linked list.

However, the Wikipedia article you seem to mention considers another operation named insertAfter: given a node, insert an element after that node. When the particular node after which to insert is given to us, we spend only $O(1)$ time to do so, as we don't have to search for it.

An example usage is "duplicate each value $x$ we find in the list". An example solution is to traverse a list, and whenever we find an $x$, add a duplicate right after it, and immediately step over it. Each such insertion takes $O(1)$, and the whole solution is $O(n)$. Note that, without any preallocation strategy, solving such a problem with a dynamic array is $O(n^2)$ worst case.

$\endgroup$
  • 1
    $\begingroup$ Thank you! It is odd and pleasant to get an answer from someone from my hometown across the world. Hope Peter is treating you well. $\endgroup$ – Ilya Zarembsky Jul 5 '18 at 7:00
  • $\begingroup$ @IlyaZarembsky Thanks. If the answer is what you were looking for, please mark it as accepted. If not, tell us what's missing. $\endgroup$ – Gassa Jul 5 '18 at 10:08

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.