# GATE1987-1-xv

4.2k views

In a circular linked list oraganisation, insertion of a record involves modification of

1. One pointer.
2. Two pointers.
3. Multiple pointers.
4. No pointer.
in DS
0
what the mean of option C) Multiple pointers.

is it more than 2 pointers or something else ?
0
In any case, only two pointers will be modified!

Suppose we have to insert node $p$ after node $q$ then

$p \rightarrow next=q \rightarrow next$

$q \rightarrow next=p$

So, two pointers,

edited
1
Doesn't it involves setting of a single pointer. Initally when a new node is created the next field of the new pointer is set to NULL. Isn't it?
–2
No it doesn't
1
what if the node is inserted at beginning head pointer is also modified. So it should be three.
0
Actually what is important is the specific position where the node is to be inserted. That is necessary. So question should be based on position and then modification of pointers. :)
0

no  Aarzoo Varshney   it is also 2 in case of beginning head pointer

0
How it will 2 in case of inserting at beginning??
0
if count setting of start pointer then its three pointers modification otherwise two .

but usually setting of start pinter isnt count in modification of pointers modification
11
Actually optimized algorithm of circular linked list doesn't use head pointer..It uses a sentinel node which points to the last node of the circular linked list so that insertion at front and end can be done efficiently..

so basically for insertion only 2 pointers needs to be modified.

p->next=q->next

q->next = p
1
What If I want to insert an element at the end of the list? In that case I need to update sentinel node as well. Please clarity
3

Shaded node is the sentinel node.

In the above implementation insertion at any location (including beginning and end) requires modification of 2 pointers only.

About other implementations- If we don't count setting of head, tail or sentinel then insertion requires modification of 2 pointers only.

0
@Soumya. In case of sentinel representation , if we want to add a node at the end, then can we do it in constant time? If you have any reference then, please share the link.Thank you..
1
No. Because for insertion at the end. We need a pointer to the last node (the one before sentinel node). So for this, we have to traverse the whole list.

Sorry, I don't have any reference :(
0
Modification means changing the existing value.So,in case of this why setting of pointer for a new node has been counted as modification?
2

@Soumya29-When we have a sentinel node and also the pointer to it, why can't we add a node in last in the circular single linked list in constant time?
0

@Ayush, So sorry I missed your comment.
We need a pointer to the node just before the sentinel node to insert a new element at the end. Sentinel node is always the last node.

In fact, there is no need of sentinel node as there is no notion of beginning and end in case of the circular linked list. We just have a pointer to any node, so that we can traverse the whole linked list.

Sentinel node is used when we want to keep track of the beginning and end of the list.

@Sourav, This is the reference-  Sentinel_node#Linked_list_implementation

1

@Soumya , If we have a pointer to a node and if we want to insert a new data node before that node where the pointer is given then still we can insert that new data node in constant time i.e. $O(1)$.

you can check here how to do it.

and pointer is not necessarily given only at sentinel node. It can given to its previous node also.It is just an implementation. check here.

here, it is mentioned that :-

"List handle should then be a pointer to the last data node, before the sentinel, if the list is not empty; or to the sentinel itself, if the list is empty."

0
@Ankit... Indeed, everything depends on implementation.

But it that particular implementation (The one in pic above). Can you please tell me how will you  insert at end in constant time. Pointer to sentinel is given and we can't store any key value in it so that we can swap values.
0