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 from the list?

a)
O(1)

b)
O(log2 n)

c)
O(logn)

d)
O(n)

Correct answer is option 'D'. Can you explain this answer?

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 from the list?

a)
O(1)
b)
O(log2 n)
c)
O(logn)
d)
O(n)

Correct answer is option 'D'. Can you explain this answer?

Answer

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).

Answer

Explanation:

To delete a node from a singly linked list, we need to first find the node and then update the pointers of the surrounding nodes to remove the node from the list. The time complexity of this operation depends on the position of the node in the list.

Worst-case time complexity:

In the worst case, the node to be deleted is the last node in the list. In this case, we need to traverse the entire list to find the node before the last node in order to update its pointer. This means we need to visit n-1 nodes in the list.

Therefore, the worst-case time complexity of the best known algorithm to delete a node from a singly linked list is O(n).

Explanation of options:

a) O(1): This would be the time complexity if we had a direct reference to the node to be deleted. However, in this case, we only have a pointer to an intermediate node, so we still need to traverse the list to find the node before it.

b) O(log2 n): This time complexity is associated with binary search algorithms. However, it does not apply to linked lists as we cannot perform binary search operations on them.

c) O(logn): Similarly, this time complexity is associated with algorithms that divide the search space in half at each step. It does not apply to linked list deletion.

d) O(n): This is the correct answer, as explained above. We need to traverse the entire list to find the node before the one to be deleted, resulting in a time complexity of O(n).

Therefore, the correct answer is option D.

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

Top Courses for Computer Science Engineering (CSE)

Top Courses for Computer Science Engineering (CSE)

Suggested Free Tests

Related Content

Mock Test Series

Subject-wise Courses

Subject-wise Courses

Other Engg Branches

Company