The Gateway to Computer Science Excellence
+28 votes

A circularly linked list is used to represent a Queue. A single variable $p$ is used to access the Queue. To which node should $p$ point such that both the operations $\text{enQueue}$ and $\text{deQueue}$ can be performed in constant time?

  1. rear node
  2. front node
  3. not possible with a single pointer
  4. node next to front
in DS by Veteran (52.2k points)
edited by | 6.9k views
the condition should be given in question that the next of rear points to the front node because that will be the case only when the queue is full.

7 Answers

+80 votes
Best answer

The pointer points to the Rear node.

EnQueue: Insert newNode after Rear, and make Rear point to the newly inserted node: 

//struct node *newNode;
newNode->next = rear->next;
rear->next = newNode;

DeQueue: Delete the Front node, and make the second node the front node.

//rear->next points to the front node.
//front->next points to the second node.
struct node* front;
front = rear->next;
rear->next = front->next;

by Boss (22.8k points)
selected by

Awesome answeryes

what does constant time means in the questn...?
@Dhalrya: Constant time means $\Theta(1)$ time
thank u Pragya...:)
0 nott getting this solution , can u plzz explain
Why we are using another front to delete previous front ? This code is much better I think...

temp = front ;

rear --> next = temp --> next;

front = rear --> next;

free (temp);
they were not metioned rear and front why are u taking rear and front????????????????????????????????????

i m in confusion
You can't use $front$ and $rear$ pointers. You only have to use pointer $p$. Although the answer *is* "rear node", your implementation of $enQueue()$ and $deQueue()$ is wrong.
@ pragy

how can you use front and rear bcoz A single variable p is used to access the Queue
@rajoramanoj  read the question  and explanations  (of pragya) again
Why are we using front pointer? Although it is possible but the question says single variable is used to access linked list .We should not create new variable.Please clarify
@Arjun Sir i think this is wrong explanation they have not mentioned any front and rear pointer in the question we can only make use of p pointer
@srestha dont u think he used additional pointers which were not mentioned in the question .. only one pointer should be used


If answer is rear node,then it is not possible with one pointer p.


@ Venkat 


front is not extra created

It is already in question

just we need to free(front)

@Rahul Sharma But GATE asked to implement it with one node only.

@srestha I think here front and rear are just mentioned in the question to indicate which nodes are front(first node) and rear(last node) and they are not pointers. Although the answer remains same that P points to rear node.

$\rightarrow$ operator uses with pointer
Yes, but in question it isn't mentioned that front and rear are pointers.

Oh my, this questions seems to have attracted a lot of confusion!

Rest assured, my answer is correct. Please re-read the question carefully. Think about what it is asking. Then re-read the answer carefully and think about what the answer is doing. Give it some time. If the confusion still persists, comment again, and I will do a ELI5.

so where is P variable  ??? in your ans


The pointer points to the Rear node

P points to the same node as rear and this the only thing which is asked. P and rear will have the same address.


@Pragy Agarwal It is possible with front node as well. 

Check the below link.

To those who are thinking we have used two pointers rear and front while the question is asking for a single variable p:

if we make p point to the rear node, then we can also access front node, i.e. we can access both front and rear with single pointer p. It is very  simple.
+13 votes

The pointer points to the Rear node.

EnQueue: Insert newNode after Rear, and make Rear point to the newly inserted node:

//struct node *newNode;
newNode->next = p->next;
p->next = newNode;

DeQueue: Delete the Front node, and make the second node the front node.

rear->next = rear->next->next;
by Active (2.3k points)

what does constant time means in the questn...?

simply we are not traversing queue thats why we not using extra time . we are performing both the opration in constant time. like O(1)
This is not deletion. Memory is not de allocated
Yup. Hence not possible with a single pointer p.

Using extra pointer is not correct way to solve as it has only one pointer given Ans should be c .It is not possible with a single [email protected] sir
+4 votes

Answer should be A.

P should point to Last node(rear), so as to perform enqueue in constant time.

To perform dequeue operation, since it is circular linked list, rear node will point front. Therefor dequeue can be performed as below:

temp= p->next->next//stores the address of node next to front node.

Delete (p->next)// delete current front node

p->next= temp// update the rear node to point to new front node.

Thus dequeue can also be perform in constant time.

by Active (2.4k points)
edited by
0 votes
answer should be C

enqueue is possible with 1 pointer but for dequeue we have to take 1 more pointer bcoz if dequeue compulsory we have to free the memory also which is not possible with only 1 pointer.if modify then we can do whatever we want but in dequeue free the memory also.

@ arjun sir plz verify
by Active (4.5k points)

Bikram sir plz verify this ans 

@Arjun sir what he said is correct answer should be C if we take use of front and rear whats the use of giving temporary pointer P even without it we can do
i was also thinking the same. answer should be c.
0 votes
We do insertion by cutting in between Rear and Front


we do deletion by forwarding Front pointer and updating Rear accordingly. so ans is rear end
by (141 points)
edited by
–1 vote
Answer can be both....if p points to rear then answer is already given

Now the  case if p points to front:

Enqueue: the data of the node pointed by p in a temp variable.

2.copy the data of new node to the node p is pointing to.

3.copy the data of the temp variable to the new node created

4.make newnode->next=p->next point to the new node

5.make p->next=newnode

6.make p=p->next



1.copy the data of the node in p->next to p.

2.make p->next=p->next->next
by Active (3.8k points)
@Arjun sir : please check this
–2 votes
I think there is no front or rear pointer here only p pointer so enQueue() and deQueue operation should be this

1.) newNode-->next=p-->next-->next;

2.) p-->next-->next=NULL;

3.) free(p-->next);

4.) p-->next=newNode;
by Active (2.3k points)

yes u r right they were not mentioned about rear and front pointers they only give us pointer P

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,321 answers
105,156 users