circular link list

[apurva agarwal]

insert a node in circular link list without traversing it.
:?:
you have to insert the node at any place "without traversing it

help me out!!! in this

[ganesh]

If you want to insert a node a node at a particular position, You must know the key value or the distance from head (or) tail. In both the cases you have to traverse the list. If the memory is not dynamic then, you can just add the distance*sizeofnode to the head and insert the node there.

If you don't consider the position of insertion, the answer becomes childish.

[wild_potatos]

you can do it as follows, use a pointer to point to the last node " consider the list as a queue " of the list consider it's name is ((( last ))) and the node you want to add is ((( index ))) and define another pointer ((( temp )))

then :

temp = last;
last->pointer = index;
last = index;
last -> pointer = temp->pointer;

and then have fun... :) :) :surprised

[Chainsaw]

Huh? It sounds like the assignment is, given a node in the target list, insert a new node into it. Otherwise you'd have an assignment like "insert in sorted order"

So, given a target node called 'target' and you want to insert 'toBeInserted' you generally need to:

A) Remove the toBeInserted node from whatever list its on
B) Add it to the new list before or after 'target', whichever is appropriate.

And the general steps for removal are (with the current node bing 'this'):

set prior's next to this next
set next's prior to be this' prior
set this' next to this
set this' prior to prior

and to insert before target you do something like this:

this' next is target
this' prior is target's prior
target's prior is this
this' prior's next is this

(to insert after is similar, but slightly different of course)

Hope that helps!

(note to moderator's: trying not to do the assignment, but to explain it. Walks a fine line, there)

[Chainsaw]

Oops! Bug! The last line in 'general steps for removal are' should read:
set this' prior to this (not to prior)

[apurva agarwal]

well explain it in amore simple manner i could not reall yget the whole of it

[Chainsaw]

:-(

I guess I should stop answering questions with anything but Google answers. Here's what Google suggests for "circular linked list insertion algorithm":

http://www.greatsnakes.com/savannah/clist.asp