Geek Answers Handbook

LinkedLists: an infinite loop

Why does the following java code lead to 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()); } } }
+4
source share
5 answers

As you use remove , you remove objects by value , not by position.

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

To remove by position, not value, say fields.remove(f) . (Note that f is an integer, and (Integer)f is an object of the type contained in the list container.)

(As an alternative to other behavior, you can continue deleting by value, but now you need to draw a random number from the [min, max] range where you need to determine the extreme values ​​of the list items separately. Of course, a lot, because you will have a lot " misses "where you don't delete anything.)

+11
source

Because of this line:

 fields.remove((Integer) f);

Remove the cast (Integer) and it should work.

There are two removal options in the list:

  • remove by position: remove(int) and
  • remove by content: remove(E) (actually it is remove(Object) for compatibility reasons)

In your case, E is Integer, and due to autoboxing, you can apply int to Integer. And so you choose the second type, while you need the first type.

+5
source

The problem arises because you are actually calling the remove (Object o) instead of the delete (int index) method!

When you call fields.remove((Integer) f); , you are not deleting the object at index f , but you are deleting an integer equal to f since your List contains Integer s

So don't throw f into Integer and everything should be fine.

In addition, to get Integer from int , use the static Integer valueOf (int i) method.

+2
source 
 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()); } } }
+1
source

Going through the debugger, I see that the problem is that you are deleting numbers that are smaller than the size. However, to start with this number, you will not delete the largest number the first time it is never deleted.

What you are trying to do is select numbers at random. The easiest 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]
0
source

More articles:


All Articles