Implementando Algoritmos de ArrayList
Introduzido| English | Significado |
|---|---|
| shift/ʃɪft/ | shift: deslocamento |
| delete/dɪˈliːt/ | delete: excluir |
| insert/ˈɪnsɜːt/ | insert: inserir |
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.
No while-loop para frente mostrado aqui, avance i apenas quando você...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Após remove(i), o próximo elemento desloca-se para i — não o pule.
O loop simples de frente em [0, 0, 5] que remove em i=0 e depois incrementa i pula o próximo zero.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
O zero restante desloca-se para o índice 0, mas o próximo teste ocorre no índice 1. Um loop para trás usa uma regra de índice correta diferente.
Uma alternativa à remoção in-place que evita o deslocamento é...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Adicionar keepers a uma lista nova contorna o deslocamento.
Algoritmos de ArrayList reutilizam padrões de array via...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Troque array [] e length por get(i) e size().
A natureza redimensionável de um ArrayList permite inserir e excluir elementos, diferentemente de um array fixo.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
add e remove alteram o tamanho da lista.
Um loop de remoção para trás começando em size()-1 deve permanecer no mesmo índice após cada exclusão.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Falso: elementos anteriores não verificados retêm seus índices, então o loop para trás 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.
A remoção para frente mantém o índice após uma exclusão
Dois zeros adjacentes são verificados no índice 0 antes que 5 seja mantido.
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].
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Each removal rechecks the shifted value; keeping 5 finally advances the index.
Quantas chamadas get o método removeZeros para frente mostrado faz em uma lista vazia?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
A condição inicial 0 < 0 é falsa, portanto nenhuma chamada get ocorre.