ArrayList algorithms: filter and the remove bug · ⁨Algoritmos de ArrayList: filtro e o bug de remove⁩

English

Doing work on a whole list

Now you can store data in an ArrayList. Next we process it.
Common jobs: count items that match a rule, filter them into a new list, and remove some of them.
All of these use a loop over the list.

Português

Trabalhando com toda a lista

Agora você pode armazenar dados em um ArrayList. Na próxima, vamos processá-los.
Tarefas comuns: contar itens que atendem a uma regra, filtrá-los em uma nova lista e remover alguns deles.
Todas essas usam um loop sobre a lista.

English

Counting with a rule

Walk the list, test each item, and add 1 to a counter when the test is true.
n % 2 == 0 is true when n is even. n % 2 != 0 is true when n is odd.
This only reads the list, so an enhanced for-loop is fine.

Português

Contando com uma regra

Percorra a lista, teste cada item e adicione 1 a um contador quando o teste for verdadeiro.
n % 2 == 0 é verdadeiro quando n é par. n % 2 != 0 é verdadeiro quando n é ímpar.
Como isso apenas lê a lista, um for-each loop é suficiente.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(4);
        nums.add(7);
        nums.add(10);
        nums.add(3);

        int evens = 0;
        for (int x : nums) {
            if (x % 2 == 0) {
                evens = evens + 1;
            }
        }
        System.out.println(evens);   // 2
    }
}

English

Filtering into a new list

Filtering keeps only the items that pass a test.
A safe pattern: make an empty new list, then add each item that passes.
The old list is not changed. This avoids the bug we see next.

Português

Filtrando em uma nova lista

Filtrar mantém apenas os itens que passam no teste.
Padrão seguro: crie uma nova lista vazia, depois add cada item que passar.
A lista antiga não é alterada. Isso evita o bug que veremos a seguir.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(4);
        nums.add(7);
        nums.add(10);
        nums.add(3);

        ArrayList<Integer> bigOnes = new ArrayList<Integer>();
        for (int x : nums) {
            if (x >= 5) {
                bigOnes.add(x);
            }
        }
        System.out.println(bigOnes);   // [7, 10]
    }
}

English

The remove-while-iterating bug

It looks easy: loop forward and remove(i) the items you do not want.
But remove(i) shifts every later item one place left. The loop then adds 1 to i and skips the item that moved into the old spot.
The example below tries to remove all evens but misses one.

Português

O bug de remover enquanto itera

Parece fácil: faça um loop para frente e remove(i) os itens que você não quer.
Mas remove(i) desloca todos os itens subsequentes uma posição para a esquerda. O loop então adiciona 1 a i e pula o item que ocupou o lugar antigo.
O exemplo abaixo tenta remover todos os pares mas perde um.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(2);
        nums.add(4);   // this one gets skipped!
        nums.add(5);

        // BUGGY: forward loop while removing
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i) % 2 == 0) {
                nums.remove(i);
            }
        }
        System.out.println(nums);   // [4, 5]  -- wrong, 4 was missed
    }
}

English

Why it skips

Start: [2, 4, 5], i = 0. 2 is even, remove it. List becomes [4, 5].
The 4 slid down into index 0. But the loop now sets i = 1.
At i = 1 we look at 5, not 4. The 4 was never checked. It stays in.

Português

Por que ele pula

Início: [2, 4, 5], i = 0. 2 é par, remova-o. A lista fica [4, 5].
O 4 deslizou para o índice 0. Mas o loop agora define i = 1.
Em i = 1 olhamos para 5, não para 4. O 4 foi nunca verificado. Ele permanece.

English

The fix: loop backwards

Walk from the last index down to 0.
When you remove index i, only items after i shift — and you have already passed those.
The indexes you still need to visit are smaller than i, so nothing moves out from under you.

Português

A correção: faça o loop de trás para frente

Percorra do último índice até 0.
Quando você remove o índice i, apenas os itens após i se deslocam — e você já passou por eles.
Os índices que ainda precisa visitar são menores que i, então nada se move sob seus pés.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(2);
        nums.add(4);
        nums.add(5);

        // SAFE: backward loop while removing
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (nums.get(i) % 2 == 0) {
                nums.remove(i);
            }
        }
        System.out.println(nums);   // [5]  -- correct
    }
}

English

A note on the enhanced for-loop

You may be tempted to remove inside for (int x : nums).
Do not. Changing the list size during an enhanced for-loop throws a ConcurrentModificationException and stops the program.
For removing, always use the backward index loop above.

Português

Uma nota sobre o for-each loop

Você pode sentir tentação de remover dentro de for (int x : nums).
Não faça. Alterar o tamanho da lista durante um for-each loop gera um ConcurrentModificationException e interrompe o programa.
Para remover, use sempre o loop de índice reverso acima.

English

Common mistakes

Removing while looping forward by index skips the next item (the remove bug).
Loop backwards, or use an iterator, when removing.

Português

Erros comuns

Remover enquanto faz loop para frente por índice salta o próximo item (o bug de remover).
Faça o loop de trás para frente, ou use um iterador, ao remover.

English

Now you try

Each task pre-fills the class skeleton — write your code inside main, or complete the method shown.
Press Run to compile and run, then Check answer.
Your code compiles and runs on the server, so even the first run is fast.

Português

Agora você tenta

Cada tarefa pré-preenche a estrutura da classe — escreva seu código dentro do main, ou complete o método mostrado.
Pressione Run para compilar e executar, depois Check answer.
Seu código compila e roda no servidor, então até a primeira execução é rápida.

Explore · ⁨Explorar⁩

Filtering a list · ⁨Filtrando uma lista⁩

Removing while looping shifts indices — step through to see why. · ⁨Remover enquanto itera desloca índices — passe passo a passo para ver o porquê.⁩

Complete countOdds(ArrayList<Integer> a) so it returns how many numbers in the list are odd. A number is odd when x % 2 != 0. · ⁨Complete countOdds(ArrayList<Integer> a) para que ele retorne quantos números na lista são ímpares. Um número é ímpar quando x % 2 != 0.⁩

import java.util.ArrayList;

public class ListUtil {
    // Return how many numbers in a are odd.
    public static int countOdds(ArrayList<Integer> a) {
        return 0;   // change this
    }
}

Click Run to see the output here. · ⁨Clique em Executar para ver a saída aqui.⁩

Complete keepPositives(ArrayList<Integer> a). Build and return a new ArrayList<Integer> that holds only the numbers greater than 0, in their original order. Do not · ⁨não⁩ change · ⁨ mudança ⁩a. · ⁨Complete keepPositives(ArrayList<Integer> a). Construa e retorne uma nova ArrayList<Integer> que contenha apenas os números maiores que 0, em sua ordem original. Não altere a.⁩

import java.util.ArrayList;

public class ListUtil {
    // Return a new list with only the numbers > 0.
    public static ArrayList<Integer> keepPositives(ArrayList<Integer> a) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        // add the positives here
        return result;
    }
}

Click Run to see the output here. · ⁨Clique em Executar para ver a saída aqui.⁩

Complete removeEvens(ArrayList<Integer> a) so it removes every even number from a itself. Loop backwards by index so you do not skip items. Return nothing (void). · ⁨Complete removeEvens(ArrayList<Integer> a) para remover todos os números pares de a em si. Itere para trás pelo índice para não pular itens. Não retorne nada (void).⁩

import java.util.ArrayList;

public class ListUtil {
    // Remove every even number from a. Loop backwards!
    public static void removeEvens(ArrayList<Integer> a) {
        // your code here
    }
}

Click Run to see the output here. · ⁨Clique em Executar para ver a saída aqui.⁩

ArrayList algorithms: filter and the remove bug · ⁨Algoritmos de ArrayList: filtro e o bug de remove⁩

Doing work on a whole list

Trabalhando com toda a lista

Counting with a rule

Contando com uma regra

Filtering into a new list

Filtrando em uma nova lista

The remove-while-iterating bug

O bug de remover enquanto itera

Why it skips

Por que ele pula

The fix: loop backwards

A correção: faça o loop de trás para frente

A note on the enhanced for-loop

Uma nota sobre o for-each loop

Common mistakes

Erros comuns

Now you try

Agora você tenta

Filtering a list · ⁨Filtrando uma lista⁩

Handout · ⁨Material de apoio⁩

Log in or create account · ⁨Entrar ou criar conta⁩

Your subject · ⁨Sua matéria⁩

All sections · ⁨Todas as seções⁩

Feedback & help · ⁨Feedback & ajuda⁩