Test by Bikram | Data Structures | Test 2 | Question: 28

Question

A circular linked list is used to represents a queue. A single variable L is used to access the queue. To which node should L point such that both the operation enqueue and dequeue can be performed in constant time ?

• A.  node next to front
• B.  front node
• C.  not possible with a single node
• D.  rear node

Answer 1

Answer is D) rear node because, from rear, we can go to front to delete and add a node(at rear) because we are at last node. We can't do this with any other node.

Answer 2

Ans is C

Comments

Answer D-- Rear Node is correct , just see this 

http://quiz.geeksforgeeks.org/data-structures-linked-list-question-12/

---

answer should be B. front node. as logic given in above link is right but direction is wrong. from front node dequeue operation occurs and from rear node new insertion is one. so direction moves from rear to front. just try to visualize.

---

read this why rear node

https://gateoverflow.in/1033/gate2004-36

http://quiz.geeksforgeeks.org/data-structures-linked-list-question-12/

Answer 3

Enqueue is done at the rear.

Dequeue is done at the front.

 

So we need to point to a node such that we can access both the front and the rear easily (in $O(1)$ time).

In circular LL, if we point to the rear, we can access rear and front easily. So, Option D

// front == (rear + 1) mod n.

 

---

 

Why are other options incorrect?

If we point to the front, to access the rear node, we have to traverse all the way to the other end, ie, $O(n)$

So, Option B

By extension Option A

And obviously since rear node is the right answer, Option C