Mengimplementasikan Algoritma ArrayList
| English | Bahasa Indonesia |
|---|---|
| shift/ʃɪft/ | pergeseran |
| delete/dɪˈliːt/ | hapus |
| insert/ˈɪnsɜːt/ | insert |
Penghapusan bersebelahan mengungkap elemen yang terlewat
- Dimulai dengan
[0, 0, 5], hapus index 0 lalu tingkatkan i. Nol kedua telah bergeser ke index 0, sehingga loop maju itu melewatkannya dan meninggalkan[0, 5]. - Untuk while-loop maju yang diajarkan di sini, tetap di index yang sama setelah penghapusan dan majukan hanya ketika menyimpan elemen. Hal itu kemudian menghapus kedua nol dan selesai dengan
[5].
Jaga index maju saat ini setelah penghapusan
- Setelah
remove(i), setiap elemen selanjutnya bergeser satu tempat ke kiri. Jika elemen sekarang menempati i, elemen tersebut belum diperiksa; periksa pada iterasi berikutnya. - Loop di bawah ini menerima daftar Integer non-null non-null dan menghapus setiap nol secara in-place. Ia menggunakan ukuran saat ini setiap iterasi dan tidak melakukan panggilan get pada list kosong.
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++;
}
}
}
}
Jelaskan mengapa loop ini berakhir
- Setiap iterasi baik menghapus satu elemen dan mengurangi ukuran, atau menyimpan satu dan meningkatkan i. Dengan demikian
size() - i, jumlah posisi yang masih harus dicek, berkurang satu setiap iterasi. - Dimulai dengan
[0, 0, 5], state-nya adalah[0, 5]pada i=0,[5]pada i=0, lalu[5]pada i=1. Kondisi akhir adalah false, sehingga tidak terjadi akses di luar batas.
Perulangan mundur mengikuti aturan yang berbeda
- Perulangan mundur dimulai dari indeks terakhir yang ada:
for (int i = list.size() - 1; i >= 0; i--). Hapus elemen yang cocok denganremove(i); nilai i berikutnya selalu lebih rendah satu. - Menghapus pada posisi i hanya menggeser indeks-indeks yang berada setelahnya, yang sudah pernah diperiksa. Elemen-elemen sebelumnya yang belum diperiksa tetap mempertahankan indeksnya, sehingga pengurangan (decrement) setelah penghapusan adalah benar di sini; aturan "jangan pernah majukan setelah penghapusan" bukanlah aturan universal.
Pilih pembaruan indeks yang sesuai dengan arah traversal. Pada perulangan while maju, tetaplah di tempat setelah penghapusan; pada perulangan for mundur, terus melakukan pengurangan. Perubahan struktur langsung selama perulangan ditingkatkan (enhanced loop) merupakan pola tidak aman yang terpisah, bahkan ketika tidak muncul pengecualian fail-fast.
Dalam while-loop maju yang ditampilkan di sini, majukan i hanya ketika Anda...
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.
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...
Menambahkan elemen yang disimpan ke list segar menghindari pergeseran.
Algoritma ArrayList memanfaatkan pola array melalui...
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.
add dan remove mengubah ukuran list.
Loop penghapusan mundur yang dimulai dari size()-1 harus tetap pada indeks yang sama setelah setiap penghapusan.
Salah: elemen yang belum diperiksa sebelumnya mempertahankan indeksnya, sehingga loop mundur decrement secara normal.
Buat daftar baru jika daftar asli harus tetap utuh
- Untuk mempertahankan daftar asli, buat hasil yang baru dan lampirkan setiap elemen nonzero saat membaca daftar asli. Ini menjaga urutan asli dan ukurannya tetap tidak berubah; namun hal ini memerlukan penyimpanan tambahan untuk daftar.
- Untuk daftar objek yang dapat diubah (mutable), menyalin referensi yang ditahan tidak akan mengklon objek-objek tersebut. Struktur daftar baru mungkin masih berbagi objek elemennya dengan daftar asli; bedakan identitas daftar dengan identitas elemen.
Penghapusan maju mempertahankan indeks setelah penghapusan.
Dua nol bersebelahan diperiksa pada indeks 0 sebelum 5 dijaga.
Periksa kasus-kasus yang memaparkan algoritma
- Uji daftar kosong, semua nol, tanpa nol, nol yang berdekatan, dan nol pada indeks terakhir. Untuk penghapusan in-place, referensi lain ke daftar yang sama akan mengamati perubahannya; hasil yang baru meninggalkan struktur asli tetap utuh.
- ArrayList dapat memasukkan atau menghapus elemen; operasi-operasi tersebut dapat menggeser indeks-indeks yang berada setelahnya. Pencarian dapat mengembalikan indeks yang ditemukan atau -1 jika tidak ditemukan; pencarian maksimum memerlukan kebijakan khusus untuk daftar kosong. Penggunaan kembali pola array melalui get/size membantu, tetapi setiap algoritma tetap memerlukan batas dan kontrak masing-masing.
Penghapusan menggeser indeks. Jelaskan elemen mana yang tersisa belum diperiksa dan pilih indeks berikutnya sesuai. Pola tetap/maju atau decrement mundur keduanya valid; daftar baru berisi elemen yang ditahan akan mempertahankan struktur asli tetapi mungkin berbagi objek.
Order the states for the corrected removal loop on [0, 0, 5].
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?
Kondisi awal 0 < 0 adalah salah, sehingga tidak ada pemanggilan get yang terjadi.