CODEWITHSUNDEEP
javalist
user2442121
user2442121

Reputation:

LinkedLists: infinite loop

Why does the following java code result in an infinite loop?

import java.util.LinkedList;
import java.util.Random;

public class Main {

public static void main(String[] args) {
    int n = 3;

    Random rand = new Random();

    LinkedList<Integer> fields = new LinkedList<Integer>();

    for (int i = 0; i < n*n; i++) {
        fields.add(i);
    }

    while (fields.size() > 0) {

        // Choose Field
        int f = rand.nextInt(fields.size());

        fields.remove((Integer) f);
        System.out.println(fields.size());
    }
}
   }

Upvotes: 4

Views: 174

Answers (5)

Kerrek SB
Kerrek SB

Reputation: 477040

The way you use remove, you remove objects by value, not by position.

Say your list consists of values [0, 1, 2, 3], and you remove 0 and 1 the first two times. Now you have [2, 3], whose size is 2, so you will never remove 3 now!

To remove by position rather than value, say fields.remove(f). (Notice that f is an integer, while (Integer)f is an object of the type contained in the list container.)

(Alternatively, for different behaviour, you could continue removing by value, but you should now draw the random number from the range [min, max], where you have to determine the extremal values of the list elements separately. This may take a lot longer, of course, since you will have a lot of "misses" where you don't remove anything.)

Upvotes: 11

Sean Patrick Floyd
Sean Patrick Floyd

Reputation: 298898

Because of this line:

fields.remove((Integer) f);

Remove the (Integer) cast and it should work.

There are two flavors of remove in List:

  • remove by position: remove(int) and
  • remove by contents: remove(E) (actually it's remove(Object) for compatibility reasons)

In your case, E is Integer, and because of autoboxing you are able to cast an int to an Integer. And by doing that, you are choosing the second type, whereas you want the first type.

Upvotes: 5

Jean Logeart
Jean Logeart

Reputation: 53829

You problem comes from the fact that you are actually calling the remove(Object o) method instead of the remove(int index) method!

When you call fields.remove((Integer) f); you do not remove the object at the index f but you remove the Integer that is equal to f since your List contains Integers

Therefore do not cast f into Integer and you should be fine.

Also, to get an Integer from an int, use the static Integer valueOf(int i) method.

Upvotes: 2

Peter Lawrey
Peter Lawrey

Reputation: 533520

Stepping through the debugger I can see the problem you have is that you are removing numbers which less than the size. To start with that number will be there however, unless you remove the largest number the first time it will never be removed.

What you are trying to do is to select numbers in a random order. The simplest way to do this is to use Collections.shuffle()

int n = 3;
List<Integer> list = new LinkedList<Integer>();
for (int i = 0; i < n * n; i++)
  list.add(i);
Collections.shuffle(list);
System.out.println(list);

prints

[7, 4, 0, 8, 5, 1, 3, 6, 2]

Upvotes: 0

Saurabh Gokhale
Saurabh Gokhale

Reputation: 46395

import java.util.LinkedList;
import java.util.Random;

public class Main {

public static void main(String[] args) {
    int n = 3;

    Random rand = new Random();

    LinkedList<Integer> fields = new LinkedList<Integer>();

    for (int i = 0; i < n*n; i++) {
        fields.add(i);
    }

    while (fields.size() > 0) {

        // Choose Field
        int f = rand.nextInt(fields.size());

        fields.remove(f);
        System.out.println(fields.size());
    }
  }
 }

Upvotes: 1

Related Questions