Mengimplementasikan Algoritma ArrayList
Diperkenalkan
13:31
Koleksi Data
Ambil satu foto di ponsel Anda. Bagi komputer, itu bukanlah gambar sama sekali — itu adalah grid angka, satu untuk setiap piksel, sekitar dua belas juta darinya. Sekarang cobalah…
Narasi bahasa Inggris · takarir bahasa Inggris dan 中文 yang dapat dipilih
In this lesson
| English | Makna |
|---|---|
| shift/ʃɪft/ | pergeseran |
| delete/dɪˈliːt/ | hapus |
| insert/ˈɪnsɜːt/ | masukkan |
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.
Dalam while-loop maju yang ditampilkan di sini, majukan i hanya ketika Anda...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Setelah remove(i), elemen berikutnya bergeser masuk ke i — jangan lewati.
Loop maju naif pada [0, 0, 5] yang menghapus pada i=0 dan kemudian mengincrement i melewatkan nol berikutnya.
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Nol yang tersisa bergeser ke indeks 0, tetapi uji berikutnya dilakukan pada indeks 1. Loop mundur menggunakan aturan indeks yang benar berbeda.
Alternatif untuk penghapusan in-place yang menghindari pergeseran adalah...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Menambahkan elemen yang disimpan ke list segar menghindari pergeseran.
Algoritma ArrayList memanfaatkan pola array melalui...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Ganti array [] dan length dengan get(i) dan size().
Sifat dapat diubah ukurannya dari ArrayList memungkinkan Anda menyisipkan dan menghapus elemen, berbeda dengan array tetap.
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
add dan remove mengubah ukuran list.
Loop penghapusan mundur yang dimulai dari size()-1 harus tetap pada indeks yang sama setelah setiap penghapusan.
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Salah: elemen yang belum diperiksa sebelumnya mempertahankan indeksnya, sehingga loop mundur decrement secara normal.
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.
Penghapusan maju mempertahankan indeks setelah penghapusan.
Dua nol bersebelahan diperiksa pada indeks 0 sebelum 5 dijaga.
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].
Kesulitan 3/5 · 200 koin + bonus kecil pada penyelesaian pertama hari ini
Each removal rechecks the shifted value; keeping 5 finally advances the index.
Berapa banyak pemanggilan get yang dilakukan metode forward removeZeros yang ditunjukkan pada daftar kosong?
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
Kondisi awal 0 < 0 adalah salah, sehingga tidak ada pemanggilan get yang terjadi.