2 ms·

Insertion in a linked list is not O(n) though.

• 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 ago
    Inserting 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).