Awesome q2a theme
0 votes
30 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) | 30 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 (85 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users May 2020
  1. Kushagra गुप्ता

    97 Points

  2. praveen modala

    15 Points

  3. ramcharantej_24

    15 Points

  4. abhishek tiwary

    12 Points

  5. srestha

    12 Points

  6. Dtiwari

    9 Points

  7. Shivateja MST

    8 Points

  8. ankitgupta.1729

    8 Points

  9. Rashimdixit

    7 Points

  10. Bhavya1902

    7 Points

7,376 questions
1,741 answers
10,682 comments
90,352 users