[JAVA] ArrayList는 크기가 어떻게 변할까?

Array(배열)와 ArrayList는 프로그래밍에서 자주 사용되는 데이터 구조로, 각각 고유한 특성을 가지고 있습니다.

Array(배열)

배열은 고정된 크기를 가지며, 한 번 생성되면 그 크기를 변경할 수 없습니다.
예를 들어, 5개의 요소를 저장할 수 있는 배열을 생성하면, 그 배열은 항상 5개의 요소만 저장할 수 있습니다.
배열에 더 많은 요소를 추가하려고 하면, 배열의 크기가 고정되어 있기 때문에 오류가 발생합니다.

ArrayList

Java에서 ArrayList는 배열을 기반으로 하지만, 그 크기가 동적으로 변할 수 있습니다.

 

즉, ArrayList에 요소를 추가하거나 제거하면, 내부적으로 배열의 크기가 자동으로 조절됩니다.

이는 프로그래머가 배열의 크기 관리에 신경 쓸 필요 없이 요소를 추가하거나 제거할 수 있게 해 줍니다.

 

예를 들어, 5개의 요소를 저장할 수 있는 배열에 11번째 요소를 추가하려고 시도하면 어떻게 될까요?

 

고정된 크기의 배열에서는 이러한 시도가 오류를 발생시키지만, ArrayList에서는 자동으로 배열의 크기가 조정되어 요소가 추가됩니다.

public class Array {
    public static void main(String[] args) {
        String[] arr = new String[5];
        for (int i = 0; i < 6; i++) {
            arr[i] = String.valueOf(i);
        }
    }
}

결과
: Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5

 

ArrayIndexOutOfBoundsException 예외가 발생하는 것을 확인 할 수있습니다.

배열의 공간이 5까지 밖에 없는데 6번째에 요소를 넣으려고 하니까 발생하는 오류입니다.

 

기존의 배열의 크기를 벗어나게 요소를 추가하려는 경우에는 더 큰 배열을 만들어서 기존의 배열을 복사하는 방법 밖에 없습니다.

 

따라서 동적으로 데이터를 다뤄야 할때는 배열이 아닌 ArrayList를 사용하는게 좋습니다.

 

그러면 ArrayList는 어떻게 내부적으로 배열의 크기가 조절될까요?

ArrayList를 생성하고 ArrayList의 add메소드를 호출하여 배열의 크기가 어떻게 변화하는지 확인해보겠습니다.

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>(); // 처음에 생성할때 는 elementData.length가 0
        for (int i = 0; i < 100; i++) {
            arrayList.add(String.valueOf(i)); // 첫번째 add에서 elemetData.lenth가 10
        }
        System.out.println(arrayList.size());
    }
}

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

ArrayList를 생성합니다.

 

ArrayList는 배열의 크기를 매개변수로 넘겨 생성할 수도 있지만 여기에서는 그냥 기본 생성자로 생성을 하였습니다.

 

기본 생성자로 생성을 하면 arrayList의 내부 배열은 크기는 참조변수로 힙 영역에 참조주소값만 형성한 상태이기 때문에 0 입니다.

 

여기서 첫번째 루프의 add() 메서드를 호출합니다.

public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
}

 

첫번째 add() 메소드에서 add(e, elemetData, size)를 호출합니다.

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

arrayList에는 아무런 값이 없기 때문에 elementData.length(배열의 크기)와 s(size) 모두 0 으로 동일합니다.

 

사이즈와 배열의 크기가 같으니 배열의 크기를 늘려줘야 새로운 요소를 add 할 수 있습니다.
따라서 grow() 메소드를 호출하여 배열의 크기를 늘려줘야 합니다.

    private Object[] grow() {
        return grow(size + 1);
    }

    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)];
        }
    }

 

코드가 갑자기 길어져서 당황스럽겠지만 하나씩 차근차근 확인해보겠습니다.
일단 oldCapacity와 현재 배열의 길이를 확인합니다.

 

만약 arrayList에 add가 한번도 호출 된 적이 없으면 배열 크기는 10(DEFAULT_CAPACITY)과 1(minCapacity, size+1) 중 큰 값으로 정해집니다.

ArrayList를 기본생성자로 생성하고 최초로 add를 했을때 ArrayList 내부 배열의 크기는 10 입니다!

그러면 11번째 요소를 추가하고 싶습니다. 어떻게 해야 할까요?

 

배열에서는 앞서 본것과 같이 ArrayIndexOutOfBoundsException 오류가 발생합니다.

 

ArrayList는 어떻까요?

위의 grow() 메서드를 다시 확인 해 보겠습니다.

    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity,
                    oldCapacity >> 1          
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

코드의 네번째 줄을 확인해보면 새로운 배열크기를 지정해 줘야 한다는 것을 확인할 수있습니다.

    public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
        if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
            return prefLength;
        } else {
            return hugeLength(oldLength, minGrowth);
        }
    }

해당 값을 대입해 보면 prefLength의 값은 15입니다.

 

그러면 다시 이전 코드로 돌아가서 Arrays.copyOf(elementData, newCapacity)로 새로운 배열을 생성하고

기존의 배열에 있는 요소들을 복사하는 것을 확인할 수 있습니다.

 

따라서 elementData.length는 15 입니다.

 

즉, 요소가 하나씩 추가 될 경우 새로운 배열의 길이는 기존길이 + 기존길이의 절반(정수, 소수점 버림) 입니다.

 

여기서 동적으로 배열의 길이를 정하는 곳은 아래의 코드입니다.
int prefLength = oldLength + Math.max(minGrowth, prefGrowth);

 

add의 경우 요소를 하나씩 추가 하기 때문에 Math.max(minGrowth, prefGrowth)의 값은 항상 prefGrowth일 수 밖에 없습니다.
minGrowth가 Max값인 경우는 addAll 같이 한번에 많은 값을 추가하는 경우입니다.

    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        modCount++;
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Object[] elementData;
        final int s;
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);
        System.arraycopy(a, 0, elementData, s, numNew);
        size = s + numNew;
        return true;
    }

 

이 경우에는 grow()의 매개변수로 s(현재 배열안의 요소수) + numNew(새로 추가할 요소들의 길이)입니다.