การ Implement Algorithms ของ ArrayList

คำศัพท์

English	ความหมาย
shift/ʃɪft/	การเลื่อน
delete/dɪˈliːt/	ลบ
insert/ˈɪnsɜːt/	แทรก

การลบที่อยู่ติดกันเผยให้เห็นปัญหาการข้ามองค์ประกอบ

เริ่มจาก [0, 0, 5] ลบดัชนี 0 แล้วเพิ่ม i ตัวเลขศูนย์ที่สองจะเลื่อนเข้ามาอยู่ในดัชนี 0 ดังนั้นลูปไปข้างหน้าจึงข้ามมันไปและเหลือ [0, 5]
สำหรับ while-loop แบบไปข้างหน้าที่สอนในที่นี้ ให้อยู่ที่ดัชนีเดิมหลังจากลบและ_advance เฉพาะเมื่อต้องการเก็บองค์ประกอบไว้ มันจะลบตัวเลขศูนย์ทั้งสองออกและจบลงด้วย [5]

Adjacent removals reveal the skipped-element bug

รักษาดัชนีไปข้างหน้าปัจจุบันหลังจากลบ

หลังจาก remove(i) ทุกองค์ประกอบถัดไปจะเลื่อนไปทางซ้ายหนึ่งตำแหน่ง หากมีองค์ประกอบใดอยู่ใน i ในตอนนี้它还未被检查; ตรวจสอบ它在下一次迭代中。
ลูปด้านล่างรับลิสต์ของ Integer ที่ไม่เป็น null และไม่มีความยาวเป็นศูนย์ แล้วลบเลข 0 ทั้งหมดออกในตำแหน่งเดิม โดยใช้ขนาดปัจจุบันในแต่ละรอบและไม่ได้เรียกใช้ 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. เงื่อนไขสุดท้ายเป็นเท็จ ดังนั้นจึงไม่มีการเข้าถึงข้อมูลนอกขอบเขตของอาร์เรย์

ลูปย้อนกลับปฏิบัติตามกฎที่แตกต่างออกไป

การวนลูปย้อนกลับเริ่มต้นที่ดัชนีสุดท้ายที่มีอยู่จริง: for (int i = list.size() - 1; i >= 0; i--) ลบองค์ประกอบที่ตรงกันด้วย remove(i); ค่า i ถัดไปจะเป็นค่าน้อยลงเสมอหนึ่ง
การลบที่ตำแหน่ง i จะทำให้เฉพาะดัชนีถัดไปเลื่อนตำแหน่ง ซึ่งได้ผ่านการตรวจสอบแล้ว องค์ประกอบที่ยังไม่ได้ตรวจสอบด้านหน้าจะคงดัชนีเดิมไว้ ดังนั้นการลดค่า i หลังการลบจึงถูกต้องในกรณีนี้; คำว่า "ห้ามเพิ่มค่าหลังการลบ" ไม่ใช่กฎสากล

Watch out

เลือกการอัปเดตดัชนีให้สอดคล้องกับทิศทางการ遍历. ใน while-loop แบบไปข้างหน้า ให้หยุดอยู่หรือเพิ่มค่าหลังการลบ; ใน for-loop แบบย้อนหลัง ให้ลดค่าต่อ. การเปลี่ยนแปลงโครงสร้างโดยตรงระหว่าง enhanced loop เป็นรูปแบบที่ไม่ปลอดภัยแยกต่างหาก แม้จะไม่เกิด fail-fast exception ก็ตาม

ฝึกฝน

ใน while-loop แบบ forward ที่แสดง在這裡 advancement i ก็ต่อเมื่อคุณ...