The Gateway to Computer Science Excellence
0 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
in Programming by Veteran (75k points)
edited by | 79 views

3 Answers

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.
by Active (1.2k points)
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

by Loyal (7k points)
–1 vote

Ans is C

by Active (1.2k points)

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

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.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,397 answers
105,455 users