Consider a singly linked list. What is the worst case time complexity of the…
2018
Consider a singly linked list. What is the worst case time complexity of the best-known algorithm to delete the node 𝑎, pointer to this node is \(𝑞\), from the list?
- A.
\(O(n \lg \: n)\) - B.
\(O(n)\) - C.
\(O(\lg \: n)\) - D.
\(O(1)\)
Attempted by 602 students.
Show answer & explanation
Correct answer: B
Answer: O(n)
Explanation:
If the node to delete is not the tail and you have a direct pointer to it, you can delete it in O(1) by copying the data from its next node into the node and then removing the next node (adjusting pointers).
If the node to delete is the tail, you must find its predecessor to update its next pointer. In a singly linked list that requires traversing from the head to the node before the tail, which takes O(n) time.
The worst-case time complexity of the best-known algorithm, therefore, is O(n).
Note: Achieving better than O(n) in the worst case would require additional data structures (for example, a doubly linked list or auxiliary indexing) that change the list model.
A video solution is available for this question — log in and enroll to watch it.