In a linked chain implementation of a queue, the performance of the enqueue operation is: A. O(1) B. O(n) C. O(log n) D. O(n^2)
Computers and Technology · College · Sun Jan 24 2021
Answered on
The correct answer is option A. O(1)
In a linked chain implementation of a queue (which can also be referred to as a linked list queue), the enqueue operation, which involves adding a new element to the rear of the queue, is an O(1) operation. This constant time complexity is possible because in a linked list, the end of the queue maintains a pointer (or reference) to the last node. When a new element is enqueued, it is simply added after the last node and the rear pointer is updated to this new node. No traversal of the entire list is required, and the operation takes a consistent amount of time regardless of the size of the queue.