HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Why are linked lists considered O(1) for in-middle insertion/deletion whereas dynamic arrays are considered O(n)?

Submitted by: @import:stackexchange-cs··
0
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?

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 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.