ISRO CS 2015
April 16, 2024Question 7875 – Data-Structures
April 17, 2024Question 7851 – Data-Structures
A queue is implemented using a non-circular singly linked list. The queue has a head pointer and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let ‘enqueue’ be implemented by inserting a new node at the head, and ‘dequeue’ be implemented by deletion of a node from the tail.
Which one of the following is the time complexity of the most time-efficient implementation of ‘enqueue’ and ‘dequeue, respectively, for this data structure?
Correct Answer: B
Question 7 Explanation:
For insertion of node at the beginning of linked list only need manipulation of pointers so θ(1) time.
But if we have pointer to the tail of the list in order to delete it, we need the address of the 2nd last node which can be obtained by traversing the list which takes O(n) time.
But if we have pointer to the tail of the list in order to delete it, we need the address of the 2nd last node which can be obtained by traversing the list which takes O(n) time.
θ(1), θ(1)
θ(1), θ(n)
θ(n), θ(1)
θ(n), θ(n)