Remove even numbers from an ArrayList

Question

I have to create a method which has an ArrayList; I need to remove even numbers from this ArrayList. I have written code for that but there is a logical error which I couldn't identify.

Here is my code:

static void sortList(){

   List <Integer> number=new ArrayList <Integer>();

   number.add(11);
   number.add(45);
   number.add(12);
   number.add(32);
   number.add(36);

   System.out.println("Unsorted List: "+number);

   for (int i=0;i<number.size();i++){      
       int even=number.get(i)%2;       
        if (even==0){
            System.out.println("This is Even Number:"+ number.get(i));
            number.remove(i);
        }    
    }

    Collections.sort(number);
    System.out.println("Sorted List: "+number);

 }

The output of the code is:

Unsorted List: [11, 45, 12, 32, 36]
This is Even Number:12
This is Even Number:36
Sorted List: [11, 32, 45]

I am wondering that why 32 is not caught as an Even number as it is an even number, I tested then by using different even numbers at same position but the result is same. Why at index(3) its happening that any even number couldnt be catch. I am really wondering why. So please any one can help me out for this and is there any other better way to implement this solution.

Thanks

Solution 1

Use an Iterator. It has an remove() method which you need.

List<Integer> numbers = new ArrayList<Integer>();

numbers.add(11);
numbers.add(45);
numbers.add(12);
numbers.add(32);
numbers.add(36);

System.out.println("Unsorted List: " + numbers);

for (Iterator<Integer> iterator = numbers.iterator(); iterator.hasNext();) {
    Integer number = iterator.next();
    if (number % 2 == 0) {
        System.out.println("This is Even Number: " + number);
        iterator.remove();
    }

}

Collections.sort(numbers);
System.out.println("Sorted List: " + numbers);

Solution 2

When you remove something from the list, the indexes of everything after that changes!

Specifically, in your implementation 32 is not removed as it comes directly after another even number.

I would use an Iterator to walk over the list, and the remove operation on that iterator instead, something like this:

for(Iterator i = number.iterator(); i.hasNext(); ) {
    if (isEven(i.next()) {
        i.remove();
    }
}

Solution 3

Both answers about list indices changing are correct. However, also be aware that removing an item from an ArrayList is slow because it has to actually shuffle all of the following entries down. Instead, I recommend creating a new list containing only the even numbers, and then just throwing away the old list. If you want to use the Iterator-based remove code in the other answer, it will work fine for small results as is, and for larger data sets if you use LinkedList. (I believe that is the name; my Java is admittedly slightly rusty.)

Solution 4

If you remove an entry from the list whilst looping over it, you'll have to adjust your loop index. Don't forget, removing the element reduces the length of the list by one, and effectively "shuffles back" the index of all elements after it.

Solution 5

The problem (as others have mentioned) is that you are modifying the list while you are traversing it. Try adding a "i--;" line inside your "if (even==0)" block. Like this:

for (int i=0;i<number.size();i++){
    int even=number.get(i)%2;

    if (even==0){
        System.out.println("This is Even Number:"+ number.get(i));
        number.remove(i);

        // Add this:
        i--;
    }
}

View more solutions

Comments

[Vishy]

You are altering the list while iterating over it. A simple fix is to iterate backwards over the list.

[Brett]

An iterator will give you O(n^2) performance for an ArrayList. That may or may not be a problem.

[Mikeb]

alternately, walk backwards from the end

[Rasmus Kaj]

It will? Sounds strange ... Anyway, I tend to use List<X> (ignoring if it is really an ArrayList or some other kind of List) and assume iterating will be fast. It should be, and I don't like to spend time on performance optimization unless I have a performance problem ...

[starblue]

The remove will be slow for array lists, but that's not the fault of the iterator.

[hjhill]

@Tom Hawtin: the remove will be O(n^2) for an ArrayList regardless of how you do it. But beginners should learn that using indexes to iterate a LinkedList will give you O(n^2) performance, but using an iterator will always be O(n) - I have seen this done wrong countless times...

[Adam Smith]

@Kevin Bourrillion: You're certainly right. Edited to reflect.

[Rasmus Kaj]

Ah, O(n^2) for the entire operation, not for i.remove(). Yes. But the only way to avoid that with an ArrayList is to walk trough the list once and copy the elements you want to keep to a new list instead of removing elements one by one (or the in-place version of that, using a read-index and a write-index).

[Ralf Stubner]

Welcome to Stack Overflow! While this code may answer the question, it is better to include some comments in your answer. In particular how your answer is different from the existing ones.