0

hi,
i have seen somany people asking about fnding loops in a single linked list.
i would like to know is there any advantange or necessity for having loops in a linked lists.
is there any application that really requires loops in lists.

Thanks,
Gaiety

5
Contributors
6
Replies
8
Views
4 Years
Discussion Span
Last Post by rubberman
0

hmm.So you know how to find the loop ? Answer if floyd algorithm. And secondly, it 's appilcation is that place when you have made any searching algorthim and if it strucked in a loop, then you can use this if my searching algorithm is strucked somwehere or not. like in the graph searching. ;) thanks.

0

Sorry, my browser is behaving strangely.

yeah i know how to detect a loop, so many links are available.
hare and tortoise,mark the node as visited. etc
do you know any other efficient way and any other problems on lists.

1

i would like to know is there any advantange or necessity for having loops in a linked lists.

Well, a circular linked list is itself a loop, and they're quite useful. Internal cycles strike me more as a bug or faulty logic (hence the need for detection algorithms), but there may be niche uses that I'm not aware of.

0

Besides circular queues, looping pointer constructs are necessary to deal with when you have references to other types of items, and they may have a reference back to one of the parents in the hierarchy. There are a number of methods to detect these situations, some of which I have dealt with in the past when writing reference-counting garbage collectors for C++. One method is to use a stack and starting at the top of the list/tree and as you traverse each item, you search the stack for the next item. If found, then you have a circular (recursive) link. If not, then push the address onto the stack and continue. The cost is proportianate to the depth (complexity) of the list. I utilized some other techniques for my C++ garbage collector because I needed it to perform in a deterministic mannger for near real-time systems.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.