![GATE 2017 [Set-2]](https://solutionsadda.in/wp-content/uploads/2019/05/green-new-logo.png){kind=logo}
Question 7969 – GATE 2017 [Set-2]
November 16, 2023Question 7977 – GATE 2017 [Set-2]
November 16, 2023GATE 2017 [Set-2]
|
Question 13
|
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) time?
I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.
I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.
|
I only
|
|
|
II only
|
|
|
Both I and II
|
|
|
Neither I nor II
|
Question 13 Explanation:
1. Next pointer of front node points to the rear node.
2. Next pointer of rear points to the front node.
So if we consider circular linked list the next of 44 is 11.
If you place pointer on next of front node (11) then to reach 44 (last node), we have to traverse the entire list.
For delete O(1), for insert O(n).
It is clearly known that next pointer of rear node points to the front node.
Hence, only II is true.
2. Next pointer of rear points to the front node.
So if we consider circular linked list the next of 44 is 11.
If you place pointer on next of front node (11) then to reach 44 (last node), we have to traverse the entire list.
For delete O(1), for insert O(n).
It is clearly known that next pointer of rear node points to the front node.
Hence, only II is true.
Correct Answer: B
Question 13 Explanation:
1. Next pointer of front node points to the rear node.
2. Next pointer of rear points to the front node.
So if we consider circular linked list the next of 44 is 11.
If you place pointer on next of front node (11) then to reach 44 (last node), we have to traverse the entire list.
For delete O(1), for insert O(n).
It is clearly known that next pointer of rear node points to the front node.
Hence, only II is true.
2. Next pointer of rear points to the front node.
So if we consider circular linked list the next of 44 is 11.
If you place pointer on next of front node (11) then to reach 44 (last node), we have to traverse the entire list.
For delete O(1), for insert O(n).
It is clearly known that next pointer of rear node points to the front node.
Hence, only II is true.
Subscribe
Login
0 Comments