4 ms·
How do you detect a cycle with linked lists? :) I actually have a side project where I've run into this - it's a distributed directed graph structure where the
by tunesmith 4y ago
How do you detect a cycle with linked lists? :) I actually have a side project where I've run into this - it's a distributed directed graph structure where the nodes can send messages to each other. It's intended to be acyclic, but "walking the graph" is really only used to send truth values, which are combined with others to run Boolean logic. So in that case, the occasional cycle doesn't matter, because if the calculated boolean value matches that of the node's internal state, it just can cease propagating. So a structural loop won't turn into an infinite processing loop.
The problem then becomes that I can't introduce NOT gates anywhere in a cycle, because then the bit will continue flipping and I'll get an infinite processing loop.
So it seems my only hope is external processes that continually walk the graph and keep track of where it visited to try and detect loops, and I don't like how that scales...
- bewaretheirs 4y agoSet two pointers to the head of the list. Step through the list by one element per iteration with one of them, and with the other, step every other iteration. If the two pointers are ever again equal you've found a cycle. If you hit end of list, no cycle.
- klysm 4y agoDoes the graph have static structure? I’m not sure if you’re describing something like an actor system.
- tunesmith 4y agoAkka cluster sharding :) Shape of the graph can change as processes are being run.
- dragontamer 4y agoWith "just" a linked list, you need a turtle (advance one-node at a time), and a hare (advance two-nodes at a time). If the turtle and hare ever meet, you have a cycle. Otherwise, if the hare reaches the end of the list, you don't have a cycle.
- timjver 4y agoJust in case performance matters, there is a more efficient way: have the tortoise stay in place and advance the hare only one node at a time, and assign the hare to the tortoise every time a power of 2 number of steps have been made. This is known as Brent's algorithm, and it requires fewer advancements than the original tortoise and hare algorithm by Floyd. Another notable advantage of Brent's algorithm is that it automatically finds the cycle length, rather than (in Floyd's case) any multiple of the cycle length. https://en.wikipedia.org/wiki/Cycle_detection#Brent's_algorithm https://en.wikipedia.org/wiki/Cycle_detection#Brent's_algori...
- Jtsummers 4y agohttps://rosettacode.org/wiki/Cycle_detection https://rosettacode.org/wiki/Cycle_detection Cycle detection in (currently) 44 languages. Most (all?) use Brent's algorithm. They're operating on an iterated function but converting most of these to detect cycles in a linked list would be straightforward.
- mdavidn 4y agoIt's not difficult. Keep a pointer to a recently-visited node. After visiting N nodes, update the pointer to the current node, but also double N. If the pointer ever matches the next node, the list has a cycle. The doubling of N ensures that even large cycles will eventually be detected.
- quickthrower2 4y agoCan you just store the first reference as a local variable and then compare each time you move to a new node? Or to save the comparisons make the thing the first node points to have a stop flag of some sort.
- mdavidn 4y agoThat approach works only when the first node is included in the cycle. Other cycles are possible.
- Jtsummers 4y agoConsider this kind of cycle: Head -> Node1 -> Node2 -> Node3 ^ | +-----------------+ If it's a circular list then your option would work, but not all cycles will produce circular lists.
- quickthrower2 4y agoThanks. This seems so obvious now! Always draw it out I guess.
- ufo 4y agoThere are a bunch of algorithms for detecting cycles. One of the classics is the tortoise and hare algorithm, which uses only O(1) space. https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoi...
- deleted 4y ago[deleted]
- Smaug123 4y agoOne of the standard texts on the matter: https://aphyr.com/posts/341-hexing-the-technical-interview https://aphyr.com/posts/341-hexing-the-technical-interview
- mst 4y agoRecycler. To be clear, http://trout.me.uk/gc/recycler-overview.pdf http://trout.me.uk/gc/recycler-overview.pdf There's also a paper with the full algorithm in that directory. It's how Nim's ORC collector works. (note that yes, I know, this is for collection, not cycle detection in general, but it's also brilliant and works)
- rightbyte 4y agoI would say the easiest way is to walk the graph and tag the nodes as visited. If you don't visit every node each iteration use a increasing key you store in each node.