CODEWITHSUNDEEP
algorithmdata-structureslinked-listcyclic-reference
Nikhil Bansal
Nikhil Bansal

Reputation: 119

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

Upvotes: 3

Views: 2126

Answers (3)

Matt Timmermans
Matt Timmermans

Reputation: 59154

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.

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.

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:

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.

Upvotes: 5

paxdiablo
paxdiablo

Reputation: 881323

Because, if you have a list like this (for example):

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

and the code to traverse it as follows:

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

then you will never complete the loop. It will happily process A, B, C, B, C, B, C,... for eternity (or until the heat death of the universe, whichever comes first).

A normal linked list will never have a cycle in it. In order to detect such a degenerate list, you can look at this answer.

Note that some cyclic linked lists are indeed valid. One example I've seen was a process list used for scheduling where the head and tail are irrelevant (since the thing that processes them wanted to loop over them forever). Hence the scheduler would be something like:

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

Upvotes: 0

no 36
no 36

Reputation: 45

linked list with loop has no end , linked list contains two links to some node Iterating through the linked list will yield all nodes in the loop multiple times A malformed (with unknown loop) linked list with a loop causes iteration over the list to fail because the iteration will never reach the end of the list. Therefore, it is desirable to be able to detect that a linked list is have loop before trying an iteration

you can find answer here

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

Upvotes: 0

Related Questions