[Java] ArrayList는 어떻게 동적으로 사이즈가 늘어나는가? add() flow(동작 방식)

ArrayList add() 동작방식

ArrayList는 내부에서 elementData 배열을 기반으로 구성되어 있다.

 

• 생성자를 통해서 직접 element 배열의 capacity 설정이 가능하다. 기본 Capacity는 10이다.
• ArrayList의 기본 생성자를 사용할 경우 elementData에 EMPTY_ELEMENTDATA (빈 Object 배열)을 할당한다.

 

add()의 내부구조

modCount++로 구조적으로 변경된 횟수를 카운트한다.

add(e, elementData, size);

 

위의 로직을 살펴보자.

 

• 두 번째 파라미터는 오브젝트형 배열을 인자로 받고있고, 세 번째 파라미터는 int형 정수(size)를 받고있다.
• s와 elementDate의 길이를 비교하여 배열의 사이즈를 조정해야 하는지 체크한다.
• elementData = grow(); 이 부분이 배열의 크기를 동적으로 늘어나게 해준다.
• size = s + 1; 클라이언트에서 보여질 arrayList의 사이즈를 늘린다. arrayList에서 size() 메서드를 사용하면 해당 변수를 반환한다

grow() 한 번 살펴볼까?

• int minCapacity를 파라미터로 갖는 첫번 째 grow(int minCapacity)는 기존의 elemantData(클라이언트는 arrayList를 사용한다면 이 배열을 사용할 것이다)를 newCapacity 길이만큼 새로 늘어난 배열에 카피한다.
• 파라미터가 없는 두번 째 grow()는 minCapacity(최소 용량)로 현재 사이즈에서 +1을 인자로 넣어준다.

grow(int minCapacity) 메서드의 newCapacity(minCapacity)도 살펴보자.

• int newCapacity = oldCapacity + (oldCapacity >> 1); 기존 용량 + 기존 용량/2 (우측 쉬프트 연산)
• ArrayList 기본 생성자를 사용할 경우 elementData에 EMPTY_ELEMENTDATA (빈 Object 배열)을 할당한다. 맨 처음 등장하는 if문은 새로운 용량이 기존의 용량의 +1 된 사이즈보다 작을 때, elementData이 DEFAULTCAPACITY_EMPTY_ELEMENTDATA (빈 Object 배열) 이라면 DEFAULT_CAPACITY (10) 으로 minCapacity를 설정한다.
• return (newCapacity - MAX_ARRAY_SIZE <= 0) ? newCapacity  : hugeCapacity(minCapacity); 새로운 용량이 기존 용량의 +1 된 사이즈보다 크면 이 로직을 수행한다.
• MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 이다. 즉, 2147483639

 

 

hugeCapacity(minCapacity)를 살펴보자.

 

최소용량이 MAX_ARRAY_SIZE를 넘어갈 경우 int의 최대치를 용량으로 부여하고, int의 범위를 넘어서면 outOfMemory 발생

정리

ArrayList 기본 생성자를 통해 사용 하고 있을 경우를 생각 해보면 element 배열 크기가 0 이기 때문에
첫 element 를 add 할때 배열의 resize 가 발생하고 배열 크기는 10 으로 설정 된다.
이후 ArrayList 에 10개의 데이터가 있고 데이터를 추가 하려고 하면 resize 가 발생하여 15 가 된다.
이렇게 임의의 capacity 를 설정하지 않는 일반적인 상황에서는 10 -> 15 -> 22 -> 33 -> 49 .... 로 배열 사이즈가 조정 된다.

 

element 배열의 capacity 가 조정 된 후 add() 하려는 element 가 배열에 추가 되고, ArrayList 의 size 가 1 증가 한다.

 

결론적으로  element를 add하려고 할 때, capacity가 elementData(배열)의 길이와 같아지면 일반적인 상황에서 기존의 용량 + 기존 용량/2 만큼 크기가 늘어난 배열에 기존 elementData를 copy한다.

 

이런 원리로 arrayList가 동적으로 크기가 늘어날 수 있는 것이다.

 

grow() 메서드로 용량을 늘린 뒤, 추가하려는 element를 할당하면 클라이언트 입장에서는 자동으로 사이즈를 늘려주면서 element가 추가된 것으로 보인다.

 

실제로는 가지고 있던 용량이 꽉 찼을 때, 용량이 기존의 1.5배를 늘린 새로운 배열에 기존 배열을 copy하는 것이다.

 

 

출처:

Carray On Progamming

FunDev Stidio