🐙 ArrayList는 내부적으로 어떻게 동작하며, 어떤 상황에서 사용하면 좋을까?

 

알고리즘 할때 ArrayList를 자주 썼는데, 내부적으로는 어떻게 동작하는지 알아보기 위해 해당 포스팅을 작성해보려고 한다.

---

 

ArrayList란?

 

• Java의 동적 배열인 ArrayList는 내부적으로 배열을 기반으로 하는 자료 구조이다.
• 크기를 동적으로 조절 가능하여 원소의 추가와 삭제가 용이하며, 랜덤 액세스에 강점을 가지고 있다.
  •  중간에 원소를 추가하거나 삭제할 때는 다른 원소들을 이동시켜야 하므로 성능 저하가 있을 수 있다.
• 크기 조절은 현재 크기의 1.5 배로 확장하는 방식을 사용한다.
• 특히 동적인 데이터 크기 및 빈번한 원소 조작이 필요한 상황에서 적합한 자료구조이다.

 

ArrayList의 동적 크기 확장의 메커니즘

 

ArrayList의 동적 크기 확장은 내부적으로 배열을 사용하며, 배열이 가득 차면 현재 크기의 1.5 배로 확장된다.

확장된 배열에 기존 원소들을 복사하여 새로운 배열에 삽입하는 과정이 이루어진다.

1. 배열이 가득 참: 현재의 배열이 원소로 가득 차면, 새로운 배열이 할당된다.
2. 새로운 배열 할당: 현재 배열의 크기의 1.5 배로 새로운 배열이 할당된다
3. 기존 원소 복사: 현재 배열에 있는 원소들이 새로운 배열로 복사된다.
4. 새로운 원소 추가: 새로운 원소가 추가되거나, 삭제된 경우에는 이 과정이 진행된다.

 

이러한 동적 크기 조절 방식을 통해 ArrayList는 유연하게 원소의 추가 및 삭제를 처리하면서 성능을 유지한다.

이 과정은 시간 복잡도 O(n)을 가지며, 여기서 n은 현재 ArrayList에 저장된 원소의 개수이다.

크기를 1.5 배로 확장하므로 평균적으로 삽입 연산의 비용이 상수 시간에 근접하게 유지된다.

 

간단하게 원리를 글로 작성하면 이렇게 말할 수 있는데, 직접 내부 구조를 파헤쳐 보자.( #Java 17기준 )

 

우선, new 키워드를 통해 ArrayList객체를 생성하면 기본 생성자가 호출 될 것이다.

ArrayList<String> arrayList = new ArrayList<>();

 

elemenData는 배열이 기본 초기 용량인 DEFAULTCAPACITY_EMPTY_ELEMENTDATA라고 되어있는데,

관련된 필드도 찾아보자.

 

 

우선 elementData란 ArrayList의 요소가 저장되는 배열 버퍼로서, ArrayList의 용량이 이 배열 버퍼의 길이와 동일하다.

맨 처음에 DEFAULTCAPACITY_EMPTY_ELEMENTDATA였던 빈 ArrayList는 첫 번째 요소가 추가될 때 DEFAULT_CAPACITY인 10으로 확장된다고 적혀있는걸 볼 수 있다.

 

이어서 add()메소드를 호출해서 원소를 추가하면 어떤 과정이 일어날까?

arrayList.add("Element");

 

 

요소가 뒤에 추가될때 마다 add(E e)메소드를 호출하게 되는데, modCount++을 통해 리스트의 구조적인 수정이 일어났음을 추적한다.

 

다시 말해서 modCount는 내부적인 데이터 구조 변경을 추적하는데 사용되는 카운터(횟수)로서,

modCount의 값이 변경되면 Iterator 및 ListLiterator에서 감지하고, Iterator가 다음 요소로 진행중이었다면 리스트가 동시에 수정된것을 발견하여 ConcurrentModificationException을 발생시킨다. 이렇게 하면 동시에 여러 부분에서 리스트가 수정되는 것을 방지한다.

 

 

 

그리고 위에 있는 add(E e, Object[] elementData, int s) 메서드를 살펴보자.

 

• 첫번째 E e : 추가하려는 요소로, 제네릭으로 선언되어 있어 어떤 타입의 객체도 받을 수 있다.
• 두번째 Object[] elementData : ArrayList의 내부에서 사용되는 배열로, 현재의 리스트 요소들이 저장되어있는 배열이다.
• 세변째 int s : 추가하려는 요소 e의 위치. 현재 리스트의 크기가s일때, s위치에 e를 추가하고 리스트의 크기를 갱신한다.

private void add(E e, Object[] elementData, int s) {
    // 현재 배열의 길이가 추가하려는 위치와 같다면
    if (s == elementData.length)
        // 배열 크기가 부족하면 배열의 크기를 확장
        elementData = grow();
    // 이미 충분한 크기라면 해당 위치에 요소 추가
    elementData[s] = e;
    // 현재 리스트의 크기를 갱신
    size = s + 1;
}

 

 

즉, ArrayList의 내부 배열 길이와 추가하려는 요소의 위치가 동일하다면 grow()메소드를 통해 배열의 크기를 확장시킨다.

grow()메서드를 통해 배열의 크기를 동적으로 확장시킨다.

 

 

• elementData(현재 길이)의 길이를 확인하고, 비어있지 않거나, 기본 빈 배열이 아닌 경우에만 크기를 조절한다.
• ArraysSupport.newLength를 사용해 새로운 배열의 길이를 계산하는데 확장에 필요한 최소 공간, 추가되는 공간, 선호하는 확장크기를 고려한다.
• 새로운 배열의 길이가 계산되면 Arrays.copyof()를 사용해 현재 배열의 내용을 새로운 크기로 복사한다.
• 빈 ArrayList인 경우, 최소 DEFAULT_CAPACITY크기의 새 배열을 생성한다.
• oldCapacity >> 1 : oldCapacity를 2로 나누는 비트 이동 연산. 현재 배열의 길이를 2로 나누어 선호하는 성장 크기 설정

private Object[] grow(int minCapacity) {
    // 현재 배열의 길이
    int oldCapacity = elementData.length;

    // 기본적으로 빈 ArrayList는 DEFAULT_CAPACITY로 초기화
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 현재 배열이 비어 있지 않은 경우 또는 빈 배열이 아닌 경우
        // ArraysSupport.newLength를 사용하여 새로운 배열의 길이 계산
        int newCapacity = ArraysSupport.newLength(
                oldCapacity,                  // 현재 배열의 길이
                minCapacity - oldCapacity,    // 필요한 추가 공간
                oldCapacity >> 1              // 선호하는 성장 크기
        );
        
        // Arrays.copyOf를 사용하여 현재 배열의 내용을 새로운 크기로 복사
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        // 빈 ArrayList인 경우, 최소 DEFAULT_CAPACITY 크기의 새 배열을 생성
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

 

 

새로운 배열 길이를 계산해 줄 ArraysSpuoort.newLength()메소드를 살펴보자

 

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
    // 인라이닝을 위해 전제조건은 확인되지 않음
    // assert oldLength >= 0
    // assert minGrowth > 0

    // 선호하는 길이를 계산함 (oldLength, minGrowth, prefGrowth를 더함)
    int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // 오버플로우가 발생할 수 있음

    // prefLength가 유효한 범위 내에 있는지 확인 (0 < prefLength <= SOFT_MAX_ARRAY_LENGTH)
    if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
        // 유효한 범위 내에 있다면 prefLength를 반환
        return prefLength;
    } else {
        // 유효한 범위 밖에 있다면 hugeLength 메소드를 호출하여 처리
        return hugeLength(oldLength, minGrowth);
    }
}

private static int hugeLength(int oldLength, int minGrowth) {
    // 최소 길이를 계산함 (oldLength과 minGrowth를 더함)
    int minLength = oldLength + minGrowth;

    // 오버플로우 확인 (minLength가 음수인 경우)
    if (minLength < 0) {
        // 오버플로우가 발생하면 적절한 메시지와 함께 OutOfMemoryError를 발생시킴
        throw new OutOfMemoryError(
            "Required array length " + oldLength + " + " + minGrowth + " is too large");
    } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) { // - 8 즉, 2147483639
        // 유효한 범위 내에 있다면 SOFT_MAX_ARRAY_LENGTH를 반환
        return SOFT_MAX_ARRAY_LENGTH;
    } else {
        // 유효한 범위 밖에 있다면 minLength를 반환
        return minLength;
    }
}

 

 

해당 코드의 어느 부분이 확장되는 것일까? prefLength가 초기화되는 7번 라인을 살펴보자.

첫 번째, 세번째 매개변수로 넘어온 인자들을 가지고 선호하는 길이를 계산할 경우 아래와 같이 된다.

 

oldCapacity + (oldCapacity >> 1);

 

만약, oldCapacity가 10이라면, olcCapacity >> 1은 5가 되어 현재 배열의 길이의 절반을 나타내게 되고,

이는 배열을 1.5배 확장하는데 사용될 수 있다.

이를 통해 일반적으로 요소를 추가하는 상황에서 10 -> 15 -> 22 -> 33 -> 49 …. 로 배열 사이즈가 조정되는 것을 알 수 있다.

 

동적 크기 확장 과정에서 배열의 크기를 1.5 배로 확장하는 이유

 

왜 하필 1.5배일까? 더 많거나 적게 확장하는건 안되는 것일까?

 

• Amortized Constant Time
  • ArrayList는 주로 삽입 연산에 사용되며, 배열 크기를 1.5배로 확장하면 삽입 연산의 평균 시간 복잡도가 O(1)에 근접한다.
  • 크기를 1.5배로 확장하면 더 많은 공간이 확보되므로, 삽입 연산이 일반적으로 상수 시간 내에 수행된다.
• 중요한 수학적 특성
  • 배열 크기를 1.5배로 확장하면, 여전히 삽입이 일어날 때마다 배열의 빈 칸이 생긴다.
  • 이는 지수 함수로 나타내기 쉽게 만들어져서 크기 조절이 균형 있게 이루어진다.
• 메모리 효율성
  • 크기를 1.5배로 확장하는 것은 메모리 할당 및 복사 연산을 최소화하면서도 충분한 여유 공간을 제공합니다.
  • 상대적으로 작은 크기로 확장하면 빈번한 크기 조절 연산이 발생하게 되어, 메모리 할당 및 복사에 소요되는 시간이 늘어날 수 있습니다.
• 계산 복잡성 감소
  • 크기를 1.5배로 확장하면 크기 조절에 필요한 계산이 상대적으로 간단해집니다.
  • 새로운 크기는 현재 크기의 1.5배이므로, 비트 시프트 연산 등을 통해 빠르게 계산할 수 있습니다.

크기를 1.5배로 확장함으로써, ArrayList는 삽입 연산에 대한 성능을 일정 수준으로 유지하면서 메모리 효율성을 확보할 수 있다.

이러한 설계 선택은 일반적인 삽입 작업에서 높은 성능을 제공하면서도 크기 조절에 따른 오버헤드를 최소화하는 효과를 가져온다.

 

 

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

array(배열)과 arrayList(리스트)의 차이

arrayList의 동적원리