Implementación de algoritmos para ArrayList
Introducido| English | Significado |
|---|---|
| shift/ʃɪft/ | desplazamiento |
| delete/dɪˈliːt/ | eliminar |
| insert/ˈɪnsɜːt/ | insertar |
Adjacent removals reveal a skipped element
- Starting with
[0, 0, 5], remove index 0 and then increment i. The second zero has shifted into index 0, so that forward loop skips it and leaves[0, 5]. - For the forward while-loop taught here, stay at the same index after removal and advance only when keeping an element. It then removes both zeros and finishes with
[5].
![Adjacent removals reveal the skipped-element bug: scanning [0, 0, 5] forwards, removing index 0 and then incrementing skips the second zero, which moved to index 0; keep the same index after a removal and increment only when keeping an item, giving [5]](/learn-media/ap_computer_science_a/assets/0410-skip-bug.png?v=1794647927)
Keep the current forward index after removal
- After
remove(i), every later element shifts one place left. If an element now occupies i, it has not yet been checked; inspect it on the next iteration. - The loop below accepts a non-null list of non-null Integers and removes every zero in place. It uses current size each iteration and performs no get call on an empty list.
import java.util.ArrayList;
public class RemoveZeros {
public static void removeZeros(ArrayList<Integer> list) {
int i = 0;
while (i < list.size()) {
if (list.get(i) == 0) {
list.remove(i);
} else {
i++;
}
}
}
}
Explain why this loop terminates
- Each iteration either removes one element and reduces size, or keeps one and increases i. Thus
size() - i, the number of positions still to check, decreases by one each iteration. - Starting with
[0, 0, 5], the states are[0, 5]at i=0,[5]at i=0, then[5]at i=1. The final condition is false, so no out-of-bounds access occurs.
A backward loop follows a different rule
- A reverse loop starts at the final existing index:
for (int i = list.size() - 1; i >= 0; i--). Remove matching elements withremove(i); the next i is always one lower. - Deleting at i shifts only later indices, which have already been checked. Earlier unchecked elements retain their indices, so decrementing after a removal is correct here; “never advance after removal” is not a universal rule.
Choose an index update that matches the direction of traversal. In the forward while-loop, stay after removal; in the backward for-loop, continue decrementing. Direct structural changes during an enhanced loop are a separate unsafe pattern, even when no fail-fast exception appears.
En el bucle while hacia adelante mostrado aquí, avanza i solo cuando tú...
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Después de remove(i), el siguiente elemento se desplaza hacia i — no lo saltes.
El bucle simple hacia adelante en [0, 0, 5] que elimina en i=0 y luego incrementa i salta el siguiente cero.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
El cero restante se desplaza al índice 0, pero la siguiente prueba se realiza en el índice 1. Un bucle hacia atrás utiliza una regla de índice correcta diferente.
Una alternativa a la eliminación in situ que evita los desplazamientos es...
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Añadir los elementos conservados a una lista nueva evita los desplazamientos.
Los algoritmos de ArrayList reutilizan patrones de array mediante...
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Reemplazar el índice [] y length por get(i) y size().
La naturaleza redimensionable de un ArrayList permite insertar y eliminar elementos, a diferencia de un array fijo.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
add y remove modifican el tamaño de la lista.
Un bucle de eliminación hacia atrás que comienza en size()-1 debe permanecer en el mismo índice después de cada eliminación.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Falso: los elementos anteriores sin verificar conservan sus índices, por lo que el bucle hacia atrás se decrementa normalmente.
Build a new list when the original must remain
- To preserve the original list, create a fresh result and append every nonzero element while reading the original. This keeps the original sequence and its size unchanged; it uses additional list storage.
- For lists of mutable objects, copying retained references does not clone those objects. A new list structure may still share its element objects with the original; distinguish list identity from element identity.
La eliminación hacia adelante mantiene el índice después de una eliminación.
Se verifican dos ceros adyacentes en el índice 0 antes de que se conserve 5.
Check the cases that expose the algorithm
- Test an empty list, all zeros, no zeros, adjacent zeros and a zero at the last index. For in-place removal, other references to the same list observe its change; a fresh result leaves that original structure intact.
- An ArrayList can insert 插入 or delete 删除 elements; those operations can shift 移位 later indices. A search may return a found index or -1 when absent; a maximum requires an explicit empty-list policy. Reusing array patterns through get/size helps, but each algorithm still needs its own bounds and contract.
Removing shifts indices. Explain which elements remain unchecked and choose the next index accordingly. Forward stay-or-increment and backward decrement are both valid patterns; a fresh list of keepers preserves the original structure but may share objects.
Order the states for the corrected removal loop on [0, 0, 5].
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Each removal rechecks the shifted value; keeping 5 finally advances the index.
¿Cuántas llamadas get realiza el método forward removeZeros mostrado sobre una lista vacía?
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
La condición inicial 0 < 0 es falsa, por lo que no ocurre ninguna llamada get.