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
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.
Quoted Text Here
floyd
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.
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.
Yes,looped linked-list is useful in the implementation of circular queue.
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.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.