Linked List implementation of Queue

Question

Which of the following is true about linked list implementation of queue?
(a) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.
(b) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be
removed from the beginning.   
(c) Both of the above
(d) None of the above

Answer is (C)

But my doubt here is that:-

If we are allowed to use only singly linked list then option a) will take O(n) time to remove a node from the end of the linked list. So, in this case i.e. in case of singly linked list with O(1) TC answer should be (b)

But If we are allowed to use doubly linked list then answer should be C only

ryt?

Answer 1

Correct answer is C

both (a) and (b) are correct.

In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.
In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning. 

Time complexity has nothing to do in this question whether it is O(1) or O(n). 

Comments

But in the question, if the constraint is given that "singly linked list" and "O(1)" then (b) should be the answer right?

---

Yes you are correct.

When using SLL, for O(1) Enqueue should be at the End using REAR and Dequeue should be at the Beginning using FRONT.

then (b) is correct option.

While in option (a) Insertion at beginning will take O(1) but deletion at end will take O(n) as we need to point the node before last to delete the last element and it will take O(n) to to find it.

Answer 2

According to the question we need not worry about the TIME COMPLEXITY. Just we need to check whether it is going to worry or not that's it

Answer 3

The correct answer is (b). In a linked list implementation of queue, new nodes are inserted at the end in the push operation and removed from the beginning in the pop operation.

Answer 4

Think in one simple rule:

In Queue using linked list, insertion and deletion happen at opposite ends.

So:

• Insert at front → Delete at rear.

• Insert at rear → Delete at front.

• Both valid.