Question 1

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?

θ(1), θ(1)
θ(1), θ(n)
θ(n), θ(1)
θ(n), θ(n)
       Data-Structures       Queues-and-Linked-Lists       Gate 2018
Question 1 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.
There is 1 question to complete.
PHP Code Snippets Powered By : XYZScripts.com