Awesome q2a theme
0 votes
20 views

In below question, it can be done via both front and rear node as well, isn't it?

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?

  1. rear node
  2. front node
  3. not possible with a single pointer
  4. node next to front

https://gateoverflow.in/1033/gate2004-36

The selected answer mentions only rear node while the nptel video below shows for front node. Please let me know if I'm missing something.

https://youtu.be/PGWZUgzDMYI?t=31m32s

in DS by (6 points) | 20 views
0
What you think ?
0

Think about the cases

  1. Singly Linked List
  2. Doubly Linked List
0
I think it is possible with both rear and front node separately. For rear node, explanation is already provided by Pragy in the selected answer. For front node, enqueue and dequeue can be done as follows.

Enqueue: Create a new node. Copy the contents of front node into this newly created node. Make it point to the node next of front node. In the existing front node, copy the new key to be enqueued. Make the existing front node point to the newly created node. Move the pointer to front node from existing front node to the newly created node.

Dequeue: Copy the contents of node next to front node, into the front node. Make the front node point to the third node. Delete the 2nd (node next to front) node.

These are constant set of operations irrespective of the number of elements in the list.

1 Answer

0 votes

The figure clearly shows it is a singly circular linked list. So P must point to the last node as with last node, we can Enqueue elements and as it is a circular linked list so we can access front node so Dequeue opeartion can be done in O(1) time. But if P points to front node then as it is a circular singly linked list so accessing rear node will take O(n) time which is NOT Constant .

by (82 points)
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Oct 2019
  1. GAITONDE

    410 Points

  2. Satbir

    317 Points

  3. Rudr Pawan

    163 Points

  4. srestha

    132 Points

  5. Mk Utkarsh

    127 Points

  6. Debapaul

    94 Points

  7. chandrikabhuyan8

    83 Points

  8. Shaik Masthan

    79 Points

  9. Verma Ashish

    77 Points

  10. !KARAN

    74 Points

Monthly Top User and those within 60% of his/her points will get a share of monthly revenue of GO subject to a minimum payout of Rs. 500. Current monthly budget for Top Users is Rs. 450.
1,680 questions
1,088 answers
4,555 comments
89,591 users