为什么我们需要检测链表中的循环 [英] Why do we need to detect a loop in a linked list

问题描述

我看到了很多关于如何检测链表中的循环的问答，但是我想了解为什么我们要这样做，换句话说，检测链表中的循环的实际用例是什么

I see many Q/A on how to detect a loop in linked list, but I want to understand is why we want to do that, in other words what are the practical use cases of detecting a loop in a linked list

推荐答案

在现实生活中，您可能永远都不需要检测链表中的循环，但是执行该操作的算法很重要，我已经在其中使用了它们.现实生活很多次.

In real life, you'll probably never need to detect a loop in a linked list, BUT the algorithms for doing that are important and I have used them in real life many times.

例如，在应该是树形的情况下，经常会递归地处理链接的数据结构.但是，如果它不是树形的并且具有循环，则将导致无限递归和堆栈溢出，因此我想在它爆炸之前抓住它.我通常使用Brent的循环查找算法，因为它很容易适应我的递归处理，并且开销极低.

Pretty often, for example, I will process a linked data structure recursively when it's supposed to be tree-shaped. If it isn't tree-shaped and has a cycle, however, that would cause infinite recursion and a stack overflow, so I like to catch that before it explodes. I usually use Brent's cycle-finding algorithm for that, because it's easy to fit into my recursive processing and has extremely low overhead.

循环查找算法在Pollard的"rho"分解算法中也很有用( https://en .wikipedia.org/wiki/Pollard％27s_rho_algorithm )

Cycle finding algorithms are also useful in Pollard's "rho" factorization algorithm (https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm)

学习这些算法时所学的思想也将在以后学习其他更复杂的东西时有用.

The ideas you learn when learning about these algorithms will also be useful when learning other more complex things later on.

ETA:

我应该补充说，错误地产生周期的常见情况是用户专门创建链接的情况.例如，在Java中，一个类可以具有超类，例如，程序员编写class C extends A {}. extends关键字在类之间创建链接.如果他还写class A extends C，则说明他已经创建了一个循环，编译器必须检测到这种情况.

I should add that common situations that produce cycles by mistake are those in which users specifically create the links. For example in Java a class can have a superclass, and the programmer writes class C extends A {}, for example. The extends keyword creates a link between classes. If he also writes class A extends C, then he has created a cycle and the compiler has to detect that condition.

这篇关于为什么我们需要检测链表中的循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！