Queues-and-Linked-Lists
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) |
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.
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.