4 ms·
The post mentions inserting in the middle of the list. Sort of, do you assume you found the right node already, then it's O(1). If not, it's O(n/2).
by sliken 4y ago
The post mentions inserting in the middle of the list.
Sort of, do you assume you found the right node already, then it's O(1).
If not, it's O(n/2).
- gpderetta 4y agoInserting in the middle of the list is still O(1). It doesn't make sense to include finding the insertion position in the insert cost as there are many ways to do that (for example you might have a separate hashed or ordered index, or simply have a pointer to the node by other means). Also, pedantically O(n/2) is the same as O(n).