ArrayList algorithms: filter and the remove bug · ⁨Algoritma ArrayList: filter dan bug penghapusan⁩

English

Doing work on a whole list

Now you can store data in an ArrayList. Next we process it.
Common jobs: count items that match a rule, filter them into a new list, and remove some of them.
All of these use a loop over the list.

Bahasa Indonesia

Melakukan pekerjaan pada seluruh daftar

Sekarang Anda dapat menyimpan data dalam an ArrayList. Selanjutnya kita proses data tersebut.
Pekerjaan umum: hitung item yang sesuai aturan, filter mereka ke dalam daftar baru, dan hapus sebagian darinya.
Semua ini menggunakan loop atas daftar.

English

Counting with a rule

Walk the list, test each item, and add 1 to a counter when the test is true.
n % 2 == 0 is true when n is even. n % 2 != 0 is true when n is odd.
This only reads the list, so an enhanced for-loop is fine.

Bahasa Indonesia

Menghitung dengan aturan

Lintasi daftar, uji setiap item, dan tambahkan 1 ke penghitung ketika uji berhasil.
n % 2 == 0 bernilai benar jika n genap. n % 2 != 0 bernilai benar jika n ganjil.
Ini hanya membaca daftar, jadi enhanced for-loop sudah cukup.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(4);
        nums.add(7);
        nums.add(10);
        nums.add(3);

        int evens = 0;
        for (int x : nums) {
            if (x % 2 == 0) {
                evens = evens + 1;
            }
        }
        System.out.println(evens);   // 2
    }
}

English

Filtering into a new list

Filtering keeps only the items that pass a test.
A safe pattern: make an empty new list, then add each item that passes.
The old list is not changed. This avoids the bug we see next.

Bahasa Indonesia

Memfilter ke daftar baru

Filtering hanya menyimpan item yang lolos uji.
Pola yang aman: buat daftar baru kosong, lalu add setiap item yang lolos.
Daftar lama tidak berubah. Ini menghindari bug yang akan kita lihat selanjutnya.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(4);
        nums.add(7);
        nums.add(10);
        nums.add(3);

        ArrayList<Integer> bigOnes = new ArrayList<Integer>();
        for (int x : nums) {
            if (x >= 5) {
                bigOnes.add(x);
            }
        }
        System.out.println(bigOnes);   // [7, 10]
    }
}

English

The remove-while-iterating bug

It looks easy: loop forward and remove(i) the items you do not want.
But remove(i) shifts every later item one place left. The loop then adds 1 to i and skips the item that moved into the old spot.
The example below tries to remove all evens but misses one.

Bahasa Indonesia

Bug remove-while-iterating

Tampaknya mudah: loop maju dan remove(i) item-item yang tidak diinginkan.
Namun, remove(i) menggeser setiap item berikutnya satu posisi ke kiri. Loop kemudian menambahkan 1 ke i dan melewati item yang berpindah ke posisi lama.
Contoh di bawah mencoba menghapus semua genap tetapi melewatkan satu.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(2);
        nums.add(4);   // this one gets skipped!
        nums.add(5);

        // BUGGY: forward loop while removing
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i) % 2 == 0) {
                nums.remove(i);
            }
        }
        System.out.println(nums);   // [4, 5]  -- wrong, 4 was missed
    }
}

English

Why it skips

Start: [2, 4, 5], i = 0. 2 is even, remove it. List becomes [4, 5].
The 4 slid down into index 0. But the loop now sets i = 1.
At i = 1 we look at 5, not 4. The 4 was never checked. It stays in.

Bahasa Indonesia

Mengapa melewatkan

Mulai: [2, 4, 5], i = 0. 2 genap, hapus. Daftar menjadi [4, 5].
The 4 turun ke index 0. Tapi loop sekarang mengatur i = 1.
Di i = 1 kita melihat 5, bukan 4. The 4 tidak pernah diperiksa. Ia tetap ada.

English

The fix: loop backwards

Walk from the last index down to 0.
When you remove index i, only items after i shift — and you have already passed those.
The indexes you still need to visit are smaller than i, so nothing moves out from under you.

Bahasa Indonesia

Perbaikan: loop mundur

Lintasi dari index terakhir turun ke 0.
Ketika Anda menghapus index i, hanya item-item setelah i yang bergeser — dan Anda telah melewati item-item tersebut.
Indeks yang masih perlu dikunjungi adalah lebih kecil dari i, jadi tidak ada yang bergerak menjauh dari Anda.

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(2);
        nums.add(4);
        nums.add(5);

        // SAFE: backward loop while removing
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (nums.get(i) % 2 == 0) {
                nums.remove(i);
            }
        }
        System.out.println(nums);   // [5]  -- correct
    }
}

English

A note on the enhanced for-loop

You may be tempted to remove inside for (int x : nums).
Do not. Changing the list size during an enhanced for-loop throws a ConcurrentModificationException and stops the program.
For removing, always use the backward index loop above.

Bahasa Indonesia

Catatan tentang enhanced for-loop

Anda mungkin tergoda untuk menghapus di dalam for (int x : nums).
Jangan lakukan. Mengubah ukuran daftar selama enhanced for-loop menyebabkan ConcurrentModificationException dan menghentikan program.
Untuk menghapus, selalu gunakan loop indeks mundur di atas.

English

Common mistakes

Removing while looping forward by index skips the next item (the remove bug).
Loop backwards, or use an iterator, when removing.

Bahasa Indonesia

Kesalahan umum

Menghapus saat looping maju berdasarkan indeks melewatkan item berikutnya (bug remove).
Loop mundur, atau gunakan iterator, saat menghapus.

English

Now you try

Each task pre-fills the class skeleton — write your code inside main, or complete the method shown.
Press Run to compile and run, then Check answer.
Your code compiles and runs on the server, so even the first run is fast.

Bahasa Indonesia

Sekarang Anda coba

Setiap tugas telah mengisi kerangka class — tulis kode Anda di dalam main, atau lengkapi method yang ditampilkan.
Tekan Jalankan untuk mengompilasi dan menjalankan, lalu Periksa jawaban.
Kode Anda dikompilasi dan dijalankan di server, sehingga bahkan jalankan pertama kali pun cepat.

Explore · ⁨Jelajahi⁩

Filtering a list · ⁨Memfilter daftar⁩

Removing while looping shifts indices — step through to see why. · ⁨Menghapus saat perulangan menggeser indeks — telusuri untuk melihat alasannya.⁩

Complete countOdds(ArrayList<Integer> a) so it returns how many numbers in the list are odd. A number is odd when x % 2 != 0. · ⁨Lengkapi countOdds(ArrayList<Integer> a) agar mengembalikan berapa banyak angka dalam daftar yang ganjil. Suatu angka adalah ganjil ketika x % 2 != 0.⁩

import java.util.ArrayList;

public class ListUtil {
    // Return how many numbers in a are odd.
    public static int countOdds(ArrayList<Integer> a) {
        return 0;   // change this
    }
}

Click Run to see the output here. · ⁨Klik Jalankan untuk melihat output di sini.⁩

Complete keepPositives(ArrayList<Integer> a). Build and return a new ArrayList<Integer> that holds only the numbers greater than 0, in their original order. Do not change a. · ⁨Lengkapi keepPositives(ArrayList<Integer> a). Bangun dan kembalikan ArrayList<Integer> baru yang hanya berisi angka-angka yang lebih besar dari 0, dalam urutan aslinya. Jangan ubah a.⁩

import java.util.ArrayList;

public class ListUtil {
    // Return a new list with only the numbers > 0.
    public static ArrayList<Integer> keepPositives(ArrayList<Integer> a) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        // add the positives here
        return result;
    }
}

Click Run to see the output here. · ⁨Klik Jalankan untuk melihat output di sini.⁩

Complete removeEvens(ArrayList<Integer> a) so it removes every even number from a itself. Loop backwards by index so you do not skip items. Return nothing (void). · ⁨Lengkapi removeEvens(ArrayList<Integer> a) agar menghapus setiap angka genap dari a itu sendiri. Loop mundur berdasarkan indeks agar Anda tidak melewatkan item. Kembalikan sesuatu (void).⁩

import java.util.ArrayList;

public class ListUtil {
    // Remove every even number from a. Loop backwards!
    public static void removeEvens(ArrayList<Integer> a) {
        // your code here
    }
}

Click Run to see the output here. · ⁨Klik Jalankan untuk melihat output di sini.⁩

ArrayList algorithms: filter and the remove bug · ⁨Algoritma ArrayList: filter dan bug penghapusan⁩

Doing work on a whole list

Melakukan pekerjaan pada seluruh daftar

Counting with a rule

Menghitung dengan aturan

Filtering into a new list

Memfilter ke daftar baru

The remove-while-iterating bug

Bug remove-while-iterating

Why it skips

Mengapa melewatkan

The fix: loop backwards

Perbaikan: loop mundur

A note on the enhanced for-loop

Catatan tentang enhanced for-loop

Common mistakes

Kesalahan umum

Now you try

Sekarang Anda coba

Filtering a list · ⁨Memfilter daftar⁩

Handout · ⁨Lembar Kerja⁩

Log in or create account · ⁨Masuk atau buat akun⁩

Your subject · ⁨Mata Pelajaran Anda⁩

All sections · ⁨Semua bagian⁩

Feedback & help · ⁨Umpan balik & bantuan⁩