ArrayList의 배열 리사이징

ArrayList는 내부적으로 가변크기 배열을 이용한다.

 

하지만 배열 크기 자체가 동적으로 설정되는 것은 아니라 내부에서 새로운 크기의 배열을 생성하고 복사한다.

 

먼저 배열을 알아보자

배열은 자료구조에서 가장 기초적이면서도 핵심적인 위치에 있다.

 

인덱스를 통한 배열 접근은 O(1)로 한 번의 연산으로 데이터에 접근이 가능하다.

int[] arr = new arr[5];
arr[0] = 1;
System.print.out(arr[0]);

  

배열은 어떻게 시간 복잡도가 O(1)이 될 수 있을까?

배열은 메모리에 연속적으로 할당된다.

 

 

연속적인 메모리 할당이 주는 이점은 배열의 시작주소와 자료형을 알 수 있다면

 

(시작주소 + 자료형 크기 * 인덱스) 라는 한 번의 연산으로 데이터의 위치를 알아 낼 수 있다.

 

자료형은 배열 생성 시점에 알려야하고 배열의 시작주소는 당연히 알 수 있으니 가능한 이야기다.

 

데이터가 아무리 많다 하더라도 인덱스를 통해 변경 연산, 뒤에 추가하는 연산, 조회하는 연산은 O(1)의 시간복잡도에서 끝낼 수 있다.

 

하지만 인덱스를 알지 못하는 상황에서 값으로 데이터를 검색해야한다면 O(N)의 시간복잡도를 갖는다.

 

배열의 불변

배열은 생성 시점에 크기를 알려주고 이 후에는 그 크기를 바꿀 수 없다.

 

만약 크기를 바꿔야한다면 새롭게 큰 배열을 생성하고 기존 데이터를 복사해야한다.

 

복사하는 것 또한 연산작업으로 O(N)의 시간복잡도를 갖는다.

 

상당한 오버헤드가 발생함을 알 수 있다.

 

배열의 추가, 삭제

배열의 데이터 사이에 빈 공간 없이 운용하기 위해선 추가 삭제 시 고려해야할 점이 있다.

 

중간이나 첫 인덱스에 데이터를 삽입, 삭제하려면 삽입할 공간을 확보하기 위해서 기존 데이터를 한 칸씩 모두 밀어내야하는데

 

이 연산도 역시 O(N)의 시간복잡도를 갖는다.

 

배열 언제 사용해야 좋을까?

배열은 인덱스만 안다면 자료가 아무리 많다고 하더라도 조회나 추가 연산은 한 번만에 이루어진다는 아주 매력적인 장점을 가지고 있다.

 

하지만 자료의 크기를 정확하게 예측하지 못한다면 추가적인 연산(O(n))이 필요하고

 

무작정 Null Null한 크기를 설정한다면 메모리 낭비 문제를 피할 수 없다.

 

또한 자료의 순서가 빈번하게 바뀌어야 하거나 삽입 삭제가 빈번하다면 좋은 선택지가 될 순 없다.

 

조회가 많고, 자료의 크기를 비교적 정확하게 예측이 가능할 때 사용하면 될 것 같다.

 

자바의 ArrayList 넌 누구니

Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)

 

자바에서 ArrayList를 소개하는 첫 단락이다.

 

- 발번역

List 인터페이스를 구현한 사이즈를 변경할 수 있는 구현체이고 null을 포함한 모든 자료를 허용한다. 배열의 사이즈를 조작하는 메서드를 제공하고 해당 사이즈 배열을 저장소로 제공한다.

 

결국 배열을 이용한다는 말이지만 핵심은 배열의 크기를 자동으로 조절해준다는 점이다.

 

ArrayList는 Object 배열을 사용한다.

transient Object[] elementData; // non-private to simplify nested class access

 

transient 키워드가 붙은 이유

 

Why does ArrayList use transient storage?

 

요약하자면 ArrayList는 직렬화 시에 커스텀한 구현을 위해 transient 키워드를 통해 표준 직렬화 방식을 사용하지 않는다.

 

최상위 클래스이기 때문에 모든 자료형을 담을 수 있다.

 

하지만 쌩 Object 배열을 사용하면 모든 타입이 들어와 자료형을 일관되게 저장할 수 없다.

 

자바는 제네릭을 이용해 타입안전성을 확보한다.

 

값이 들어오는 부분과 값을 내보내는 부분에 타입을 지정해 잘못된 타입이 들어오는 것을 막는다.

 

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

E elementData(int index) {
    return (E) elementData[index];
}

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

 

 

ArrayList는 배열의 크기를 어떻게 조정할까?

 

add()메서드를 호출하면 내부적으로 아래 메서드가 호출된다.

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

 

내부에서 배열 사이즈를 체크하고 꽉 차있다면 grow()메서드를 통해 배열을 리사이징한다.

private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        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);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

 

 

배열의 새로운 사이즈를 ArraysSupport.newLength()를 호출해서 구한다.

 

첫 인자는 현재 배열의 크기, 두 번째 인자는 size(현재 배열의 크기)+1, 세 번째 인자는 현재 배열의 크기를 비트연산 한 값이다.

 

디폴트 크기가 10이고 리사이징마다 1.5배 증가한다.

 

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
    // preconditions not checked because of inlining
    // assert oldLength >= 0
    // assert minGrowth > 0

    int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
    if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
        return prefLength;
    } else {
        // put code cold in a separate method
        return hugeLength(oldLength, minGrowth);
    }
}

 

 

위 메서드의 문서에 아래와 같이 적혀있다.

The returned length is usually clamped at the soft maximum length in order to avoid hitting the JVM implementation limit.

 

JVM이 정해 놓은 크기의 최대치(SOFT_MAX_ARRAY_LENGTH, 2147483639)가 있는데

 

만약 과거 배열의 크기에 비트연산한 값이 위 한계치를 넘으면 size+1 만큼만 증가시킨다.

 

역시 자바는 설렁설렁하지 않다...

 

정리

ArrayList는 배열을 이용하기 때문에 기본 배열이 갖는 장점과 단점을 그대로 갖게된다.

 

그저 개발자의 편리함을 위해 예외처리, 배열 리사이징, 타입 체크(제네릭) 등 여러 메서드를 제공하기 위함이다.

 

연속된 메모리에 배열을 할당하기에 인덱스를 통한 접근, 순차접근은 여타 다른 자료구조에 비해 훨씬 빠르겠지만

 

중간에 요소를 추가하거나 삭제하는 연산에서 성능이 많이 떨어진다.

 

또한 메모리 측면에서도 리사이징 후에 사용하지 않는 메모리가 발생하기 쉽다.

 

자료구조를 선택할 때 적어도 이런 장단을 잘 알고 사용해야겠다.