Algoritmos de ArrayList: filtro e o bug de remove
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.
Contando com uma regra
- Percorra a lista, teste cada item e adicione
1a um contador quando o teste for verdadeiro. n % 2 == 0é verdadeiro quandoné par.n % 2 != 0é verdadeiro quandoné í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
}
}
Filtrando em uma nova lista
- Filtrar mantém apenas os itens que passam no teste.
- Padrão seguro: crie uma nova lista vazia, depois
addcada 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]
}
}
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 adiciona1aie 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
}
}
Por que ele pula
- Início:
[2, 4, 5],i = 0.2é par, remova-o. A lista fica[4, 5]. - O
4deslizou para o índice0. Mas o loop agora definei = 1. - Em
i = 1olhamos para5, não para4. O4foi nunca verificado. Ele permanece.
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ósise 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
}
}
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 loop for melhorado geralmente gera uma
ConcurrentModificationException, e quando não ocorre, itens são silenciosamente pulados. Use um loop com índice em vez disso. - Para remover, use sempre o loop de índice reverso acima.
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.
Agora você tenta
- Cada tarefa pré-preenche a estrutura da classe — escreva seu código dentro do main, ou complete o método mostrado.
- Use Check answer para compilar seu código com os testes fornecidos e visualizar os resultados. Mantenha as interfaces da classe e do método mostradas no modelo.
- Seu código compila e roda no servidor, então até a primeira execução é rápida.
Filtrando uma lista
Remover enquanto itera desloca índices — passe passo a passo para ver o porquê.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
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.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
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.
Clique em Executar para ver a saída aqui.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
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).
Clique em Executar para ver a saída aqui.