배열의 조회·삽입·삭제와 시간 복잡도

배열로 회원 목록 관리하기와 객체 배열로 회원 저장소 만들기에서는 배열과 size 변수로 회원을 저장했습니다. 그때는 새 회원을 언제나 맨 끝에 붙였기 때문에 members[size]에 넣고 size를 1 늘리면 끝이었습니다. 그런데 목록 중간에 값을 끼워 넣거나 중간의 값을 지워야 한다면 이야기가 달라집니다. 배열의 칸은 위치가 고정되어 있어서, 빈자리를 만들거나 메우려면 뒤쪽 원소를 한 칸씩 직접 옮겨야 하기 때문입니다.

이 장에서는 자바의 ArrayList와 LinkedList에 해당하는 목록 자료구조를 직접 만들어 봅니다. 이 글은 그 출발점으로, 크기가 고정된 배열 위에 조회·검색·삽입·삭제를 구현합니다. 그 과정에서 연산마다 원소를 몇 번 읽거나 옮기는지 세어 보고, 그 횟수가 원소 수에 따라 어떻게 늘어나는지를 시간 복잡도로 나타내는 방법을 익힙니다. 다음 글에서는 이 배열이 가득 차면 스스로 늘어나게 만들고, 그다음 글에서는 이 목록이 왜 제네릭이어야 하는지와 제네릭 목록 안에서 배열을 어떻게 다루는지 살펴봅니다.

인덱스로 한 칸을 바로 찾는 이유

배열은 같은 크기의 칸이 한 줄로 이어진 구조입니다. 그래서 0번 칸이 어디서 시작하는지만 알면, i번 칸의 위치는 '시작 위치 + i × 칸 하나의 크기'라는 계산 한 번으로 나옵니다. values[2]를 읽든 values[2000]을 읽든 앞의 칸들을 거쳐 갈 필요가 없으니, 배열이 아무리 커도 한 칸을 읽는 데 드는 일은 같습니다.

String[]처럼 객체를 담는 배열도 마찬가지입니다. 문자열마다 길이는 다르지만, 배열의 칸에는 문자열 객체 자체가 아니라 그 객체를 가리키는 참조가 들어 있습니다. 참조는 모두 같은 크기이므로 칸 크기도 일정하고, 위치 계산도 똑같이 성립합니다.

반면 어떤 값이 몇 번 칸에 있는지 찾는 검색은 이렇게 할 수 없습니다. 값과 위치 사이에 계산할 수 있는 관계가 없으니 0번 칸부터 차례로 비교해 보는 수밖에 없습니다. 찾는 값이 맨 끝에 있거나 아예 없으면 원소 n개를 모두 비교해야 합니다. 즉 인덱스로 읽는 일과 값으로 찾는 일은 둘 다 배열을 다루는 일이지만, 드는 비용은 전혀 다릅니다.

작업 횟수가 늘어나는 모양, 시간 복잡도

비용을 비교하려면 공통의 잣대가 필요합니다. 실행 시간을 밀리초로 재면 컴퓨터마다, 또 실행할 때마다 값이 달라집니다. 그래서 자료구조의 비용은 보통 '원소가 n개일 때 핵심 작업을 몇 번 하는가'로 셉니다. 그리고 n이 커질 때 그 횟수가 어떤 모양으로 늘어나는지를 시간 복잡도(time complexity)라고 하며, 대문자 O를 쓰는 빅오 표기법(Big-O notation)으로 나타냅니다. 이 장에서는 다음 세 가지 표현을 씁니다.

빅오 표기는 정확한 횟수가 아니라 늘어나는 모양만 남깁니다. 비교를 n번 하든 2n + 3번 하든, n이 열 배가 되면 작업도 대략 열 배가 된다는 점은 같으므로 둘 다 O(n)이라고 씁니다. 상수 배와 작은 항을 버리는 이유는 원소가 충분히 많아지면 결국 늘어나는 모양이 비용을 좌우하기 때문입니다. 대신 원소가 적을 때는 버린 상수가 실제 속도를 좌우할 수도 있다는 점을 기억해 두세요.

같은 연산이라도 입력에 따라 횟수가 달라질 수 있습니다. 검색은 찾는 값이 0번 칸에 있으면 한 번 만에 끝나고, 없으면 n번 비교합니다. 이 글에서 따로 말하지 않으면 시간 복잡도는 가장 불리한 경우, 즉 최악의 경우(worst case)를 기준으로 합니다. 분할 상환은 최악의 경우나 평균과는 또 다른 기준이므로, 동적 배열을 만드는 다음 글에서 자세히 설명합니다.

더 깊이: O 표기의 엄밀한 뜻

엄밀하게 말하면 f(n) = O(g(n))은 어떤 상수 c와 n₀가 있어서 n ≥ n₀인 모든 n에 대해 f(n) ≤ c·g(n)이라는 뜻, 즉 위쪽 한계(상한)입니다. 이 정의대로라면 O(1)인 연산을 O(n)이라고 말해도 틀린 것은 아닙니다. 위아래 양쪽에서 같은 모양으로 묶인다는 것을 정확히 나타낼 때는 Θ(세타) 표기를 쓰는데, 아래쪽 한계를 나타내는 Ω까지 포함한 정의는 입력 크기·O·Ω·Θ와 정보의 개수에서 자세히 다룹니다. 실무와 대부분의 교재에서는 가장 촘촘한 상한을 O로 적는 관례를 따르며, 이 교재도 그렇게 씁니다.

배열은 목록의 크기를 모른다

배열로 목록을 만들 때 가장 먼저 구분해야 할 것은 두 가지 크기입니다. 배열의 길이 values.length는 미리 확보해 둔 칸의 수, 곧 용량(capacity)입니다. 반면 size는 그 가운데 실제로 값을 채운 칸의 수로, 목록의 크기입니다. 길이 5인 배열에 세 값을 넣었다면 용량은 5, 크기는 3이고, 3번과 4번 칸은 다음 값을 위해 비워 둔 여유 공간일 뿐 목록의 원소가 아닙니다.

문제는 배열 자신은 이 구분을 모른다는 점입니다. 다음 코드는 길이 5인 배열에 세 값을 넣은 뒤, 목록으로 치면 존재하지 않는 3번 칸을 읽습니다.

public final class SpareSlotRead {
    public static void main(String[] args) {
        String[] values = new String[5];
        int size = 0;
        values[size++] = "array";
        values[size++] = "list";
        values[size++] = "index";

        System.out.println("size=" + size + ", capacity=" + values.length);
        System.out.println("values[3]=" + values[3]);
    }
}

size=3, capacity=5
values[3]=null

3번은 배열의 인덱스 범위인 0부터 4 안에 있으므로, 자바는 아무 예외 없이 그 칸의 초깃값 null을 돌려줍니다. 목록에 없는 원소를 읽었는데도 오류가 나지 않은 것입니다. 배열이 ArrayIndexOutOfBoundsException으로 막아 주는 것은 용량을 벗어난 접근뿐이므로, 목록의 크기를 벗어난 접근은 목록이 size와 비교해서 직접 막아야 합니다.

그래서 배열 기반 목록에서 원소를 가리키는 유효한 인덱스는 0 <= index && index < size를 만족하는 값입니다. 이 조건을 어기는 요청은 배열에 손대기 전에 IndexOutOfBoundsException으로 거절해야 호출한 쪽이 실수를 바로 알 수 있습니다. 다만 삽입에는 한 가지 예외가 있는데, 이것은 삽입을 구현하면서 살펴보겠습니다.

중간에 넣으려면 뒤쪽 원소를 옮겨야 한다

[A, B, C]가 들어 있는 배열의 1번 위치에 X를 넣는다고 해 봅시다. 넣고 나면 목록은 [A, X, B, C]가 되어야 하므로 B와 C는 각각 한 칸씩 오른쪽으로 옮겨 가야 합니다. 배열에는 '사이에 끼워 넣기'라는 동작이 따로 없습니다. 빈자리를 만들려면 뒤쪽 원소를 한 칸씩 복사해서 직접 옮기는 수밖에 없습니다.

이때 옮기는 순서가 중요합니다. 다음 코드는 [array, list]의 0번 위치에 index를 넣으려고, 낮은 인덱스부터 차례로 오른쪽 칸에 복사합니다. 언뜻 자연스러워 보이지만 결과가 틀립니다.

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]

기대한 결과는 [index, array, list]인데, list가 사라지고 array가 두 번 들어갔습니다. 반복 i=0에서 titles[1] = titles[0]이 실행되면, 1번 칸에 있던 list는 어디에도 옮겨지기 전에 array로 덮입니다. 이어서 i=1의 titles[2] = titles[1]은 1번 칸을 원본으로 읽는데, 그 칸에는 이제 array가 들어 있습니다. 결국 방금 덮어쓴 값이 다음 복사의 원본이 되어 같은 값이 뒤로 번진 것입니다.

해결책은 반대 방향, 즉 마지막 원소부터 옮기는 것입니다. [A, B, C, _]의 1번에 X를 넣는다면 먼저 C를 3번 칸으로, 다음에 B를 2번 칸으로 옮긴 뒤 비게 된 1번 칸에 X를 씁니다. 높은 쪽부터 옮기면 값을 쓰는 칸이 언제나 빈칸이거나 이미 읽어서 옮겨 둔 칸이므로, 아직 읽지 않은 원본을 덮는 일이 생기지 않습니다.

중간 상태에서 C나 B가 두 칸에 함께 들어 있는 것은 문제가 되지 않습니다. 복사본을 먼저 만들어 두고, 원본이 있던 칸은 그다음 단계에서 덮어쓰기 때문입니다.

삭제는 반대로 앞쪽부터 당긴다

삭제는 삽입을 거울에 비춘 모습입니다. [A, B, C, D]에서 1번의 B를 지우면 C와 D가 한 칸씩 왼쪽으로 와서 빈자리를 메워야 합니다. 이번에는 낮은 쪽부터 옮겨야 합니다. C를 먼저 1번으로, 다음에 D를 2번으로 옮기면 값을 쓰는 칸이 언제나 지울 칸이거나 방금 옮겨 둔 칸이 됩니다.

방향을 거꾸로 하면 삽입 때와 같은 일이 벌어집니다. 뒤에서부터 당기는 잘못된 순서를 따라가 보겠습니다.

첫 대입이 아직 옮기지 않은 C를 D로 덮었기 때문에 C가 사라졌습니다. values[i + 1] = values[i]나 values[i - 1] = values[i] 같은 복사 대입은 오른쪽의 원본을 먼저 읽고 왼쪽의 목적지에 씁니다. 그러니 원소가 움직이는 방향의 맨 앞에 있는 원소부터 처리해야 합니다. 오른쪽으로 미는 삽입은 마지막 원소부터, 왼쪽으로 당기는 삭제는 지운 자리 바로 다음 원소부터 옮깁니다.

조회와 삽입의 인덱스 범위를 따로 검사하기

이제 지금까지의 규칙을 하나의 클래스로 묶어 보겠습니다. TitleArray는 용량이 고정된 문자열 목록으로, 끝 추가, 위치를 지정한 삽입, 조회, 검색, 삭제를 제공합니다. main은 array와 list를 끝에 추가한 뒤 1번 위치에 index를 끼워 넣고, 조회·검색·삭제 결과를 차례로 출력합니다.

import java.util.Arrays;
import java.util.Objects;

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 (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) {   // 조회·삭제: 0 <= index < size
            if (index < 0 || index >= size) {
                throw new IndexOutOfBoundsException(index);
            }
        }

        private void checkAddIndex(int index) {       // 삽입: 0 <= index <= size
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException(index);
            }
        }

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

index
found=2
removed=array
[index, list]

출력을 차례로 따라가 보겠습니다. 두 번의 끝 추가로 목록은 [array, list]가 되고, add(1, "index")가 list를 2번으로 옮긴 뒤 1번에 index를 써서 [array, index, list]가 됩니다. 그래서 첫 줄의 get(1)은 index입니다. indexOf("list")는 0번과 1번을 비교하고 지나가 2번에서 찾으므로 found=2를 출력합니다. remove(0)은 지운 값 array를 돌려주고 남은 두 원소를 앞으로 당기므로, 마지막 줄은 [index, list]입니다.

코드에서 눈여겨볼 곳은 인덱스 검사가 두 가지라는 점입니다. get과 remove는 이미 있는 원소를 가리켜야 하므로 checkElementIndex가 index < size까지만 허용합니다. 반면 add(index, value)는 마지막 원소 바로 뒤, 즉 index == size인 위치에도 넣을 수 있어야 합니다. 그 위치에 넣는 것이 곧 끝 추가이기 때문입니다. 실제로 add(value)는 add(size, value)를 호출하도록 구현되어 있고, 그래서 checkAddIndex는 index <= size까지 허용합니다.

두 검사를 하나로 합치면 어느 쪽으로든 문제가 생깁니다. index < size로 통일하면 끝 추가가 거절되어 빈 목록에는 아무것도 넣을 수 없습니다. 반대로 index <= size로 통일하면 get(size)가 검사를 통과해, 앞에서 본 것처럼 목록에 없는 칸의 null을 돌려줍니다. 삽입에서 size보다 큰 인덱스를 막는 이유도 비슷합니다. 크기 3인 목록에 add(4, ...)를 허용하면 값은 4번 칸에 들어가고 크기는 4가 되지만, 목록의 3번 원소는 null이 되고 정작 넣은 값은 목록 범위 밖에 놓입니다.

나머지 부분도 짧게 짚어 보겠습니다. 배열이 가득 차면 add는 IllegalStateException을 던집니다. 고정 용량 목록이니 더 넣을 곳이 없다는 사실을 알리는 것이고, 이 제한은 다음 글에서 배열을 늘리는 방식으로 없앱니다. 인덱스 검사와 용량 검사는 모두 배열을 건드리기 전에 하므로, 예외가 나도 목록은 원래 상태 그대로입니다. 또 indexOf가 values[i].equals(target) 대신 Objects.equals를 쓰는 것은, 목록에 null이 들어 있어도 NullPointerException 없이 비교하기 위해서입니다.

인덱스 오류 메시지도 살펴볼 만합니다. new IndexOutOfBoundsException(index)가 만드는 메시지는 Index out of range: 5처럼 인덱스만 담습니다. 자바의 ArrayList는 같은 상황에서 Index 3 out of bounds for length 3처럼 목록 크기를 함께 알려 주는데, 여기서 length는 배열 용량이 아니라 목록의 크기입니다. 직접 만든 목록을 다듬을 때도 인덱스와 size를 함께 보여 주면, 호출한 쪽이 무엇이 잘못됐는지 바로 알 수 있습니다.

삭제한 뒤 마지막 칸을 비우는 이유

remove의 마지막 줄 values[--size] = null은 두 가지 일을 한 번에 합니다. 전위 감소 연산자 --size는 size를 먼저 1 줄이고 그 값을 인덱스로 쓰므로, 삭제하기 전의 마지막 원소 자리, 곧 이제 목록 범위 밖이 된 칸을 가리킵니다. 그 칸에 null을 넣어 남아 있던 참조를 지우는 것입니다.

이 줄을 size--;로 바꿔도 출력은 똑같습니다. toString도 get도 size까지만 보기 때문입니다. 하지만 배열에는 참조가 그대로 남습니다. 앞의 remove(0)이라면 2번 칸에 list가 한 번 더 남는데, list는 아직 목록에 있는 원소이므로 당장은 문제가 없습니다. 그러나 마지막 원소를 지울 때는 옮길 원소가 없으므로, 그 칸에 남는 것은 방금 지운 객체 자신입니다.

가비지 컬렉터(GC)는 어딘가에서 참조하고 있는 객체, 즉 도달할 수 있는 객체를 회수하지 않습니다. 그래서 목록이 오래 살아 있다면, 논리적으로는 지워진 객체가 배열의 남은 칸 때문에 계속 메모리를 차지합니다. 이처럼 프로그램이 다시 쓰지 않을 객체를 붙잡고 있는 참조를 쓸모없는 참조(obsolete reference)라고 합니다. 복사본으로 남은 참조도 그 원소가 나중에 목록에서 지워지면 똑같이 쓸모없는 참조가 되므로, 삭제할 때마다 범위 밖이 된 칸을 비우는 것이 가장 간단한 규칙입니다. 자바의 ArrayList도 삭제한 뒤 같은 방식으로 마지막 칸을 null로 비웁니다.

위치에 따라 달라지는 이동 횟수

이제 연산마다 원소를 몇 번 옮기는지 세어 보겠습니다. 크기가 n인 목록의 index 위치에 삽입하면, index번부터 마지막 원소까지가 한 칸씩 밀리므로 이동은 n - index번입니다. 끝 추가는 index가 n이니 0번이고, 맨 앞 삽입은 n번입니다. 삭제는 지운 자리 다음부터 마지막까지 당기므로 n - index - 1번이고, 마지막 원소를 지울 때는 한 번도 옮기지 않습니다.

끝 추가가 O(1)인 것은 이 글의 TitleArray가 가득 차면 예외를 던지는 고정 용량 목록이기 때문입니다. 배열이 가득 찼을 때 더 큰 배열로 옮겨야 하는 동적 배열에서는 사정이 달라지며, 그 이야기가 다음 글의 분할 상환 O(1)입니다.

중간 삽입과 삭제를 O(n)으로 적는 것은 최악의 경우인 맨 앞 위치를 기준으로 했기 때문입니다. 위치가 고르게 섞여 들어온다고 가정해도 평균 이동 횟수는 약 n/2이므로 여전히 n에 비례합니다. 그렇다고 위치별 차이가 의미 없는 것은 아닙니다. 같은 O(n)이라도 주로 끝 근처에 넣는 프로그램과 주로 맨 앞에 넣는 프로그램은 실제로 옮기는 원소 수가 크게 다릅니다. 그래서 자료구조를 고를 때는 복잡도 표와 함께 그 프로그램이 어느 위치에서 주로 넣고 빼는지도 살펴야 합니다.

다음 문제로 계산을 확인해 보세요. 크기 8, 용량 10인 목록에서 인덱스 4에 값을 하나 삽입하는 경우와 인덱스 4의 값을 삭제하는 경우를 따로 생각합니다. 각 경우에 옮기는 원소 수와 연산 뒤의 size, 그리고 연산 뒤에 get(8)이 성공하는지를 적어 보세요.

더 깊이: System.arraycopy로 한꺼번에 옮기기

이 글에서는 이동 방향을 보여 주려고 반복문으로 한 칸씩 옮겼지만, 실무 코드와 자바의 ArrayList는 System.arraycopy(src, srcPos, dest, destPos, length)로 구간을 한꺼번에 옮깁니다. 같은 배열 안에서 겹치는 구간을 복사해도 되는지 걱정할 수 있는데, 공식 문서는 원본 구간을 임시 배열에 먼저 복사한 다음 목적지로 옮긴 것과 같은 결과가 나오도록 정해 두었습니다. 그래서 System.arraycopy(values, index, values, index + 1, size - index)는 방향을 신경 쓰지 않아도 원소들을 올바르게 한 칸씩 밉니다.

다만 옮기는 원소 수가 줄어드는 것은 아닙니다. JVM이 최적화한 방식으로 한꺼번에 옮기므로 반복문보다 대개 빠르지만, 여전히 size - index개를 옮겨야 하므로 시간 복잡도는 O(n) 그대로입니다.

게시글 저장소의 첫 버전

이 장에서는 절마다 같은 게시글 저장소 프로그램을 조금씩 바꿔 가며 실행합니다. 게시글의 제목과 조회 수를 저장하고, 입력한 순서대로 출력한 뒤 조회 수 합계를 보여 주는 간단한 프로그램입니다. 저장소 내부는 절마다 바뀌지만 출력은 같은 규칙을 따르므로, 내부를 바꿨을 때 사용자에게 보이는 동작이 달라지지 않았는지 확인하는 기준으로 씁니다.

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) {}
}

0:array-index=35
1:insert-shift=45
total=80

Entry는 제목과 조회 수를 한 쌍으로 묶은 레코드입니다. add는 빈 제목이나 0 이하의 조회 수를 IllegalArgumentException으로 거절하고, 검사를 통과한 값만 Entry로 만들어 끝에 붙입니다. 저장하기 전에 호출하는 ensureCapacity는 칸이 모자라면 더 큰 배열을 만들어 옮기는 메서드로, 다음 글의 주제입니다. 이번 실행은 두 칸짜리 배열에 게시글 두 개만 넣으므로 배열이 늘어나지 않습니다.

print와 totalViewCount는 둘 다 0번부터 size - 1번까지만 돕니다. 그래서 출력은 입력한 순서대로 0번과 1번 두 줄이고, 합계는 35 + 45 = 80입니다. 앞으로 저장소 내부를 동적 배열이나 연결 목록으로 바꾸더라도 이 세 가지, 곧 입력 순서대로 출력된다는 것과 합계가 맞는다는 것, 비어 있는 칸이 출력에 나타나지 않는다는 것은 그대로 유지되어야 합니다.

배열 기반 목록이 잘 맞는 경우

배열 기반 목록의 강점은 인덱스 조회가 O(1)이라는 점과 원소가 연속된 칸에 모여 있다는 점입니다. 약점은 앞쪽이나 중간에서 넣고 뺄 때마다 뒤쪽 원소를 옮겨야 한다는 점입니다. 그래서 어떤 작업이 많은 프로그램인지에 따라 판단이 달라집니다.

원소가 적다면 복잡도만 보고 구조를 바꿀 필요는 없습니다. 원소 수십 개를 옮기는 비용은 대개 무시할 만하고, 연속된 메모리를 차례로 읽고 옮기는 작업은 CPU 캐시와 잘 맞아서 특히 빠르기 때문입니다. CPU 캐시는 메모리에서 읽은 데이터를 이웃한 칸까지 함께 담아 두는 작고 빠른 저장소인데, 이 원리는 메모리 계층과 주기억장치에서 다룹니다. 반대로 원소가 많고 맨 앞 삽입이 계속되는데 실제로 측정해 보니 이동이 병목이라면, 그때 다른 구조를 검토할 이유가 생깁니다. 이 장의 뒤에서 만드는 연결 목록이 그 후보 가운데 하나입니다. 다만 연결 목록도 삽입할 위치까지 찾아가는 데 O(n)이 든다는 점은 그때 함께 따져 보겠습니다.

정리

• 배열은 i번 칸의 위치를 계산 한 번으로 구하므로 인덱스 조회는 O(1)이고, 값으로 찾는 검색은 앞에서부터 비교해야 하므로 O(n)입니다.
• 배열 길이는 용량이고 size는 실제 원소 수입니다. 배열은 size를 모르므로 목록이 size를 기준으로 인덱스를 검사해야 합니다.
• 조회와 삭제는 index < size까지, 삽입은 index <= size까지 허용합니다. index == size에 넣는 것이 곧 끝 추가입니다.
• 삽입은 마지막 원소부터 오른쪽으로 밀고, 삭제는 지운 자리 다음 원소부터 왼쪽으로 당깁니다. 순서를 거꾸로 하면 아직 옮기지 않은 원소를 덮어씁니다.
• 삭제한 뒤에는 범위 밖이 된 마지막 칸을 null로 비워 쓸모없는 참조를 남기지 않습니다.
• 크기 n인 목록의 index에 삽입하면 n - index번, 삭제하면 n - index - 1번 옮깁니다. 가장 불리한 위치는 맨 앞이며, 둘 다 O(n)입니다.

연습 문제

문제 1: 삽입 위치별 이동 횟수 계산하기

크기 8인 배열 기반 목록에 새 값을 하나 넣습니다. 삽입 인덱스가 0, 3, 8일 때 각각 몇 개의 원소를 오른쪽으로 옮겨야 하는지 출력하는 프로그램을 작성하세요. 실제 배열을 만들어 옮기지 말고 이동 횟수를 계산하는 메서드로 표현하며, 잘못된 인덱스가 들어오면 조용히 계산하지 말고 예외를 던지세요.

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

문제 2: 삽입과 삭제를 차례로 추적하기

용량 5인 TitleArray에 [A, B, C, D]가 들어 있습니다(크기 4). 여기에 add(1, "X")를 실행한 다음 remove(3)을 실행합니다. 각 연산이 끝난 뒤 배열 다섯 칸 전체의 상태와 size, 그리고 remove가 돌려주는 값을 적어 보세요.

문제 3: 마지막 칸을 비우지 않으면 생기는 일

remove에서 values[--size] = null;을 size--;로 바꿔도 출력은 달라지지 않습니다. 그런데도 원래 줄이 필요한 이유를 마지막 원소를 지우는 경우와 맨 앞 원소를 지우는 경우로 나누어 설명하세요.

다음 글

용량이 늘어나는 동적 배열 만들기에서는 TitleArray의 가장 큰 제약인 고정 용량을 없앱니다. 가득 찬 순간 더 큰 배열로 옮겨 가는 방법과, 그때마다 원소를 복사하는데도 끝 추가를 분할 상환 O(1)이라고 부를 수 있는 이유를 살펴봅니다.