1. 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?

circularLinkedList

(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