GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
626 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 (38.8k points)   | 626 views
what the mean of option C) Multiple pointers.

is it more than 2 pointers or something else ?

1 Answer

+5 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 (4k points)  
selected by
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 :(


Top Users Sep 2017
  1. Habibkhan

    6970 Points

  2. Warrior

    2490 Points

  3. Arjun

    2368 Points

  4. rishu_darkshadow

    2136 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. makhdoom ghaya

    1760 Points

  8. manu00x

    1750 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,060 questions
33,668 answers
79,747 comments
31,079 users