GATE CSE 2004 | Question: 36

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 $\text{enQueue}$ and $\text{deQueue}$ can be performed in constant time?

• A. rear node
• B. front node
• C. not possible with a single pointer
• D. node next to front

Comments

A circular linked list given, meaning the last address of linked list will point to head or start of linked list. Also this implementation is of a queue.

Now from the diagram, rear and front are given, which means following queue property first in first out we are deleting from front and as the queue grows we are adding to rear.

Say, first 2 enters in the linked list.

Then 3 and then 5 and then 6 enters.

Now according to question,

The linked list will look like

2->3->5->6 (6 is rear latest added and 2 is front oldest added)

And since circular linked list is used  6 points to 2.

 

Now where to point the pointer p such that insertion and deletion takes constant time.

 

Clearly if we point it to front, then deletion is constant time but not the insertion as we need to travel the whole linked list it's n time.

 

But if we point to rear then insertion takes constant time as p is pointing to rear element. And deletion is also constant time as rear points to front so we can go to front directly.

Therefore, the p points to rear.

---

$$
\begin{aligned}
\textbf{P points to Rear:} & \quad \text{It is the same as having a rear pointer; P simply acts as an additional pointer to the rear node.} \\[6pt]
\textbf{P points to Front:} & \quad \text{If P points to the front and we perform a dequeue, the front moves to the next node.} \\
                           & \quad \text{The old front node gets deleted, but P still points to that deleted node,} \\
                           & \quad \text{so P becomes a dangling pointer.}\\

\end{aligned}
$$
correct me, if i am wrong?

---

@duckduck if P points to front, then it takes O(n) to make rear point to the node next to front so it is not correct answer.

Answer 1

The pointer points to the Rear node.

EnQueue: Insert newNode after Rear, and make Rear point to the newly inserted node: 

//struct node *newNode;
newNode->next = rear->next;
rear->next = newNode;
rear=newNode;

DeQueue: Delete the Front node, and make the second node the front node.

//rear->next points to the front node.
//front->next points to the second node.
struct node* front;
front = rear->next;
rear->next = front->next;
free(front);

---

Since there has been a lot of confusion in the comments, let me explain the answer using the pointer `p`

Note that the answer remains unchanged – the below code is just written in a different style.

struct node *p; // a pointer to the rear node

void enqueue(struct node *item) {
    item->next = p->next;
    p->next = item;
    p = item;
}

void dequeue() {
    struct node* temp = p->next;
    p->next = p->next->next;
    free(temp);
}

 

A single variable $p$ is used to access the Queue

This means that the data-structure only tracks the rear node.

You can create as many temporary pointers as you want – that has nothing to do with the data-structure’s internals.

In enqueue, there’s an extra pointer struct node *item because if you wish to enqueue something, you need that thing in the first place.

In dequeue, there’s an extra pointer struct node *temp because if you don’t keep track of the thing that you’re removing in order to free the memory, you will have a memory leak in your code.

Comments

P Node at the Rear Node is Rear Node Itself  : )

---

This explaination is wrong if we had front and rear pointer then we would have solved it O(1) without P, here in the question they showed front and rear for the sake of understanding with the use of p only we have to think and answer

---

got it , so if the P is at the rear node or refering to rear node , then only the operation is happens in constant time right ?

Answer 2

The pointer points to the Rear node.

---

EnQueue: Insert newNode after Rear, and make Rear point to the newly inserted node:

//struct node *newNode;
newNode->next = p->next;
p->next = newNode;
rear=newNode;

---

DeQueue: Delete the Front node, and make the second node the front node.

rear->next = rear->next->next;

Comments

https://www.youtube.com/watch?v=eui68AspjJU

---

Using extra pointer is not correct way to solve as it has only one pointer given Ans should be c .It is not possible with a single pointer.@Arjun sir

---

I think Simple ans is.. If we put node in front then we can not access rear (deletion) in constant time.. But if we put node in rear we can access front and rear in constant time (single linked list cannot access previous node)

Answer 3

Answer should be A.

P should point to Last node(rear), so as to perform enqueue in constant time.

To perform dequeue operation, since it is circular linked list, rear node will point front. Therefor dequeue can be performed as below:

temp= p->next->next//stores the address of node next to front node.

Delete (p->next)// delete current front node

p->next= temp// update the rear node to point to new front node.

Thus dequeue can also be perform in constant time.

Answer 4

Here is the idea :

Answer 5

answer should be C

enqueue is possible with 1 pointer but for dequeue we have to take 1 more pointer bcoz if dequeue compulsory we have to free the memory also which is not possible with only 1 pointer.if modify then we can do whatever we want but in dequeue free the memory also.

@ arjun sir plz verify

Comments

i was also thinking the same. answer should be c.

---

if dequeue compulsory we have to free the memory also which is not possible with only 1 pointer

How about this?

Assume p is pointing to rear node and p->next is pointing to the 1st node and we need to deQueue and also free the 1st node

 

front = front-> next;

free(p->next);

rear-> next = front;

p->next = front;

---

They are asking to complete the operation with constant time not a single pointer.

Answer 6

We do insertion by cutting in between Rear and Front

and

we do deletion by forwarding Front pointer and updating Rear accordingly. so ans is rear end