[Java] ArrayList 내부 구현

출처

ChatGPT

---

ArrayList는 Java의 java.util 패키지에서 제공하는 동적 배열을 기반으로 하는 컬렉션 클래스이다. ArrayList는 배열을 내부적으로 사용하여 요소들을 저장하며, 필요에 따라 자동으로 크기를 조정할 수 있다.

소스 코드 예제는 Java 8 버전의 ArrayList 소스 코드 부분들이다. 

 

 

1. 기본 구조

ArrayList는 List 인터페이스를 구현하며, 내부적으로 동적 배열을 사용하여 요소들을 저장한다. 이 배열은 필요에 따라 자동으로 크기가 조정된다.

• 관련 글 -> [프로그래밍 개념] 동적 배열과 정적 배열

주요 필드

// 기본적으로 사용되는 빈 배열로, 초기 상태에서 비어있는 ArrayList는 이 배열을 참조합니다.
private static final Object[] EMPTY_ELEMENTDATA = {};

// 빈 배열이지만, 초기 용량이 지정된 ArrayList는 이 배열을 참조합니다.
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 실제 데이터가 저장되는 배열
transient Object[] elementData;

// ArrayList의 크기(현재 저장된 요소의 수)
private int size;

 

elementData 배열은 Object 타입의 배열로, 모든 객체를 저장할 수 있는 형태이다. 하지만, 원시 타입은 저장할 수 없고, 반드시 해당 타입의 래퍼 클래스 (예: Integer, Double)로 저장된다.

 

2. 생성자

ArrayList는 다양한 생성자를 제공한다.

기본 생성자

내부 배열의 초기 크기가 10인 기본 용량으로 생성된다.

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

 

초기 용량을 지정하는 생성자

사용자가 초기 용량을 지정할 수 있다.

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
}

 

컬렉션을 인자로 받는 생성자

다른 컬렉션을 인자로 받아 초기화할 수 있다.

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

 

3. 크기 조정 Resizing

ArrayList의 가장 중요한 특징 중 하나는 배열이 동적이라는 것이다. 즉, 배열의 크기가 자동으로 조정된다. 이 작업은 새로운 요소를 추가할 때, 내부 배열의 크기가 부족하면 수행된다.

 

크기 증가 메커니즘

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
} // ChatGPT의 코드

/** 내 컴퓨터 Java 8 코드
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
**/


private void ensureExplicitCapacity(int minCapacity) {
    // 크기를 증가하기 전에 구조적 수정 횟수를 기록합니다.
    modCount++;

    // 필요한 최소 용량이 현재 배열의 길이보다 큰 경우 크기 조정
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 현재 크기의 1.5배로 증가
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

 

• 현재 크기의 1.5배로 증가: ArrayList는 기본적으로 현재 배열 크기의 1.5배로 크기를 늘린다. 즉, 배열의 길이를 늘릴 때마다 50%씩 증가한다.
• 배열 복사: 새로운 배열을 생성한 후, 기존 배열의 데이터를 새로운 배열로 복사한다.
• 최대 크기 검사: JVM이 허용하는 최대 배열 크기를 초과하지 않도록 검사한다.

 

 

4. 요소 추가 및 제거

요소 추가

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 내부 배열이 충분한지 확인
    elementData[size++] = e;           // 요소를 배열에 추가하고 size를 증가
    return true;
}

 

• 새로운 요소를 추가하기 전에 ensureCapacityInternal 메서드를 호출하여 현재 배열의 크기를 확인하고 필요하면 크기를 조정한다.
• 요소를 elementData 배열에 추가하고, size를 증가시킨다.

요소 제거

public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);

    elementData[--size] = null; // GC(가비지 컬렉션)을 돕기 위해 마지막 요소를 null로 설정

    return oldValue;
} // ChatGPT 제공 코드

/** 내 컴퓨터 Java 8 코드
public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

**/

 

 

• 요소를 제거할 때, 제거할 요소 뒤에 있는 모든 요소들을 왼쪽으로 이동시킨다.
• 이동 후, 마지막 위치의 요소는 null로 설정하여 가비지 컬렉션이 사용할 수 있도록 한다.

 

 

5. 가비지 컬렉션(Garbage Collection) 지원

ArrayList는 동적 크기 조정을 위해 배열을 사용하므로, 불필요한 객체들이 메모리에 남지 않도록 관리해야 한다. 요소를 제거할 때, 해당 인덱스의 값을 null로 설정하여 가비지 컬렉션이 메모리를 효율적으로 회수할 수 있도록 다.

 

6. 성능 특성

 

• 인덱스 접근(O(1)): 배열 기반이기 때문에 인덱스를 사용한 접근이 빠르다.
• 요소 추가(O(1) 평균, O(n) 최악): 일반적으로 끝에 요소를 추가하는 것은 빠르지만, 크기를 조정해야 하는 경우에는 느려질 수 있다.
• 요소 제거(O(n)): 요소를 제거할 때 배열의 요소들을 이동해야 하기 때문에, 요소가 많은 경우 느려질 수 있다.