[Java] ArrayList의 capacity, size, 그리고 add(int index, E element)

문제

알고리즘 문제를 풀던 중 2차원 배열 형태를 ArrayList<ArrayList<>> 형태로 구현하려고 했다. 코드는 다음과 같다.

N = Integer.parseInt(br.readLine());

tree = new ArrayList<>(N + 1);
            
ArrayList<Integer> list = new ArrayList<>(N + 1);
list.add(child, weight);
tree.add(parent, list);

언뜻 봐서는 정상적으로 동작할 것 같지만 list.add() 에서 IndexOutOfBoundsException이 발생한다. 왜 예외가 발생하는 것일까?

capacity와 size

ArrayList는 내부적으로 capacity와 size라는 변수를 두고 있닫. 용도는 다음과 같다.

• capacity - ArrayList에 담을 수 있는 최대 허용 개수를 나타낸다.
• size - 실제 ArrayList에 담겨있는 요소의 개수를 나타낸다.

 

ArrayList를 초기화할 때 인수로 넘겨주는 수는 capacity로 설정된다. 그리고 내부에서는 이 크기를 바탕으로 Object 배열을 생성한다.

 

capacity는 내부에서 배열의 크기를 관리하기 위해서 사용된다. 만약 요소가 계속 추가되어 size가 일정 이상 커지게 되면 내부적으로 더 큰 배열을 생성하고 기존 값을 복사한다.

add(int index, E element)

add(int index, E Element)를 사용하면 index에 element를 저장한다. 로직은 다음과 같다.

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
}

맨 처음에 범위를 체크하는 메서드를 호출하는데 이 코드를 보자.

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

index가 size보다 크거나 index가 0 이하인 경우 예외를 발생하도록 한다. 여기서 위에서 만났던 예외를 던지는 것이다.

위에서 ArrayList의 크기를 설정했다 생각하고 add(index, elem)을 사용할 수 있다고 생각했지만 내부에서는 정작 size를 사용하여 add가 가능한지를 판단한다. 왜 이렇게 체크하는 로직을 구성했을까?

Lazy

필자가 생각하기에 이렇게 로직을 구성한 이유는 Lazy 처리를 하기 위해서인 것 같다. 해당 인덱스에 직접 넣을 거라면 그냥 2차원 배열을 사용하도록 유도하고 ArrayList에선 요소를 넣음으로써 크기를 관리하기 위함인 것 같다. 만약 이를 capacity로 관리하게 되면 발생하는 상황을 생각해보자.

처음 capacity를 10으로 설정한 ArrayList를 생성했다. 그런데 개발자가 add(10, 10)으로 호출했다고 하자. 그렇다면 ArrayList에 접근한 인덱스가 관리하던 capacity의 일정 범위를 넘어섰기 때문에 내부에서 배열 크기를 늘리게 된다. 실질적으로 값은 arr[10] = 10에 해당하는 1개밖에 없지만 배열 크기는 불필요하게 커진다. 이러한 문제를 막기 위해 실제 요소가 들어있는 값인 size로 처리하는 것으로 판단된다.