Consider a singly linked list. What is the worst case time complexity of the best-known algorithm to delete the node a, pointer to this node is q, from the list?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. O(n)
Explanation
Copying the next node's data into q and unlinking the next node is O(1), but it fails when q is the last node; then the predecessor must be found by traversal, so the worst case is O(n).
More Data Structures and Algorithms questions
- The second smallest of n elements can be found with ____________ comparisons in the worst case.
- Consider the pseudo-code fragment, where m is a non-negative integer that has been initialized: p = 0; k = 0; while (k < m) p = p + 2^k; k…
- The solution of the recurrence relation T(m) = T(3 m/4) + 1 is :
- Consider the array A=<4, 1, 3, 2, 16, 9, 10, 14, 8, 7>. After building heap from the array A, the depth of the heap and the right child of…
- Which of the following algorithms solves the single-source shortest paths ?
- A text is made up of the characters A, B, C, D, E each occurring with the probability 0.08, 0.40, 0.25, 0.15 and 0.12 respectively. The opt…