배열 인덱스와 삽입 비용

배열은 같은 타입의 칸을 연속된 주소에 두기 때문에 인덱스 조회가 빠릅니다.

그러나 “빠르다”는 말만 외우면 중간 삽입에서 기존 값을 덮어쓰는 실수를 놓칩니다.

이 절은 게시글 저장소 항목을 배열에 넣으며 조회 횟수와 이동 횟수를 따로 기록합니다.

끝 삽입, 첫 삽입, 중간 삽입이 왜 다른지 실제 상태 변화로 확인합니다.

이 장에서 처음 사용하는 시간 복잡도는 실제 밀리초가 아니라 입력 원소 수가 커질 때 작업 횟수가 어떤 모양으로 늘어나는지를 나타냅니다.

원소 수를 n이라고 할 때 다음 세 표현부터 사용합니다.

표현	뜻	배열 예
`O(1)`	원소 수가 늘어도 핵심 작업 수가 거의 일정	인덱스로 한 칸 조회
`O(n)`	원소 수에 비례해 작업이 늘어남	처음부터 끝까지 검색
상환 `O(1)`	가끔 큰 확장이 있지만 여러 연산에 나누면 평균이 일정한 수준	동적 배열의 끝 추가

Big-O는 정확한 실행 시간을 보장하지 않습니다.

먼저 실제로 읽거나 옮긴 원소 수를 세고, 그 증가 모양에 이름을 붙입니다.

평균·최악·상환 조건은 해당 구현을 배울 때 빠뜨리지 않고 함께 적습니다.

정방향 복사와 기존 값 소실

중간에 빈칸을 만들 때 낮은 인덱스부터 복사하면 방금 옮긴 값이 다음 반복의 원본이 됩니다.

실행 결과는 원래 두 번째 값인 목록이 사라지는 잘못된 상태를 고정합니다.

lab/ArrayInsertOverwriteBug.java

import java.util.Arrays;

public final class ArrayInsertOverwriteBug {
    public static void main(String[] args) {
        String[] titles = {"array", "list", null, null};
        int size = 2;
        int index = 0;
        for (int i = index; i < size; i++) {
            titles[i + 1] = titles[i];
        }
        titles[index] = "index";
        size++;
        System.out.println(Arrays.toString(Arrays.copyOf(titles, size)));
    }
}

관찰 결과

[index, array, array]

복사 방향이 읽을 원본을 먼저 파괴했습니다.

오른쪽 이동은 마지막 원소부터 시작해야 하고, 왼쪽 이동은 제거 위치 다음 칸부터 시작해야 합니다.

배열 자체는 논리 크기를 모르므로 size를 별도 상태로 관리해야 합니다.

조회·검색·삽입 비용 분리

유효한 조회 인덱스는 0 이상 size 미만이며 용량과 혼동하지 않습니다.
삽입은 먼저 공간을 확보한 다음 뒤에서 앞으로 원소를 이동해야 덮어쓰기를 막습니다.
삭제는 제거값을 보존하고 앞으로 당긴 뒤 사용하지 않는 슬롯을 null로 비웁니다.
size는 논리 원소 수이고 배열 길이는 물리 용량이므로 두 값의 역할이 다릅니다.
실패는 공개 API에서 예외로 고정해 내부 배열 예외가 새어 나오지 않게 합니다.
연산 비용은 코드 줄 수가 아니라 이동하거나 따라간 원소 수로 비교합니다.

조회·삽입 구분 분리

완성 구현은 조회용 구분과 삽입용 구분을 분리합니다.

add(size, 값)는 허용되지만 get(size)는 허용되지 않습니다.

remove 뒤의 마지막 사용 슬롯을 null로 지워 더 이상 쓰지 않는 객체가 배열 때문에 유지되는 일도 막습니다.

src/ArrayIndexOperations.java

import java.util.Arrays;

public final class ArrayIndexOperations {
    public static void main(String[] args) {
        TitleArray titles = new TitleArray(5);
        titles.add("array");
        titles.add("list");
        titles.add(1, "index");
        System.out.println(titles.get(1));
        System.out.println("found=" + titles.indexOf("list"));
        System.out.println("removed=" + titles.remove(0));
        System.out.println(titles);
    }

    private static final class TitleArray {
        private final String[] values;
        private int size;

        TitleArray(int capacity) {
            values = new String[capacity];
        }

        void add(String value) {
            add(size, value);
        }

        void add(int index, String value) {
            checkAddIndex(index);
            if (size == values.length) throw new IllegalStateException("full");
            for (int i = size - 1; i >= index; i--) {
                values[i + 1] = values[i];
            }
            values[index] = value;
            size++;
        }

        String get(int index) {
            checkElementIndex(index);
            return values[index];
        }

        int indexOf(String target) {
            for (int i = 0; i < size; i++)
                if (java.util.Objects.equals(values[i], target)) return i;
            return -1;
        }

        String remove(int index) {
            checkElementIndex(index);
            String old = values[index];
            for (int i = index + 1; i < size; i++) {
                values[i - 1] = values[i];
            }
            values[--size] = null;
            return old;
        }

        private void checkElementIndex(int index) {
            if (index < 0 || index >= size) throw new IndexOutOfBoundsException(index);
        }

        private void checkAddIndex(int index) {
            if (index < 0 || index > size) throw new IndexOutOfBoundsException(index);
        }

        public String toString() {
            return Arrays.toString(Arrays.copyOf(values, size));
        }
    }
}

조회·삽입 범위의 차이

get(index)와 remove(index)는 이미 존재하는 원소를 가리켜야 하므로 0 <= index && index < size만 허용합니다.

반면 add(index, value)는 현재 마지막 원소 뒤에도 새 값을 붙일 수 있어 index == size가 유효합니다.

두 조건을 하나의 검사 메서드로 합치면 끝 추가가 거부되거나 존재하지 않는 원소 조회가 허용됩니다.

용량은 배열이 확보한 칸 수일 뿐 조회 가능한 원소 수가 아닙니다.

길이 10 배열에 세 값만 넣었다면 3부터 9까지는 저장 여유이지 목록 원소가 아닙니다.

공개 메서드의 오류 메시지에는 index와 size를 넣고 내부 배열 길이는 구현 정보로 감춥니다.

이동 방향 수동 추적

[A, B, C, _]의 1번에 X를 넣을 때 먼저 C를 3번으로, 다음 B를 2번으로 옮기고 마지막에 X를 1번에 씁니다.

높은 쪽에서 낮은 쪽으로 움직이면 아직 읽지 않은 원본이 보존됩니다.

삭제는 반대로 제거 위치 다음 값부터 낮은 쪽으로 당겨야 같은 원소를 두 번 복사하지 않습니다.

끝 추가는 이동 0회, 첫 추가는 기존 size회, 가운데 추가는 size - index회입니다.

Big-O가 모두 O(n)인 경우에도 실제 이동량은 위치에 따라 다릅니다.

게시글 저장소가 시간순 끝 추가를 주로 한다면 이 분포를 선택 근거로 기록해야 합니다.

제거 뒤 null 정리가 필요한 이유

참조 배열에서 size만 줄이고 마지막 슬롯을 비우지 않으면 논리 목록에서는 사라진 객체를 배열이 계속 가리킵니다.

GC는 도달 가능한 참조를 회수하지 않으므로 장시간 살아 있는 목록에서 보이지 않는 보유가 누적될 수 있습니다.

values[--size] = null은 메모리 관리와 디버깅 양쪽에서 삭제 완료를 표시합니다.

인덱스 순서 보존

누적 CLI의 첫 저장소는 작은 동적 배열입니다.

사용자는 입력 순서대로 기록을 보고 합계를 얻습니다.

이 장의 직접 구현과 분리해 애플리케이션 규칙을 먼저 고정하면 이후 LinkedList로 교체할 때 회귀 결과를 비교할 수 있습니다.

app/PostRepositoryCliCH141.java

public final class PostRepositoryCliCH141 {
    public static void main(String[] args) {
        PostRepository repository = new PostRepository();
        repository.add("array-index", 35);
        repository.add("insert-shift", 45);
        repository.print();
        System.out.println("total=" + repository.totalViewCount());
    }

    private static final class PostRepository {
        private Entry[] entries = new Entry[2];
        private int size;

        void add(String title, int viewCount) {
            if (title == null || title.isBlank()) throw new IllegalArgumentException("title");
            if (viewCount <= 0) throw new IllegalArgumentException("viewCount");
            ensureCapacity(size + 1);
            entries[size++] = new Entry(title, viewCount);
        }

        private void ensureCapacity(int required) {
            if (required <= entries.length) return;
            Entry[] grown = new Entry[Math.max(required, entries.length * 2)];
            System.arraycopy(entries, 0, grown, 0, size);
            entries = grown;
        }

        int totalViewCount() {
            int total = 0;
            for (int i = 0; i < size; i++) {
                total += entries[i].viewCount();
            }
            return total;
        }

        void print() {
            for (int i = 0; i < size; i++) {
                Entry entry = entries[i];
                System.out.println(i + ":" + entry.title() + "=" + entry.viewCount());
            }
        }
    }

    private record Entry(String title, int viewCount) {}
}

CLI 회귀 기준은 세 가지입니다.

첫째, 0번과 1번 출력이 입력 순서를 보존합니다.

둘째, 두 게시글의 조회수 합은 80입니다.

셋째, 내부 배열의 남은 칸은 출력에 나타나지 않습니다.

이 기준을 고정하면 이후 용량 증가나 연결 저장소로 교체해도 사용자 관점의 차이를 즉시 찾을 수 있습니다.

배열 기반 목록이 맞는 작업 부하

질문	관찰할 값	선택 또는 조치
인덱스 조회가 많은가	`get` 호출 비율	연속 배열 우선
중간 삽입이 많은가	평균 이동 칸 수	연결 구조 검토
최대 크기를 아는가	용량 상한	고정 배열 가능
오류 진단이 필요한가	경계 예외 위치	공개 메서드에서 검사

데이터가 작다면 Big-O만으로 선택하지 않습니다.

인덱스 조회의 단순성, CPU 캐시의 연속 접근, 구현 복잡도를 함께 봅니다.

반대로 앞 삽입이 연속되고 이동량이 병목으로 측정되었다면 연결 구조를 검토할 근거가 생깁니다.

연습 문제

크기 8인 배열 목록에 새 값을 넣습니다.

인덱스 0, 3, 8에서 각각 몇 칸을 오른쪽으로 옮겨야 하는지 출력하세요.

실제 배열을 복사하지 말고 이동량 공식을 코드로 표현합니다.

정답과 해설

끝 위치 8에는 기존 원소가 없으므로 0회입니다.

나머지는 삽입 인덱스부터 마지막 기존 원소까지의 개수인 size - index입니다.

잘못된 인덱스도 조용히 계산하지 않도록 먼저 검사합니다.

exercise/ArrayShiftCountSolution.java

public final class ArrayShiftCountSolution {
    public static void main(String[] args) {
        int size = 8;
        for (int index : new int[] {0, 3, 8}) {
            System.out.println(index + "=" + movesForInsert(size, index));
        }
    }

    private static int movesForInsert(int size, int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
        }
        return size - index;
    }
}

출력은 0=8, 3=5, 8=0입니다.

이 숫자는 삽입 코드의 반복 횟수와 정확히 대응하므로 성능 설명을 추측이 아니라 실행 가능한 규칙으로 바꿉니다.

인덱스 규칙 최종 확인

조회는 index < size, 삽입은 index <= size라는 차이를 코드 없이 말할 수 있어야 합니다.

오른쪽 이동은 뒤에서 시작하고 왼쪽 이동은 앞에서 시작합니다.

remove가 끝난 뒤 마지막 사용 슬롯은 null이어야 합니다.

이 세 규칙이 유지되면 고정 배열 목록의 기능 규칙은 완성됩니다.

이 페이지의 목차