ArrayList 알고리즘 구현

어휘

English	의미
shift/ʃɪft/	시프트
delete/dɪˈliːt/	삭제
insert/ˈɪnsɜːt/	삽입

인접한 삭제는 생략된 요소를 드러냅니다

[0, 0, 5]로 시작하여 인덱스 0을 제거한 후 i를 증가시킵니다. 두 번째 0이 인덱스 0로 이동했으므로, 전진 루프는 이를 건너뛰고 [0, 5]을 남깁니다.
For the forward while-loop taught here, stay at the same index after removal and advance only when keeping an element. It then removes both zeros and finishes with [5].

제거 후 현재 전방 인덱스를 유지하세요

remove(i) 이후, 모든 나중 요소가 한 자리씩 왼쪽으로 밀립니다. 이제 i에 있는 요소는 아직 검사되지 않았으므로, 다음 반복에서 확인하십시오.
아래 루프는 비공/null이 아닌 Integers의 List를 받아서 각 0을 제자리에 in-place으로 제거합니다. 매 반복마다 현재 크기를 사용하며, 빈 List에 대해 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++;
            }
        }
    }
}

이 루프가 종료되는 이유를 설명하세요

각 반복은either 하나를 제거하고 크기를 줄이거나, 하나를 유지하고 i를 증가시킵니다. 따라서 size() - i, 즉 아직 체크해야 할 위치의 개수는 반복마다 하나씩 감소합니다.
[0, 0, 5]로 시작하여, 상태는 i=0일 때 [0, 5], i=0일 때 [5], 그리고 i=1일 때 [5]입니다. 마지막 조건이 거짓이므로, 인덱스 범위를 벗어난 접근은 발생하지 않습니다.

후방 루프는 다른 규칙을 따릅니다

역순(later loop) 루프는 마지막 유효 인덱스로 시작합니다: for (int i = list.size() - 1; i >= 0; i--). 일치하는 요소를 remove(i)로 제거하면, 다음 i는 항상 하나 더 낮아집니다.
i에서 삭제하면 이미 검증한 나중 인덱스들만 밀립니다. 아직 확인하지 못한 앞쪽 요소들은 인덱스를 유지하므로, 제거 후 감쇠(decrementing)는此处正确; “제거 후 절대 진행하지 마라”는 보편적 규칙이 아닙니다.

Watch out

traverse 방향과 일치하는 인덱스 업데이트를 선택하십시오. 전방 while-looopy에서는 제거 후 머물고, 후방 for-loop에서는 감쇠를 계속합니다. enhanced loop 중 직접적인 구조 변경은 실패-빠른(fail-fast) 예외가 표시되지 않더라도 별도의 위험한 패턴입니다.

연습

여기서 보여주는 전진 while-루프에서는 다음 조건일 때만 i를 증가시키십시오...