- Gate 2001

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 enQueue and deQueue can be performed in constant time?

**(A)** rear node

**(B)** front node

**(C)** not possible with a single pointer

**(D)** node next to front

**Explanation:**

when we point p at rear then we can also access front in O(1) time. So enque and deque can be done in O(1) time

We can also point p at front and both the operations enQueue and deQueue can be performed in constant time

**Deque:**

Note: p is at front

Copy the p–>next value to p–>value

Take temp pointer and hold p->next

Link p->next to temp->next

free(temp)

**Enqueue**

Create a node and say pointer to it is newnode

Write p->value into new node

p->info = value to be inserted

Link newnode->next=p->next

p->next = newnode