What is the time complexity of enqueue and dequeue operations in a queue implemented using a linked list with front and rear pointers?

Options

  • A. O(1) for both operations
  • B. O(n) for both operations
  • C. O(log n) for both operations
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

A. O(1) for both operations

Detailed Explanation

When a queue is implemented using a linked list with both front and rear pointers, enqueue and dequeue can both be performed in O(1) time. Enqueue adds a node at the rear, while dequeue removes the node from the front. Maintaining the rear pointer avoids traversing the complete linked list during insertion. Without an appropriate rear pointer, insertion at the end could require O(n) traversal.

← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts