3 ms·
> By now you may be wondering why we do not simply use a set, and return fast if we encounter a node already in the set. Or, indeed, to solve what we’re buildin
by e12e 5y ago
> By now you may be wondering why we do not simply use a set, and return fast if we encounter a node already in the set. Or, indeed, to solve what we’re building towards, we could just return the first value which is already in the set. (...)
> However, as I mentioned, this solution is spatially inefficient,
Typically you'd need to store N pointers, and the list would be of size N(size_of(pointer) + size_of(node)) - which would normally be much larger than the pointers? (otherwise use an array, perhaps?)
What are some real world cases where long linked list of very light nodes are best checked for cycles with this algorithm?
- thewakalix 5y agoPerhaps you don't have the entire linked list in memory, but are instead requesting individual nodes from a server.
- joppy 5y agoYou might have an abstract function f which takes and returns an integer, and you want to figure out if this function has “cycles”, eg if ffffff(n) = fff(n) etc. The numbers used might be enormous, and so trying to store them all is a non-starter.
- sischoel 5y agoIndeed, there are quite a few application in cryptography, where one has to search trough a huge space. Wikipedia actually listens a few: https://en.wikipedia.org/wiki/Cycle_detection#Applications https://en.wikipedia.org/wiki/Cycle_detection#Applications