Реализация алгоритмов для ArrayList
| English | Русский |
|---|---|
| shift/ʃɪft/ | сдвиг |
| delete/dɪˈliːt/ | удалить |
| insert/ˈɪnsɜːt/ | insert |
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].
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.
В показанном здесь прямом цикле while увеличивайте i только тогда, когда...
После вызова remove(i) следующий элемент смещается на позицию i — не пропустите его.
Наивный прямой цикл на [0, 0, 5], который удаляет элемент при i=0, а затем увеличивает i, пропускает следующий ноль.
Оставшийся ноль смещается в индекс 0, но следующая проверка выполняется по индексу 1. Цикл с обратным направлением использует иное корректное правило для индекса.
Альтернатива удалению на месте, избегающая смещения, заключается в том, чтобы...
Добавление сохраняемых элементов в новый список обходит проблему смещения.
Алгоритмы для ArrayList повторяют шаблоны работы с массивами благодаря...
Замените массив [] и length на get(i) и size().
Изменяемая длина ArrayList позволяет вставлять и удалять элементы, в отличие от фиксированного массива.
add и remove изменяют размер списка.
Цикл удаления в обратном направлении, начинающийся с size()-1, должен оставаться на том же индексе после каждого удаления.
Неверно: ранее не проверенные элементы сохраняют свои индексы, поэтому обратный цикл уменьшается стандартным образом.
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.
При удалении в прямом порядке индекс после удаления сохраняется.
Два соседних нуля проверяются по индексу 0 перед тем, как ⟨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].
Each removal rechecks the shifted value; keeping 5 finally advances the index.
Сколько вызовов get выполняет показанный метод removeZeros прямого порядка на пустом списке?
Начальное условие 0 < 0 ложно, поэтому вызов get не происходит.