ArrayList는 어떻게 Array를 가변적으로 만들었을까?

uncle.ra·2023년 7월 30일

Intro

자바에서 Array는 생성할 때, 초기 크기를 지정해 주거나, 초기값들을 설정해 주어야 한다.


// 초기 크기 지정 배열 생성하기
int[] array = new int[5];

// 값 목록으로 배열 생성하기
int[] array = new int[] {0,0,0,0,0};

그런데 Array를 기반으로 구현된 java.util.ArrayList는 어떻게 가변적으로 만들었는지 호기심이 들었다😌

ArrayList 생성자 종류

우선 ArrayList를 생성할 때 생성자는 총 3가지 존재한다.

parameter가 없는 경우

ArrayList<Integer> list = new ArrayList<>();

parameter로 initialCapacity를 지정하는 경우

ArrayList<Integer> list = new ArrayList<>(100);

parameter로 ArrayList를 지정하는 경우

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1,2,3,4,5));

여기서 눈에 들어왔던건 initialCapacity 였다🤔

내부 ArrayList Class에서 initialCapacity 값을 지정해준 생성자를 살펴봤을 때, 초기 배열 생성 시 initialCapacity에 지정해준 크기에 따라 배열 객체가 생성 되는 걸로 보였다.

그렇다면 initailCapacity를 지정해주지 않고 생성 시에는 크기가 몇으로 설정될까?

초기에는 빈 배열로 생성되는 것으로 확인이 된다. 즉 저장 공간은 0이다?!

The array buffer into which the elements of the ArrayList are stored. The capacity of the ArrayList is the length of this array buffer. Any empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to DEFAULT_CAPACITY when the first element is added.

위 내용을 토대로 생각했을 때, 값을 처음 추가할 경우 공간이 10개(DEFAULT_CAPACITY)인 배열로 확장된다로 이해할 수 있었다.

배열의 공간을 다 채웠을 때는 어떻게 동작할까?

public Class Main {
	private void checkArrayListAddMethod() {
    	ArrayList<Integer> list = new ArrayList<>(5);
        for(int i = 1; i <= 5; i++) {
            list.add(i);
        }

        list.add(6);
        System.out.println("list = " + list);
    }

}

처음 ArrayList 생성 시 initailCapacity = 5를 주었다.
배열의 공간을 for문을 통해 전부 채운 후에, list.add(6)을 해준다.

list.length와 배열의 총 저장 공간이 같을 때, grow() 를 통해 배열의 저장 공간을 늘리게 된다.

grow()의 기존에 저장 공간(5) + 1을 parameter로 넘겨주고,

newCapacity()로 새롭게 받아온 크기의 공간으로 배열을 복사하게 된다.

저장 공간은 어떤식으로 확장될까?

여기서 파란 네모에 표시된 코드는 파라미터 없이 생성된 ArrayList에서 처음 add했을 때 사이즈가 10으로 커지는 걸 보여준다.

빨간 네모에 표시된 코드는 그 이후의 저장 공간을 확장시키는 경우다.
어떻게 커지는지 직접 테스트 해보았다.

public Class Main {
	private int newCapacity(int oldCapacity) {
        int newCapacity = oldCapacity + (oldCapacity >> 	1);
        System.out.println("oldCapacity=" + oldCapacity + "-> newCapacity=" + newCapacity);
        return newCapacity;
    }
    
    private  void checkGrowSize() {
        int oldCapacity = 5;
        for(int i = 1; i <= 10; i++) {
            oldCapacity = this.newCapacity(oldCapacity);
        }
    }

}

저장공간은 기존 저장공간 + 0.5 크기로 커지는걸 확인할 수 있다.

그렇다면 ArrayList를 언제 사용하면 좋을까?

(업데이트 일시: 23.08.24)

ArrayList는 add() method를 통해 마지막 요소에 추가 하는 작업은

일반적인 경우 시간 복잡도 O(1)을 가진다.
하지만, 저장 공간을 초과했을 경우 1.5배 크기의 새로운 배열을 생성 후, 기존 배열을 확장된 새로운 배열에 복사하는 작업이 들어가기 때문에 O(N) 만큼 소요된다.

필자가 ArrayList와 LinkedList에 대해서 성능 비교를 해본 글 인데 카테고리 중 마지막에 요소를 추가하는 경우를 살펴보면 조금 더 구체적으로 알 수 있다.

요구사항에 따라 어떤 자료구조를 사용할지 달라지겠지만 ArrayList는 아래 두 가지의 경우에 사용하면 좋을 것 같다.

저장 공간의 크기를 정확하게 혹은 대략적으로 알고 있는 경우
그리고 비교적 전체 공간을 사용할 경우

2번의 경우는 너무 애매모호하게 들리겠지만 초반에 100,000 만의 크기의 ArrayList를 생성했는데 그 안에 데이터를 200개 정도의 공간만을 사용한다고 하면 메모리 낭비임이 분명하기 때문이다..! 시간 복잡도 뿐만 아니라 공간 복잡도 역시 고려해서 어떤 자료구조를 사용하면 좋을지 판단하면 좋을 것 같다😁

Conclusion

ArrayList는 배열 기반으로 만들어져 있다.
초기 생성시 initialCapacity를 지정하지 않으면, 생성 후 add() method 호출 시, 10개의 저장 공간(capacity)을 확보한다.
저장 공간을 넘어서서 add() method를 호출 할 경우, 새로운 배열을 복사해서 배열을 재생성 해준다. 이때 저장 공간은 기존에 1.5배로 확보한다.
ArrayList는 add() method를 통해 마지막 요소에 추가 하는 작업은 일반적인 경우 시간 복잡도 O(1)을 가진다. 하지만, 저장 공간을 초과했을 경우 1.5배 크기의 새로운 배열을 생성 후, 기존 배열을 확장된 새로운 배열에 복사하는 작업이 들어가기 때문에 O(N) 만큼 소요된다.
그렇기 때문에 미리 어느 정도의 공간을 차지할지 정확하게 혹은 대략적으로 알고 있는 경우, 그리고 비교적 전체공간을 사용할 경우에 선택하면 좋은 자료구조라고 생각한다.

이번에 ArrayList를 공부하며, 어떻게 Array를 기반으로 가변적일 수 있는지는 명확하게 인지할 수 있었다. 내가 저장 공간을 얼마나 가져갈 지를 명확하게 알고 있다면 상관 없지만, 그렇지 않은 경우에 capacity를 어느 정도로 지정하면 좋을지에 대한 의문이 들었다.🥺 이 부분에 대해서도 테스트 후에 포스팅 해봐야겠다