edited by
772 views
1 votes
1 votes

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 ?

  1.  node next to front
  2.  front node
  3.  not possible with a single node
  4.  rear node
edited by

3 Answers

0 votes
0 votes
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.
0 votes
0 votes

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

–1 votes
–1 votes

Ans is C

Answer:

Related questions

0 votes
0 votes
1 answer
2
Bikram asked Nov 26, 2016
1,637 views
Three algorithms do the same task. Algorithm One is $O(N)$ and Algorithm Two is $O(\log N)$ and Algorithm Three is $O(N1/2)$. Which algorithm should execute the fastest f...
0 votes
0 votes
0 answers
3
1 votes
1 votes
1 answer
4
Bikram asked Nov 26, 2016
842 views
Consider an array of elements $6 \ 4 \ 5 \ 3 \ 7 \ 1$. The contents of the array after three passes when we apply Bubble Sort on it is$3 \ 4 \ 1 \ 5 \ 6 \ 7$$3 \ 4 \ 5 \ ...