how to identify loop in a linked list

[Shashank Rudra]

Hi Guys

We are given a linked list, that might have some loops. few of them can be seen as under


1 ---> 2 ---> 3 ---> 4
|                   ^
|                    |
|                    |
-----> 5 ------>

So here is a loop - 1 2 3 5.

How to find such loops? Does java linked list also have multiple pointers like in C++.

[Henry Wong]

The detecting of loops in a linked list, is a classic algorithm problem. There is actually a solution that can do it in O(n), which admittedly, if asked during an interview, I couldn't give the answer -- but I am sure it can be googled.

As for the Java collections implementations, I wouldn't worry about those. As long as you don't use threads on a non-synchronized collection, your chances of creating a loop is zero.

Henry

[Jesper de Jong]

java.util.LinkedList is implemented as a doubly linked list, i.e. each node in the list has two pointers - one to the next and one to the previous element.

I don't understand the arrows in your picture. What exactly do the two arrows that come from element 1 mean with regard to LinkedList? Also, I don't see a loop in your picture. There's no way you can follow the arrows and come back to the element you started at. Sure, there are two paths from 1 to 3, but not a loop.

Are you really talking about linked lists, or is this really about finding loops in a graph?

[Shashank Rudra]

Thanks Henry for your comments.

Here is a link that can be followed to get an overview of the same in terms of algorithm(logic).
http://ostermiller.org/find_loop_singly_linked_list.html

Some ways will not work in languages like Java where you don't have access to the memory address.

Some people might say that

Object obj = new Object(); 
System.out.println(obj.toString());

will get you a memory address. But I don't buy that, and think that is a hashcode basically which is returned by toString() method for each class unless they override it to some meaningful implementation. (please comment on this if not right)

A link related to java perspective is here
http://eddii.wordpress.com/2006/11/15/detecting-infinite-loop/


Any better link or comments guys.

[Joanne Neal]

Sam Giraldo wrote:... and think that is a hashcode basically which is returned by toString() method for each class unless they override it to some meaningful implementation. (please comment on this if not right)

Correct. From the javadoc for Object.toString()

The toString method for class Object returns a string consisting of the name of the class of which the object is an instance, the at-sign character `@', and the unsigned hexadecimal representation of the hash code of the object.

[Shashank Rudra]

thanks Joanne for clearing this up.