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? (GATE 2004) rear nodefront nodenot possible with a single pointernode next to front
Question
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? (GATE 2004) rear nodefront nodenot possible with a single pointernode next to front
Solution
The answer is "rear node".
Here's why:
In a circular linked list, the last node points to the first node making it a circle. If we have a pointer to the rear node, we can perform both enQueue and deQueue operations in constant time.
-
enQueue operation: To insert an element, we need to add a node after the rear node and then move the rear pointer to the next node. This can be done in constant time if we have a pointer to the rear node.
-
deQueue operation: To delete an element, we need to remove the node that the rear node is pointing to. This can also be done in constant time if we have a pointer to the rear node because the node before the rear node is the front node in a circular linked list.
Therefore, to perform both operations in constant time, the pointer p should point to the rear node.
Similar Questions
n linked list implementation of queue, if only front pointer is maintained, which of the following operation take worst case linear time?
n linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into EMPTY queue
Given a queue implemented using a linked list, the rear pointer points to the rear node, and front pointer points to the front node of the queue, which of the following statement is not possible in O(1) complexity*2 pointsinsertion at rearinsertion at frontdeletion at frontdeletion at rear
In linked list implementation of a queue, the important condition for a queue to be empty is?
A list of elements in which enqueue operation takes place from one end, and dequeue operation takes place from one end is__a.Binary treeb.Stackc.Queued.Linked list
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.