ArrayList algorithms: filter and the remove bug · ⁨Algoritmos de ArrayList: filtrar y el error 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.

Español

Realizar operaciones sobre una lista completa

Ahora puedes almacenar datos en un ArrayList. A continuación, lo procesamos.
Tareas comunes: contar los elementos que cumplen una regla, filtrarlos en una nueva lista y eliminar algunos de ellos.
Todas estas tareas utilizan un bucle sobre la 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.

Español

Contando con una regla

Recorre la lista, verifica cada elemento y suma 1 a un contador cuando la verificación sea verdadera.
n % 2 == 0 es verdadero cuando n es par. n % 2 != 0 es verdadero cuando n es impar.
Esto solo lee la lista, por lo que un bucle for mejorado (enhanced for-loop) es adecuado.

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.

Español

Filtrando en una nueva lista

Filtrar mantiene solo los elementos que pasan una prueba.
Un patrón seguro: crea una nueva lista vacía, luego add (agrega) cada elemento que pase.
La lista original no se modifica. Esto evita el error que veremos a continuación.

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.

Español

El error al eliminar mientras se itera

Parece sencillo: iterar hacia adelante y hacer remove(i) de los elementos que no deseas.
Pero remove(i) desplaza todos los elementos posteriores un lugar a la izquierda. Luego el bucle incrementa 1 en i y salta el elemento que se movió a la posición anterior.
El ejemplo de abajo intenta eliminar todos los pares pero omite uno.

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.

Español

Por qué salta

Inicio: [2, 4, 5], i = 0. El 2 es par, se elimina. La lista se convierte en [4, 5].
El 4 se desplazó al índice 0. Pero el bucle agora establece i = 1.
En i = 1 miramos el 5, no el 4. El 4 nunca fue verificado. Permanece dentro.

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.

Español

La solución: iterar hacia atrás

Recorre desde el último índice hacia abajo hasta el 0.
Cuando eliminas el índice i, solo los elementos después de i se desplazan — y ya has pasado por esos.
Los índices que aún necesitas visitar son menores que i, por lo que nada se mueve bajo tus pies.

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.

Español

Una nota sobre el bucle for mejorado

Puede tentarte eliminar dentro de for (int x : nums).
No lo hagas. Modificar el tamaño de la lista durante un bucle for mejorado lanza una ConcurrentModificationException y detiene el programa.
Para eliminar, utiliza siempre el bucle de índice inverso mostrado arriba.

English

Common mistakes

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

Español

Errores comunes

Eliminar mientras se itera hacia adelante por índice salta el siguiente elemento (el error de eliminación).
Itera hacia atrás, o usa un iterator, al eliminar.

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.

Español

Ahora tú intentas

Cada tarea prellena la estructura de la clase — escribe tu código dentro de main, o completa el método mostrado.
Presiona Run para compilar y ejecutar, luego Check answer.
Tu código se compila y ejecuta en el servidor, así que incluso la primera ejecución es rápida.

Explore · ⁨Explorar⁩

Filtering a list · ⁨Filtrar una lista⁩

Removing while looping shifts indices — step through to see why. · ⁨Eliminar durante un bucle desplaza los índices — pase paso a paso para ver por qué.⁩

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 devuelva cuántos números en la lista son impares. Un número es impar cuando 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. · ⁨Haz clic en Ejecutar para ver la salida aquí.⁩

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 · ⁨no⁩ change · ⁨ cambio ⁩a. · ⁨Complete keepPositives(ArrayList<Integer> a). Construya y devuelva un nuevo ArrayList<Integer> que contenga solo los números mayores que 0, en su orden original. No modifique 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. · ⁨Haz clic en Ejecutar para ver la salida aquí.⁩

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 que elimine todos los números pares de a mismo. Recorra hacia atrás por índice para no omitir elementos. No devuelve 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. · ⁨Haz clic en Ejecutar para ver la salida aquí.⁩

ArrayList algorithms: filter and the remove bug · ⁨Algoritmos de ArrayList: filtrar y el error de remove⁩

Doing work on a whole list

Realizar operaciones sobre una lista completa

Counting with a rule

Contando con una regla

Filtering into a new list

Filtrando en una nueva lista

The remove-while-iterating bug

El error al eliminar mientras se itera

Why it skips

Por qué salta

The fix: loop backwards

La solución: iterar hacia atrás

A note on the enhanced for-loop

Una nota sobre el bucle for mejorado

Common mistakes

Errores comunes

Now you try

Ahora tú intentas

Filtering a list · ⁨Filtrar una lista⁩

Handout · ⁨Material⁩

Log in or create account · ⁨Iniciar sesión o crear cuenta⁩

Your subject · ⁨Tu asignatura⁩

All sections · ⁨Todas las secciones⁩

Feedback & help · ⁨Comentarios y ayuda⁩