GO Classes Test Series 2023 | Data Structures | Test 3 | Question: 6

Answer 1

Implementing a queue using singly linked list with head and tail pointers – 

front of queue $\equiv$ tail of the list.

In front we do dequeue(), deleting one node pointed by tail is O(n). Since, we have to go to n-1^th node to adjust pointers.

rear of queue $\equiv$ head of the list.

In rear we do enqueue(), adding one node pointed by head is O(1).

Answer :- B.

Comments

I didnot understood it can you @shishir__roy please elaborate it a bit.

---

it is given that queue is implemented using “singly linked list”

in singly linked list BACK TRAVERSAL is not possible (that’s why we use doubly linked list for back traversal). We can conveniently enqueue in O(1) time at the head and make the head point to the newly added node. Now to dequeue we need to initialize a temp pointer at the head and traverse till:

temp→ next != front  ( O(n)).

Now, 

below steps need O(1) time

free(front);

front = temp;

temp = head;// for future dequeue we will again traverse the complete list.

Answer 2

Question says:  Implementing  a queue using Singly Linked List with head and tail pointer.

It is also given that:-

rear==head of SLL  &&  front == tail of SLL.So,

For Enqueue():- Insert a node at beginning of SLL. =O(1).

For Dequeue():-Delete a node from end of SLL. That requires the pointer of second last node (n-1)th node to delete last node . To traverse till 2nd last node it will take O(n).So,overall TC to dequeue is==O(n).

Note: We know that we have the pointer to the last node(tail pointer) after every Enqueue but ,since it is SLL se cannot move to prev node.

Correct Answer:B