Array vs Dynamic Array

Array

배열은 메모리 상에서 데이터가 연속적으로 연결되어 있는 선형 자료구조

이처럼 크기는 고정되어 있으며 변경될 수 없습니다.

Dynamic Array

Dynamic Array는 메모리 상에서 데이터가 연속적으로 연결되어 있는 선형 자료구조 입니다.

크기가 동적으로 변경될 수 있으나, 근본적으로 Array 기반으로 구현되어 있습니다.

여유 공간이 없으면 사이즈를 2배(Java) 혹은 50%씩 늘립니다.

Java의 경우 사이즈를 2배씩 늘리도록 구현되어 있어, 데이터를 20억개 넣기 까지 30번만 resizing 하면 되기 때문에 큰 부하가 오지 않습니다.

Resizing에 걸리는 시간을 알아보도록 하겠습니다.

초기 사이즈 지정 X

public class Resizing {

    private static final int MAX = 200_000_000;

    // 처음에 파라미터를 주지 않으면 10칸짜리 배열을 만들어준다. (List 에 내부적으로 있음)
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();

        long start = System.currentTimeMillis();

        for (int i = 0; i < MAX; i++) {
            list.add(i);
        }

        long end = System.currentTimeMillis();

        System.out.println((end - start) / 1000.0);
    }
}

초기 사이즈 MAX로 지정

public class Resizing {

    private static final int MAX = 200_000_000;

    // 처음에 파라미터를 주지 않으면 10칸짜리 배열을 만들어준다. (List 에 내부적으로 있음)
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>(MAX);

        long start = System.currentTimeMillis();

        for (int i = 0; i < MAX; i++) {
            list.add(i);
        }

        long end = System.currentTimeMillis();

        System.out.println((end - start) / 1000.0);
    }
}

초기 사이즈를 지정해주지 않으면 0.238s, 초기 사이즈를 지정할 경우 0.238s가 걸리는 것을 확인할 수 있습니다.