יישום אלגוריתמים של ArrayList

מילון מונחים

English	משמעות
shift/ʃɪft/	הזזה
delete/dɪˈliːt/	מחיקה
insert/ˈɪnsɜːt/	הכנסה

הסרות צמודות חושפות אלמנט שדולק

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

הסרות צמודות חשופות את שגיאת האלמנט הדולק

שמור על האינדקס הקדמי הנוכחי לאחר ההסרה

לאחר remove(i), כל אלמנט מאוחר יותר מזיז מקום אחד שמאלה. אם אלמנט תופס כעת את i, הוא טרם נבדק; בדוק אותו בפנייה הבאה.
הלולאה למטה מקבלת רשימה שאינה null של Integers שאינם null ומסירה כל אפס במקום. היא משתמשת בגודל הנוכחי בכל פנייה ואינה ביצע get על רשימה ריקה.

Example

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++;
            }
        }
    }
}

הסבר מדוע לולאה זו מסתיימת

בכל פנייה או שהיא מסירה אלמנט אחד ומצמצמת גודל, או שומרת על אלמנט ומגדילה את i. כך size() - i, מספר המיקומים שעוד לבדוק, מצטמצם באחד בכל פנייה.
ההתחל עם [0, 0, 5], המצבים הם [0, 5] ב-i=0, [5] ב-i=0, ולאחר מכן [5] ב-i=1. התנאי הסופי הוא false, ולכן אין גישה מחוץ לגבול.

לולאה אחורית עוקבת אחרי כלל שונה

לולאה הפוכה מתחילה באינדקס האחרון הקיים: for (int i = list.size() - 1; i >= 0; i--). הסר אלמנטים תואמים עם remove(i); ה-i הבא הוא תמיד אחד פחות.
מחיקה ב-i מזיזה רק אינדקסים מאוחרים, שאלה כבר נבדקו. אלמנטים מאוחרים שלא נבדקו שומרים על האינדקסים שלהם, ולכן הצמצמה לאחר הסרה היא נכונה כאן; "לעולם אל תעלה לאחר הסרה" אינו כלל אוניברסלי.

Watch out

בחר עדכון אינדקס המתאים לכיוון הטיפוס. בלולאת while קדמית, נשאר לאחר ההסרה; בלולאת for אחורית, המשך בהקטעה. שינויים מבניים ישירים בזמן לולאה משופרת הם דגם מסוכן נפרד, גם כאשר אין יוצא מהכללים של fail-fast.

אימונים

בתוך לולעת while קדמית המוצגת כאן, הקדם את i רק כאשר אתה...