The Gateway to Computer Science Excellence
+13 votes
2.7k 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 by Boss (30.2k points) | 2.7k views
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!

3 Answers

+17 votes
Best answer

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

$p \rightarrow next=q \rightarrow next$

$q \rightarrow next=p$

So, two pointers,

Answer is (B).

by Active (4.1k points)
edited by
+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
2 is the answer in case of single circular linked list

4 is the answer for the double circular linked list.

@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

@Soumya , Sentinel node is just a dummy node which tells that list is now ended and it avoids the loop. We can put "end_marker" as its value which tells that list is now ended or search is now finished for an element. This end_marker can be anything like  $ or any special character or combination of special characters ... but it should not be matched with any key element of the list. So we have to put a value which we don't generally use while creating a list of elements.

According to wikipedia :-

In computer programming, a sentinel value (also referred to as a flag value, trip value, rogue value, signal value, or dummy data) is a special value in the context of an algorithm which uses its presence as a condition of termination, typically in a loop or recursive algorithm.

Please check here. Here, value of the sentinel node is taken as $v$.

0

@ankitgupta.1729

2 is the answer in case of single circular linked list

4 is the answer for the double circular linked list.
 

this is correct statement. right??

So, C) also a true option, isnot it?? 

+6 votes

Image result for insertion in circular linked list

So Option B is correct

by Boss (11.4k points)
0
So if i insert in the start,head will be modified ,so this accounts for 3 total?
0

Y->next = Head->next ; Head->next = Y; 

0
I think you are taking a extra modification pointer, why I'm saying that because if you took "head" pointer for your facility (we can't take anything extra other than said in the question itself) I can also take "end" and "middle" pointer too then there will be 5 pointer modification.

"Always try to work only with what is strictly given in the question. Take extra things in consideration only when question can't be solved without it or detection of this extra thing is the purpose of question itself."
0
Here if we see the term "modification of pointer" then are we also considering the incoming new node's pointer modification. Because if we go by original list, then only the previous node's pointer will be modified.
0
@Vivekk,Yes we have to modify the incoming new node's pointer modification as well. But what is important is the position where it is being inserted. Read the above comments. And please note the list is circular. So the modification is done accordingly.
+3 votes

Note that in a circular linked list, the next of the last node points to the head of the list.

 

Let $\mathrm{p}$ be a variable pointer and $\mathrm{head}$ is the pointer of the circular linked list.

Now to insert a new record (node) $\mathrm{q}$, we have to loop through the linked list from the head to the last node like this pseudocode below.

p=head
while(p->next!=head)
{
    p=p->next;
}

After finishing the loop, we will reach the last node meaning that $\mathrm{p}$ is now the last node. So we need to append the new node $\mathrm{q}$ to the next of $\mathrm{p}$. Then finally the next of $\mathrm{q}$ will have to point to the head since the linked list is circular. The pseudocode for this task is below.

p->next=q;
q->next=head;

 

$\therefore$ There needs modification of two pointers.

 

So the correct answer is B.

by Active (3.2k points)
edited by
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
50,645 questions
56,601 answers
195,852 comments
102,211 users