Question

A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O(1)O(1) time?

I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.

Choose one option
Official answer and solution
Official answer
B
From
Official GATE 2017 answer key

Solution

Recall the structural pointer invariant of a circular linked list representing a FIFO queue.

In a queue, elements are deleted from the FRONT and inserted at the REAR.
In a circular singly linked list:

  • The nodes are arranged in sequence from FRONT to REAR: FRONT -> Node2 -> ... -> REAR.
  • To make the list circular, the next pointer of the REAR node must point back to the FRONT node: REAR->next = FRONT.
  • When inserting a new node new_node at the rear in O(1)O(1) time:
    new_node->next = REAR->next; (which is FRONT)
    REAR->next = new_node;
    REAR = new_node;
  • When deleting the front node in O(1)O(1) time:
    FRONT = FRONT->next;
    REAR->next = FRONT;

Therefore, the next pointer of the rear node points to the front node (Statement II is CORRECT).
Statement I claims that the next pointer of the front node points to the rear node, which is only true for a list of length 1, not in general.

Thus, statement II only is correct, matching option B.

Final answer

B

Common trap

Thinking a circular list requires both front pointing to rear and rear pointing to front, which would be bidirectional (doubly linked).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2017 Computer Science and Information Technology (CS) Session 2
Question
13 of 65, printed as CS Q.13
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.