Зачем нам нужно обнаруживать петли в связанном списке

Question

Я вижу много вопросов и ответов о том, как обнаружить цикл в связанном списке, но я хочу понять, почему мы хотим сделать это, другими словами, каковы практические случаи использования обнаружения цикла в связанном списке

Answer 1

связанный список с циклом не имеет конца, связанный список содержит две ссылки на некоторый узел Итерация по связанному списку приведет ко всем узлам цикла несколько раз. Искаженный (с неизвестным циклом) связанный список с циклом приводит к сбою итерации по списку, поскольку итерация никогда не достигнет конца списка. Поэтому желательно иметь возможность обнаружить, что связанный список имеет цикл, прежде чем пытаться выполнить итерацию

Вы можете найти ответ здесь

https://blog.ostermiller.org/find-loop-singly-linked-list

Answer 2

Потому что, если у вас есть такой список (например):

head -> A -> B -> C -+
             ^       |
             +-------+

и код для его обхода следующим образом:

node = head
while node <> null:
    processNode(node)
    node = node.next

тогда вы никогда не завершите цикл. Он будет радостно обрабатывать A, B, C, B, C, B, C,... вечность (или пока не наступит тепловая смерть вселенной, в зависимости от того, что наступит раньше).

Обычный связанный список никогда не будет иметь цикл . Чтобы обнаружить такой вырожденный список, вы можете посмотреть этот ответ .

Обратите внимание, что некоторые циклически связанные списки действительно действительны. Одним из примеров, которые я видел, был список процессов, используемый для планирования, когда голова и хвост не имеют значения (поскольку объект, который их обрабатывает , хотел , чтобы зациклить их навсегда). Следовательно, планировщик будет выглядеть примерно так:

curr = somePointInList()
while true:
    runForABit(curr)
    curr = curr.next

Answer 3

В реальной жизни вам, вероятно, никогда не понадобится обнаруживать цикл в связанном списке, НО алгоритмы для этого важны, и я использовал их в реальной жизни много раз.

Очень часто, например, я рекурсивно обрабатываю связанную структуру данных, когда она должна иметь древовидную форму. Если он не в форме дерева и имеет цикл, однако, это вызовет бесконечную рекурсию и переполнение стека, поэтому я хотел бы поймать это до того, как он взорвется. Для этого я обычно использую алгоритм поиска цикла Брента, потому что он легко вписывается в мою рекурсивную обработку и имеет чрезвычайно низкие накладные расходы.

Алгоритмы поиска циклов также полезны в алгоритме факторизации "rho" Полларда (https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm)

Идеи, которые вы узнаете при изучении этих алгоритмов, также будут полезны при дальнейшем изучении других более сложных вещей.

ETA:

Я должен добавить, что распространенными ситуациями, которые по ошибке производят циклы, являются те, в которых пользователи специально создают ссылки. Например, в Java класс может иметь суперкласс, а программист пишет, например, class C extends A {}. Ключевое слово extends создает связь между классами. Если он также пишет class A extends C, то он создал цикл, и компилятор должен обнаружить это условие.