ArrayList algorithms: filter and the remove bug · ⁨אלגוריתמים ב-ArrayList: סינון ובעיית ההסרה⁩

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.

עברית

ביצוע פעולות על רשימה שלמה

כעת ניתן לאחסן נתונים ב-ArrayList. בפעם הבאה נעשה עיבוד עליהם.
משימות נפוצות: ספירה של פריטים העונים לתנאי מסוים, סינון שלהם לרשימה חדשה, והסרת חלק מהם.
כולם משתמשים במעגל על הרשימה.

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.

עברית

ספירה עם כלל

הליכה על הרשימה, בדיקת כל פריט, והוספת 1 למניין כאשר הבדיקה מתאמת.
n % 2 == 0 מתאמת כאשר n הוא זוגי. n % 2 != 0 מתאמת כאשר n הוא אי-זוגי.
כאן רק נקראים את הרשימה, ולכן מעגל for משופר מתאים.

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.

עברית

סינון לרשימה חדשה

סינון משאיר רק את הפריטים שעברו את הבדיקה.
דפוס בטוח: יצירת רשימה ריקה חדשה, ולאחר מכן add כל פריט שעובר את הבדיקה.
הרשימה הישנה אינה משתנה. הדבר נמנע מהשגיאה שנתראה בהמשך.

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.

עברית

שגיאת הסרה בזמן איטרציה

זה נראה קל: מעגל קדימה והסרת remove(i) הפריטים שאינו רוצים.
אך remove(i) מזיז כל פריט אחר מקום אחד שמאלה. המעגל אז מוסיף 1 לi ודולג על הפריט שעבר למקום הקודם.
הדוגמה להלן מנסה להסיר את כול הזוגיים אך מחמיצה אחד.

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.

עברית

מדוע הדילוג מתרחש

התחלה: [2, 4, 5], i = 0. 2 הוא זוגי, הסרתו. הרשימה הופכת ל[4, 5].
ה4 החליק מטה לתוך האינדקס 0. אך המעגל כעת מגדיר את i = 1.
בi = 1 אנו מסתכלים על 5, לא על 4. ה4 לא נבדק לעולם. הוא נשאר ברשימה.

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.

עברית

התיקון: מעגל אחורה

הליכה מהאינדקס האחרון כלפי מטה עד 0.
כאשר מסירים את האינדקס i, רק פריטים אחרי i זזים — ואנו כבר עברנו אותם.
האינדקסים שאתה עדיין צריך לבקר בהם הם קטנים מ-i, ולכן אף דבר לא יזוז מתחתך.

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.

עברית

הערה על מחזור for משופר

ייתכן שתחשה לנקות בתוך for (int x : nums).
אל תעשה זאת. שינוי גודל הרשימה במהלך מחזור for משופר גורם ל-ConcurrentModificationException ומפסיק את התוכנית.
עבור מחיקה, השתמש תמיד במחזור אינדקס אחורי כפי שצוין למעלה.

English

Common mistakes

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

עברית

טעויות נפוצות

מחיקה בעת סיור קדמי לפי אינדקס מדלג על הפריט הבא (שגיאת ההסרה).
סור באופן אחורי, או השתמש באיטרטור, בעת מחיקה.

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.

עברית

כעת תנסו בעצמכם

כל משימה ממלאת מראש את שלד המחלקה — כתוב את הקוד שלך בתוך main, או השלם את השיטה המוצגת.
לחץ על Run כדי להרכיב ולהריץ, ולאחר מכן לחץ על Check answer.
הקוד שלך נרכב ונרץ על השרת, ולכן גם ההפעלה הראשונה היא מהירה.

Explore · ⁨חקור⁩

Filtering a list · ⁨סינון רשימה⁩

Removing while looping shifts indices — step through to see why. · ⁨הסרה בזמן סיור גורמת להזזת אינדקסים — צעד אחורה כדי להבין מדוע.⁩

Complete countOdds(ArrayList<Integer> a) so it returns how many numbers in the list are odd. A number is odd when x % 2 != 0. · ⁨השלם countOdds(ArrayList<Integer> a) כך שיחזיר כמה מספרים ברשימה הם אי-זוגיים. מספר הוא אי-זוגי כאשר 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. · ⁨לחץ על הרץ כדי לראות את התוצא כאן.⁩

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. · ⁨השלם keepPositives(ArrayList<Integer> a). בנה והחזר רשימה חדשה ArrayList<Integer> שמכילה רק מספרים גדולים מ0, בסדר המקורי שלהם. אל תשנה את 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. · ⁨לחץ על הרץ כדי לראות את התוצא כאן.⁩

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). · ⁨השלם removeEvens(ArrayList<Integer> a) כך שיסיר כל מספר זוגי ממערך a עצמו. טפל אחורה באינדקס כדי לא לדלג על פריטים. אל תחזיר דבר (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. · ⁨לחץ על הרץ כדי לראות את התוצא כאן.⁩

ArrayList algorithms: filter and the remove bug · ⁨אלגוריתמים ב-ArrayList: סינון ובעיית ההסרה⁩

Doing work on a whole list

ביצוע פעולות על רשימה שלמה

Counting with a rule

ספירה עם כלל

Filtering into a new list

סינון לרשימה חדשה

The remove-while-iterating bug

שגיאת הסרה בזמן איטרציה

Why it skips

מדוע הדילוג מתרחש

The fix: loop backwards

התיקון: מעגל אחורה

A note on the enhanced for-loop

הערה על מחזור for משופר

Common mistakes

טעויות נפוצות

Now you try

כעת תנסו בעצמכם

Filtering a list · ⁨סינון רשימה⁩

Handout · ⁨חומר עזר⁩

Log in or create account · ⁨היכנס או צור חשבון⁩

Your subject · ⁨הנושא שלך⁩

All sections · ⁨כל הסעיפים⁩

Feedback & help · ⁨משוב וסיוע⁩