ArrayList의 동적 배열 할당 원리 (Java)

ArrayList는 어떻게 동적으로 늘어날까요? LinkedList는 ArrayList 대비 add/delete가 빠르다는 장점이 있다고 알려져있습니다. ArrayList의 마지막 요소에 add 메서드를 실행하면 시간 복잡도가 O(1)이라고 알려져있는데, 정적 할당된 배열의 사이즈를 바꾸는 것은 새로운 정적 배열을 선언 후 복사해야하기 때문에 O(n)이 됩니다. 사실 요소를 하나하나 삽입할 때마다 배열을 재할당하면 연산량이 엄청나겠죠. 분명 내부적으로 리사이즈하는 주기를 별도로 두었을거라는 생각이 들었습니다.  자세히 살펴보기에 앞서, 먼저 Array와 ArrayList의 차이점을 알아봅시다.

Array와 ArrayList의 차이

---

• Array는 크기가 고정되어있는 정적배열, arrayList는 동적 배열이다.
• Array는 Object와 primitive를 다 담을 수 있지만, arrayList는 object만 담을 수 있다.
• Array는 제네릭을 사용할 수 없고, arrayList는 사용할 수 있다.
• Array는 길이에 대해 배열은 length 변수, arrayList는 size() 메서드를 사용한다.
• Array는 element를 할당(대입)하고, arrayList는 add()로 삽입한다.

여기서 중요한 점은, 배열은 length 변수로 나타내고, arrayList는 size()메서드로 사이즈를 반환한다는 것입니다. 즉, arrayList는 내부에 size의 필드를 별도로 두어 클라이언트에게 보여지는 size와 실제 배열의 length를 다르게 관리할 수 있다는 의미도 되겠네요. 여기서 힌트를 얻고, ArrayList를 직접 살펴보도록 하겠습니다.

동적으로 할당시키는 원리

---

ArrayList는 클라이언트에 보여주는 size와 내부 저장 array의 length를 다르게 가지고 있습니다. 예를 들면, 3개의 원소를 가지고 있는 ArrayList numbers가 있다고 가정해보겠습니다. numbers.size()를 호출하면 3이 클라이언트에게 반환되지만 실제로 생성자는 최소 Capacity인 10의 length 배열을 생성합니다. 그리고 size가 length와 같아질 때, (즉 배열이 꽉 찼을 때) 현재 Capacity + 1/2 현재 Capacity만큼의 새로운 배열을 생성하고 원래 원소를 복사해 옮깁니다. 이 때는 O(n)의 연산이 필요합니다.

즉, 끝에 원소를 추가하는 경우, capacity에 여유가 있는 경우 O(1), 여유가 없어 resize가 필요한 경우 O(n)의 시간복잡도를 갖습니다. 결론적으로 일부는 맞고 일부는 틀린 설명이 되겠네요.

코드를 보겠습니다. add 메서드를 호출하면 size와 내부 array의 length를 비교합니다. 같은 경우 grow 메서드를 호출해서 동적으로 용량을 키울 것입니다.

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

newCapacity는 (size + 1) + (size / 2)로 계산되는 것을 확인할 수 있습니다.

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