patternMinor
Why are linked lists considered O(1) for in-middle insertion/deletion whereas dynamic arrays are considered O(n)?
Viewed 0 times
insertionwhyarraysareconsidereddynamicforlistswhereasdeletion
Problem
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?
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?
Solution
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
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.
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.
Context
StackExchange Computer Science Q#93875, answer score: 2
Revisions (0)
No revisions yet.