Question

Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best-known algorithm to delete the node x form the list?

• A. $O\left(logn\right)$
• B. $O\left(n\right)$
• C. $O\left(1\right)$
• D. $O\left(lo{g}^{2}n\right)$

Answer 1

The correct option is B $O\left(n\right)$

To delete node x, we should find out the previous node to the x. To find the previous nodes to the x will take O(n).
Therefore it takes O(n).