In a standard linked-list implementation of a queue that maintains both front…
2024
In a standard linked-list implementation of a queue that maintains both front and rear pointers, compare the time complexity of enqueue and dequeue operations.
- A.
Enqueue : O(n), Dequeue : O(1)
- B.
Enqueue : O(1), Dequeue : O(n)
- C.
Both : O(1)
- D.
Both : O(n)
Attempted by 129 students.
Show answer & explanation
Correct answer: C
Key assumption: A standard linked-list queue maintains both front and rear pointers.
Enqueue: insert the new node at the rear and update the rear pointer. This takes O(1) time.
Dequeue: remove the front node and update the front pointer. This also takes O(1) time.
If no rear pointer were maintained, enqueue could require traversal. The stem now states the standard front-and-rear pointer representation explicitly.
Final answer: Both enqueue and dequeue are O(1).