ArrayList는 어떻게 데이터를 관리할까?(디버깅 과정 포함)

아래의 내용은 직접 디버깅을 통해 알아가는 과정을 포함하고 있습니다.

 

Array와의 가장 큰 차이점이라고 한다면 List는 배열의 크기를 따로 설정해주지 않아도 된다.

 

기존의 배열은 아래처럼 한정된 크기를 설정해 주고 크기 안에서만 값을 할당할 수 있었다.

int[] arr = new int[5];
arr[0] = 1;            
arr[1] = 2;

 

반면에 List는 크기를 정하지 않아도 데이터를 집어넣을 수 있다.

List<Integer> list = new ArrayList<>();
list.add(1);                           
list.add(2);

 

그러면 List는 어떻게 구성이 되어 있길래 크기를 설정하지 않아도 가능한 것일까?

ArrayList

 

가장 먼저 주목할 부분은 아래 주석의 내용이다.

 

주석 설명을 해석하면 ArrayList는 결국 용량을 가지고 있다. 왜냐면 Array가 배열이기 때문이다. 또한 내부적으로 배열을 이용하는 List 구현체인 것이다.

 

그래서 ArrayList의 필드값을 보면 아래처럼 기본 용량을 10으로 가지고 있다.

 

또한, 내부적으로 값을 저장하기 위해서 elementData라는 배열을 사용하고 있다.

 

여태 ArrayList를 만들 때 ArrayList<>() 이렇게 생성해서 초기 값을 설정한 적이 없었을 것이다.

 

그러나 아래처럼 초기값을 줘서 초기 용량을 설정할 수 있다.

 

그러면 어떻게 ArrayList는 배열의 크기를 늘려주는 것일까? 설마 배열이 꽉 차면 새로운 크기의 배열을 만들어서 이동시키나?? 너무 비효율적이지 않나??

 

위의 생각이 정확하게 일치한다.

 

즉 ArrayList는 배열이 꽉 차면 해당 새로운 배열을 생성하고 해당 배열에 값을 옮겨주고 새로운 값을 추가한다.

 

아래 add 구현 코드를 보면 알 수 있다.

 

첫 번째 사진은 우리가 값을 추가할 때 실행되는 메서드이다.

즉 add(5)를 실행하면 내부적으로 오버로딩된 두 번째 메서드가 실행된다. 이때 size의 값이 배열의 길이와 같다면 더 이상 값을 넣을 수 없기 때문에 grow()라는 메서드를 실행한다.

 

grow()도 오버로된 메서드가 2개가 존재한다. 우선 아래 메서드를 통해 grow(size + 1)을 호출한다.

 

그다음 메서드는 아래와 같다.

1. 현재 elementData.length를 oldCapacity로 저장한다. (즉 현재의 크기)
2. oldCapacity가 0보다 크거나 elementData가 초기화된 빈 배열이 아닌 경우
3. 새롭게 용량을 책정한다.

 

만약에 현재 capacity가 5라고 가정해 보자. 그러면 grow 파라미터인 minCapacity는 6이 되어 있다.(이전에 size + 1로 넘겨주었으니)

그래서 minGrowth(최소)는 1이 되고, preferredGrowth(선호)는 1비트 이동시킨다. 이건 2로 나눈 값과 같다. 즉 2가 된다.

 

그리고 새롭게 elementData 배열을 만들어서 값을 copy 해서 리턴을 시킨다. 이런 과정을 거치면 배열을 늘렸기에 새로운 데이터를 추가할 수 있게 된다.

 

그러면 디버깅을 통해서 어떻게 데이터가 늘어나는지 과정을 다시 살펴보자.

아래의 코드는 초기 사이즈가 6인 List를 선언해 두고 10번의 반복을 돌린 결과이다. BP는 ArrayList의 madCount++;에 찍어두고 확인.

List<Integer> list = new ArrayList<>(6);
for(int i=0; i<10; i++){                
    list.add(i);                        
}

 

우선 i가 5일 경우 현재 6의 크기에 딱 맞기 때문에 값을 바로 집어넣는다.

 

i가 6이 되는 순간 s == elementData.length는 충족하게 되고 grow()를 실행시킨다.

 

현재 size는 6이니 6+1 = 7이 인자로 전달된다.

 

oldCapacity는 현재 길이인 6으로 설정이 되었고

 

새롭게 newCapacity를 만드는데 6에서 3이 늘어난 9로 크기가 설정되었다.(대부분 크기를 증가시킬 때 현재 크기의 1.5배를 증가시킨다고 한다.)

 

 

기억할 점은 ArrayList는 내부적으로 배열을 사용한다. 배열의 초기 용량을 뛰어넘게 되면 내부적인 로직을 통해 대략 1.5배씩 크기를 증가시킨다고 보면 된다.