Implémentation d'algorithmes ArrayList
Introduit| English | Sens |
|---|---|
| shift/ʃɪft/ | décalage |
| delete/dɪˈliːt/ | supprimer |
| insert/ˈɪnsɜːt/ | insérer |
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.
Dans la boucle while vers l'avant montrée ici, avancez i uniquement lorsque vous...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Après remove(i), l'élément suivant passe à i — ne pas le sauter.
La boucle naive vers l'avant sur [0, 0, 5] qui supprime à i=0 puis incrémente i saute le prochain zéro.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Le zéro restant se décale vers l'indice 0, mais le test suivant a lieu à l'indice 1. Une boucle vers l'arrière utilise une règle d'indice correcte différente.
Une alternative à la suppression in-place qui évite le décalage consiste à...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Ajouter les conservateurs à une liste vierge contourne le décalage.
Les algorithmes ArrayList réutilisent les motifs de tableau via...
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Remplacer [] et length de tableau par get(i) et size().
La nature redimensionnable d'un ArrayList permet d'insérer et de supprimer des éléments, contrairement à un tableau fixe.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
add et remove changent la taille de la liste.
Une boucle de suppression vers l'arrière commençant à size()-1 doit rester au même indice après chaque suppression.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Faux : les éléments initiaux non vérifiés conservent leurs indices, donc la boucle arrière décrémente normalement.
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 suppression vers l'avant conserve l'indice après une suppression
Deux zéros adjacents sont vérifiés à l'indice 0 avant que 5 ne soit conservé.
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].
Difficulté 3/5 · 200 pièces + un petit bonus lors de la première réussite aujourd'hui
Each removal rechecks the shifted value; keeping 5 finally advances the index.
Combien d'appels get la méthode forward removeZeros affichée effectue-t-elle sur une liste vide ?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
La condition initiale 0 < 0 est fausse, donc aucun appel get ne se produit.