Triển khai Các thuật toán ArrayList

Từ vựng

English	Ý nghĩa
shift/ʃɪft/	dịch chuyển
delete/dɪˈliːt/	xóa
insert/ˈɪnsɜːt/	chèn

Xóa các phần tử liền kề tiết lộ lỗi bỏ sót phần tử

Bắt đầu từ [0, 0, 5], xóa chỉ mục 0 rồi tăng i. Số 0 thứ hai đã dịch chuyển vào index 0, nên vòng lặp tiến tới sẽ bỏ sót nó và giữ lại [0, 5].
Đối với vòng lặp while tiến trình được dạy ở đây, hãy giữ nguyên chỉ số sau khi xóa và chỉ tăng lên khi giữ lại một phần tử. Khi đó nó sẽ loại bỏ cả hai số không và kết thúc với [5].

Các phép xóa liền kề tiết lộ lỗi bỏ sót phần tử

Giữ nguyên chỉ mục tiến tới hiện tại sau khi xóa

Sau khi remove(i), mọi phần tử sau đó sẽ dịch chuyển một vị trí sang trái. Nếu một phần tử hiện nằm ở vị trí i, thì nó chưa được kiểm tra; hãy xem xét nó trong lần lặp tiếp theo.
Vòng lặp dưới đây chấp nhận một danh sách Integers khác null và xóa mọi số 0 tại chỗ. Nó sử dụng kích thước hiện tại trong mỗi lần lặp và không thực hiện get nào trên một danh sách rỗng.

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

Giải thích tại sao vòng lặp này kết thúc

Mỗi lần lặp hoặc xóa một phần tử và giảm size, hoặc giữ lại một phần tử và tăng i. Do đó size() - i, số vị trí còn lại cần kiểm tra, giảm đi một đơn vị trong mỗi lần lặp.
Bắt đầu từ [0, 0, 5], các trạng thái lần lượt là [0, 5] tại i=0, [5] tại i=0, sau đó là [5] tại i=1. Điều kiện cuối cùng là sai, do đó không xảy ra truy cập ngoài biên.

Một vòng lặp ngược tuân theo quy tắc khác

Vòng lặp ngược bắt đầu từ chỉ mục tồn tại cuối cùng: for (int i = list.size() - 1; i >= 0; i--). Xóa các phần tử trùng khớp bằng remove(i); giá trị i tiếp theo luôn nhỏ hơn một đơn vị.
Xóa tại i chỉ dịch chuyển các chỉ mục phía sau, những chỉ mục này đã được kiểm tra trước đó. Các phần tử chưa được kiểm tra phía trước vẫn giữ nguyên chỉ mục của chúng, vì vậy giảm i sau khi xóa là đúng đắn ở đây; “không bao giờ tăng sau khi xóa” không phải là quy tắc phổ quát.

Watch out

Chọn cách cập nhật chỉ mục phù hợp với hướng duyệt. Trong while-loop tiến tới, hãy giữ nguyên sau khi xóa; trong for-loop ngược, tiếp tục giảm. Thay đổi cấu trúc trực tiếp trong khi duyệt nâng cao là một mẫu không an toàn riêng biệt, ngay cả khi không xuất hiện ngoại lệ fail-fast.

Luyện tập

Trong vòng lặp while theo hướng trước được hiển thị ở đây, chỉ tiến hành i khi bạn...