ArrayList가 add를 수행하는 방법

들어가며

ArrayList는 어떤 과정으로 add를 수행할까?

교수님께서 X만큼씩 커진다고 하셨던 게 기억나는데, 자세히 기억나지는 않아서 정리해보려고 한다.

 

add에 대해 살펴보려고 하는 만큼,

ArrayList에 대해서는 이미 알고 있다고 가정하고 정의나 메서드의 의미 등 기초 내용에 대해서는 설명하지 않는다.

 

예시

자, 여기 한 ArrayList numbers가 있다.

List<Integer> numbers = new ArrayList<>();

 

질문! numbers에는 몇 개의 값을 넣을 수 있을까?

- 용량을 지정하지 않았으므로 기본값인 10이 capacity가 된다.

 

그럼 값을 추가해보자.

for(int i = 0; i<10; i++) {
    numbers.add(i);
}

 

0부터 9까지 10개의 값을 추가했다.

여기에서 우리는 numbers에 10이라는 값을 하나 더 추가하고 싶어졌다.

numbers.add(10);

 

add(E e)

값을 추가하고 싶기 때문에 add(10)을 사용했고, 이 메서드가 호출되는 순간 어떤 코드가 실행되는지 살펴보자.

위 사진의 코드는 ArrayList.java에 있는 코드이다.

우리가 numbers.add(10); 이 라인을 실행하는 순간 이 코드가 동작한다.

(정확히 말하면 이 코드를 low level의 코드로 바꾼 코드가 한 줄씩 실행되겠지만, 이해를 돕기 위해 이 코드로 설명하겠다.)

 

- modCount : 리스트가 구조적으로 수정된 횟수를 세는 변수이다. (구조적 수정에는 리스트의 크기를 변경하는 작업이 포함된다.)

 

add(E e) 메서드는 modCount를 하나 증가시키고, 오버로딩된 다른 add 메서드를 호출한다.

 

add(E e, Object[] elementData, int s)

 

매개변수

- E e : 제네릭 타입, ArrayList에 추가하고 싶은 값

- Object[] elementData

: ArrayList 클래스의 요소들이 실제로 저장되는 array buffer.

: ArrayList의 용량은 이 array buffer의 길이다.

: 빈 ArrayList의 경우 elementData는 DEFAULTCAPACITY_EMPTY_ELEMENTDATA('{}') 이다.

- int s : ArrayList의 현재 size (ArrayList의 size는 리스트가 갖고 있는 요소의 개수를 말한다.)

 

size와 array buffer의 길이 비교하기

ArrayList에 값을 add하고 싶은데 용량이 꽉 찬 경우, (용량이 Integer.MAX_VALUE보다 크면 예외가 발생하므로 이 경우를 제외하고)

ArrayList는 용량을 증가시키고 우리가 추가하고 싶은 값을 ArrayList에 추가해준다.

 

따라서 ArrayList에 add하고 싶은 경우, 현재 ArrayList에 저장된 객체의 개수와 ArrayList의 용량을 비교해야 한다.

if (s == elementData.length) {
    elementData = grow();
}

 

s(size)와 elementData.length(실제 요소가 저장된 배열 버퍼의 길이)가 같다면 더 들어갈 공간이 없는 것이므로

ArrayList의 용량을 증가시켜야 한다.

 

grow()

elementData를 grow()로 다시 할당하고 있다.

grow()의 소스코드를 살펴보자.

현재 ArrayList의 요소 개수(size)에 1을 더한 값을 파라미터로, 오버로딩된 grow를 반환하고 있다.

 

grow(int minCapacity)

 

매개변수

minCapacity : size + 1

 

코드

int oldCapacity = elementData.length;

- 현재 ArrayList의 용량을 oldCapacity로 둔다.

 

경우 1

if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)

- 현재 용량이 0보다 크거나

  현재 ArrayList가 {}, 즉 빈 리스트가 아닐 때 다음 로직을 실행한다.

 

if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    int newCapacity = ArraysSupport.newLength(oldCapacity,
            			minCapacity - oldCapacity, /* minimum growth */
            			oldCapacity >> 1           /* preferred growth */);
    return elementData = Arrays.copyOf(elementData, newCapacity);
}

- ArraysSupport.newLength(oldCapacity, minCapacity-oldCapacity, oldCapacity >> 1)의 값을

  새 용량(newCapacity)으로 설정한다.

 

매개변수로 넣어주는 값을 살펴보자.

- oldCapacity : 현재 ArrayList의 용량

- minCapacity - oldCapacity : (현재 ArrayList에 저장된 요소의 개수size + 1) - 현재 용량  : [최소 증가분] : 1*이다.

- oldCapacity >> 1 : 현재 용량을 1만큼 오른쪽으로 시프트연산*한 값                                     : [최대 증가분]

 

minCapacity - oldCapacity가 항상 1인 이유

1. minCapacity

- grow()에서 grow(int minCapacity)를 호출할 때, minCapacity로 size+1을 넣어 호출했다.

 

2. oldCapacity

- elementData.length이다.

 

3. add(E e, Object[] elementData, int s)에서 s == elementData.length를 비교했다.

- 위 조건이 true인 경우에만 grow()가 호출되므로 s(size) == elementData.length는 true이다.

 

4. minCapacity - oldCapacity

= (size + 1) - elementData.length

= elementData.length + 1 - elementData.length

= 1

 

따라서 최소 증가분은 항상 1이다.

 

시프트연산

1. >>, 우측 시프트연산

- 모든 값을 오른쪽으로 지정한 만큼의 비트씩 이동시킨다.

- 예) 10 >> 1 = 5

- 10을 이진수로 바꾸면 1010이고, 오른쪽으로 1비트 이동하면 _101이 된다.

   빈 곳은 0으로 채우고, 이 때 0101을 십진수로 바꾸면 5임을 알 수 있다.

- 우측 시프트연산은 1/2^N의 효과가 있음을 알 수 있다.

 

2. <<, 좌측 시프트연산

- 모든 값을 왼쪽으로 지정한 만큼의 비트씩 이동시킨다.

- 예) 10 << 1 = 

- 10은 1010이므로 왼쪽으로 1비트 이동하면 10100이 된다.

   int는 8바이트, 즉 32비트이므로 이 경우 손실되는 비트 없이 시프트연산을 처리할 수 있다.

   10100을 십진수로 바꾸면 20임을 알 수 있다.

- 좌측 시프트연산은 2^N의 효과가 있음을 알 수 있다.

 

ArraysSupport.newLength(int oldLength, int minGrowth, int prefGrowth)

이 메서드는 여러 매개변수를 받아 새 길이를 리턴하는 메서드이다.

- oldLength : 현재 길이

- minGrowth : 최소 증가분

- prefGrowth : 최적 증가분

 

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
    int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
    if (newLength - MAX_ARRAY_LENGTH <= 0) {
        return newLength;
    }
    return hugeLength(oldLength, minGrowth);
}

- 현재 길이에 최소 증가분(minGrowth)과 최적 증가분(prefGrowth) 중 큰 값을 더한 길이를 새 길이(newLength)로 정한다.

- 새 길이에서 MAX_ARRAY_LENGTH를 뺀 값이 0이거나 음수이면, 즉 새 길이가 배열최대길이보다 작거나 같으면

  이 길이(newLength)를 리턴한다.

- 그렇지 않은 경우(새 길이가 배열최대길이보다 크면) hugeLength(oldLength, minGrowth) 메서드를 반환한다.

 

ArraysSupport.hugeLength(int oldLength, int minGrowth)

이 메서드는 배열의 새 길이가 MAX_ARRAY_LENGTH 보다 큰 경우 새 길이를 정해주는 메서드다.

- 현재길이(oldLength)와 최소 증가분(minGrowth)을 매개변수로 받는다.

- 현재 길이와 최소증가분을 더한 값을 최소 길이로 정한다.

- 최소길이(minLength)가 0보다 작으면,

   (현재 길이는 양수, 최소 증가분도 양수인데 더해서 음수가 되었다는 것은 int overflow가 발생했음을 의미하므로)

   OutOfMemoryError를 발생시킨다.

- 그렇지 않고 최소길이(minLength)가 최대배열길이보다 작거나 같은 경우 최대배열길이(MAX_ARRAY_LENGTH)를 리턴한다.

 

다시 grow(int minCapacity)

ArraysSupport.newLength()를 이용해 newCapacity를 정했다.

if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    int newCapacity = ArraysSupport.newLength(oldCapacity,
            			minCapacity - oldCapacity, /* minimum growth */
            			oldCapacity >> 1           /* preferred growth */);
    return elementData = Arrays.copyOf(elementData, newCapacity);
}

- Arrays.copyOf(elementData, newCapacity)로 elementData를 변경하고 반환한다.

 

Arrays.copyOf(byte[] original, int new Length)

매개변수

- original : 원본 배열

- newLength : 새 배열길이

 

코드

1. 새 배열길이만큼 바이트 배열을 생성한다.

2. 원본 배열의 길이와 새 배열길이 중 작은 값만큼의 길이만큼, 새 배열에 원본배열의 요소들을 복사한다.

3. 복사된 배열을 리턴한다.

 

중간정리

add(E e) - add(E e, Object[] elementData, int s) - grow() - grow(int minCapacity)를 거쳐 왔다.

 

1. e를 ArrayList에 추가하고 싶다.

   우리는 add(E e)를 호출하지만, 내부적으로 add(E e, Object[] elementData, int s)가 호출된다.

2. ArrayList의 size와 elementData의 길이를 비교해본다.

    2-1. size와 길이가 같으면 grow() 메서드를 호출한다.

 

우리는 2-1에서 grow()를 살펴보고 있었다.

grow()는 ArrayList의 용량을 증가시키는 메서드로, 내부적으로 grow(int minCapacity)를 호출한다.

 

grow(int minCapacity)에서는

(i) elementData의 길이가 0보다 크거나, elementData가 빈 배열이 아닌 경우

(ii) 그렇지 않은 경우

두 가지 경우로 나누어 로직이 실행된다.

 

(i)의 경우

1. newCapacity를 정한다.

2. newCapacity 길이로 생성한 새 배열에 원본배열을 모두 복사하고 리턴한다.

 

경우 2

이제 else 구문을 살펴보자.

else는 현재 리스트 용량이 0이거나, elementData가 {}인 경우를 말한다.

 

이 경우, DEFAULT_CAPACITY와 minCapacity(size+1) 중 큰 값을 새 배열의 길이로 하여

Objecct 배열을 생성해 elementData로 설정하고 elementData를 반환한다.

 

다시 add(E e, Object[] elementData, int s)

우리는 지금까지 s(size)가 elementData.length와 같은 경우 새 배열이 어떻게 생기는지 알아봤다. (line 2-3)

 

그 후 ArrayList의 요소들이 실제로 저장되는 배열 버퍼인 elementData의 [s]번째에 원하는 객체인 e를 추가한다.

size(현재 ArrayList에 저장된 요소들의 개수)를 하나 증가시킨다.

 

끝

이렇게 긴 과정 끝에 add 메서드의 실행이 완료되었다.

 

요약

1. add 시도

2. 현재 저장된 요소의 개수와 리스트의 용량을 비교한다.

2-1. size == elementData.length 이면

       새 길이만큼 배열을 생성하고 원본 배열을 복사한 배열로 elementData를 바꾼다.

3. element[s] = e로 저장한다.

4. size를 1 증가시킨다.

 

이렇게 간단하지만, 2-1에서 newCapacity의 크기를 정하는 과정이 조금 복잡하게 느껴졌을 것이다.

그 부분을 다시한번 정리해보자.

 

새 배열길이(newCapacity) 정하기

1. 현재 배열길이가 0보다 크거나, elementData가 {}가 아닌 경우

1-1. newCapacity는 1+oldCapacity 또는 oldCapacity + oldCapacity/2 중 큰 값으로 결정된다.

1-2. newCapacity가 결정되기 전 고려해야 하는 사항 : MAX_ARRAY_LENGTH

      1-1-1. 만약 newCapacity가 MAX_ARRAY_LENGTH보다 작거나 같으면 1-1에서 정한 newCapacity가 새 배열길이가 된다.

      1-1-2. 그렇지 않으면 큰 배열길이를 정해야 하므로 huge 메서드를 호출한다.

                 1-1-3. oldCapacity + 1 값이 음수이면 overflow이므로 에러를 발생시킨다.

                 1-1-4. oldCapacity 값이 MAX_ARRAY_LENGTH와 같거나 작으면 newCapacity는 배열최대길이가 된다.

                 1-1-5. oldCapacity 값이 MAX_ARRAY_LENGTH보다 크면 newCapacity는 Integer.MAX_VALUE가 된다.

 

새 배열길이 요약

보통의 경우 현재 용량/2만큼씩 배열의 크기가 늘어나지만

배열최대길이까지 리스트가 커지는 경우 MAX_ARRAY_LENGTH 또는 Integer.MAX_VALUE로 새 길이의 배열이 생성된다.

 

 

마치며

ArrayList가 꽉 차 있을 때 add를 시도하면, 현재 용량의 절반만큼 계속해서 배열의 크기가 늘어난다.

그러다 MAX_ARRAY_LENGTH(Integer.MAX_VALUE - 8)에 가까워지고 결국 이 값을 넘으면 Integer.MAX_VALUE가 되는데,

이 값보다 더 커져야 하는 경우 에러가 발생한다.

 

이 세 줄을 이해하기 위해 여러 코드를 살펴보았는데,

어려운 건 아니었지만 newCapacity를 정하는 부분이 복잡하다고 느꼈을 만하다.

 

내부 구현을 알고 사용한다면 보다 효율적으로 자료구조를 이해하고 활용할 수 있으므로,

꼭 알아두고 넘어가면 좋을 듯하다.