java infinite loop while using collections

Question

Please suggest me to solve the below infinite loop . Class object contains the collection of same type objects. While converting to String , The object calls the toString of each object in the collection. Hence it leads to infinite loop. Please dont use any static variables.

import java.util.LinkedList;

/**
 *
 * @author ranga
 */
public class MyList  {
    LinkedList<Object> l1,l2;

    MyList() {
        l1 = new LinkedList<Object>();
        l2 = new LinkedList<Object>();
        l2.add(l1);
        l1.add(l2);
    }

    @Override
    public String toString() {
        return l1.toString();
    }

    public static void main(String ...args) {
        MyList m = new MyList();
        System.out.println(m);
    }
}

possible duplicate of [Most efficient way to prevent an infinite recursion in toString()?](http://stackoverflow.com/questions/11300203/most-efficient-way-to-prevent-an-infinite-recursion-in-tostring) — assylias, Nov 14 '12 at 15:25
Why are you putting a list as element into another, and that crosswise? — Andy, Nov 14 '12 at 15:27

score 2 · Answer 1 · answered Nov 14 '12 at 15:26

2

Don't add a linked list to itself.

answered Nov 14 '12 at 15:26

djechlin

59,258
35
162
290

score 1 · Answer 2 · answered Nov 14 '12 at 16:02

I'm going to assume that you intentionally created a cyclic data structure as an example, and you really do want to be able to generate a String rendering of a cyclic graph.

The answer is not straightforward.

Firstly, you need to perform a traversal of a (potentially) cyclic graph without getting into a loop. The basic algorithm is like this:

public void traverse(List<?> graph) {
    doTraverse(graph, new IdentityHashMap<?, ?>());
}

private void doTraverse(List<?> graph, IdentityHashMap<?, ?> visited) {
    if (visited.get(graph) == null) {
        visited.put(graph, graph);
        for (Object element : graph) {
            if (element instanceof List<?>) {
                doTraverse((List<?>) element, visited);
            }
        }
    }
}

The visited map allows the traversal to not visit nodes that it has already visited.

The second part of the problem is to modify the code to do the rendering. And at this point you have to decide how you want to render the cycles in the graph ... in the context of the output being a sequence of characters.

The obvious way is to label things. For example we could write a rendering of l1 as

1: [2: [1] ]

(Each list is represented as a [ ... ] and n: means that the following thing has a "label" n. When we encounter a "node" we have already seen, we use a the label; e.g. the 2nd 1 in the above refers back to the list we labelled as 1.)

Given a representation like that, we can modify the doTravers method to take an extra StringBuilder argument, and change the IdentityHashMap to hold the label strings as values. The rest is pretty straightforward.

The problem with this approach are:

The rendering is not very readable ... especially for larger and/or more complicated graph structures.
The algorithm needs to know how to do the traversal AND the rendering for the specific types involved. It is difficult to implement this in a generic, data-structure-independent fashion.

score 0 · Answer 3 · answered Nov 14 '12 at 15:31

0

IS it me or that recursivly calling ToString() methhod has always recursivly calls itself and has not a single case when that recursive calll can stop ? If so you need some condition to quit calling itself recursivly.

answered Nov 14 '12 at 15:31

user1633277

510
2
7
14

score 0 · Answer 4 · answered Nov 14 '12 at 15:46

There is nothing wrong with the toString() method. By default, it prints all elements in a collection by iterating over them (look in the implementation of AbstractCollection.toString()). The problem that you are having is that by adding a list as an element to the other (and the other way around). When l1 is printed, it calls the toString() method of l2 (because that it is first element), which in turns prints the element one by one, and since l2's first element is l1 it calls the toString() method of it, and so on...

In short, don't short-circuit lists by adding them as elements to each other.

java infinite loop while using collections

4 Answers4