The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
819 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.
asked in DS by Veteran (42k points) | 819 views
what the mean of option C) Multiple pointers.

is it more than 2 pointers or something else ?

2 Answers

+7 votes
Best answer
suppose we have to insert node p after node q then

p->next=q->next

q->next=p

so two pointers

b)
answered by Loyal (4.3k points)
selected by
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?
No it doesn't
what if the node is inserted at beginning head pointer is also modified. So it should be three.
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. :)

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

How it will 2 in case of inserting at beginning??
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
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
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

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. 

@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..
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 votes

Image result for insertion in circular linked list

 

So Option B is correct

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


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

28,831 questions
36,676 answers
90,579 comments
34,638 users