[Java] array(배열)과 arrayList(리스트)의 차이(arrayList는 어떻게 동적으로 늘어나는가?)

array(배열)과 arrayList(리스트)의 차이

arrayList는 사이즈가 동적으로 알아서 늘어나주니 찾아볼 생각을 못하다가 어떻게 내부적으로 size가 늘어나는지 코드를 분석해봤다.

 

일단 기본적인 차이부터 살펴보자

 

1. Implementation of array is simple fixed sized array but Implementation of ArrayList is dynamic sized array.
배열은 크기가 고정되어있지만 arrayList는 사이즈가 동적인 배열이다.

 

2. Array can contain both primitives and objects but ArrayList can contain only object elements
배열은 primitive type(int, byte, char 등)과 object 모두를 담을 수 있지만, arrayList는 object element만 담을 수 있다.

 

3. You can’t use generics along with array but ArrayList allows us to use generics to ensure type safety.
배열은 제네릭을 사용할 수 없지만, arrayList는 타입 안정성을 보장해주는 제네릭을 사용할 수 있다.

 

4. You can use length variable to calculate length of an array but size() method to calculate size of ArrayList.
길이에 대해 배열은 length 변수를 쓰고, arrayList는 size() 메서드를 써야한다.

 

5. Array use assignment operator to store elements but ArrayList use add() to insert elements.
배열은 element들을 할당하기 위해 assignment(할당) 연산자를 써야하고, arrayList는 add() 메서드를 통해 element를 삽입한다.

 

출처: [QUORA] What is the difference between an array and an array list?

 

arrayList는 어떻게 동적으로 사이즈가 늘어나는가?

단순하게 접근했다. 사이즈가 늘어나는 것에 관여하려면 element를 추가할 때 무엇인가 벌어지지 않을까? 라는 생각으로 arrayList의 add()를 살펴보았다.

 

아래는 java에서 ArrayList 클래스이다. 순서대로 볼 수 있도록 메서드 순서만 재배치했다.

    // jdk 11을 까보긴 했는데, 다른 java 버전이라도 원리는 유사할 것이다.

    public boolean add(E e) {
        ++this.modCount; // 구조적으로 변경된 횟수를 카운트함 (이 포스팅에서는 크게 신경 안써도 됨)
        this.add(e, this.elementData, this.size);
        return true;
    }

    private void add(E e, Object[] elementData, int s) {
        // arrayList의 size 변수와 element들을 담고 있는 배열의 길이가 같으면 아래의 if문을 타게 된다. 
        if (s == elementData.length) {
            elementData = this.grow(); // 이 부분이 배열의 크기를 동적으로 늘어나게 해줄 거라는 느낌이 든다. 
        }

        elementData[s] = e;
        this.size = s + 1; // 클라이언트에서 보여질 arrayList의 사이즈를 늘린다. arrayList에서 size() 메서드를 사용하면 해당 변수를 반환한다. 
    }

 

배열의 크기를 늘려줄 것 같은 grow() 메서드를 타고 들어가보자.

    private Object[] grow() {
        // minCapacity(최소 용량)로 현재 사이즈에서 + 1을 인자로 넣어준다.
        return this.grow(this.size + 1);
    }

    private Object[] grow(int minCapacity) {
        // 여기서 기존의 elementData(클라이언트는 arrayList를 사용한다면 이 배열을 사용할 것이다)를 newCapacity 길이만큼 새로 늘어난 배열에 카피한다.
        return this.elementData = Arrays.copyOf(this.elementData, this.newCapacity(minCapacity));
    }

    // arrayList의 새로운 용량을 정한다.
    private int newCapacity(int minCapacity) {
        int oldCapacity = this.elementData.length;
        // 기존 용량 + 기존 용량/2 (우측 시프트 연산)
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (this.elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // arrayList가 비어있을 때
                return Math.max(10, minCapacity);
            } else if (minCapacity < 0) {
                throw new OutOfMemoryError();
            } else {
                return minCapacity;
            }
        } else {
            // 새로운 용량이 기존 용량의 +1 된 사이즈보다 크면 아래의 로직을 수행한다. 
            return newCapacity - 2147483639 <= 0 ? newCapacity : hugeCapacity(minCapacity);
        }
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) {
            throw new OutOfMemoryError();
        } else {
            // 2147483639 byte를 넘어갈 경우, int의 최대치를 용량으로 부여하고 int의 범위를 넘어서면 outOfMemory 발생
            return minCapacity > 2147483639 ? 2147483647 : 2147483639;
        }
    }

 

 

그림)  size가 6인 arrayList에 새로운 element 4를 추가하고자 한다. 그럼 내부동작은 이렇게 되는 것이다.

 

 

 

 

 

결론적으로는 element를 add하려고 할 때, capacity가 elementData(배열)의 길이와 같아지면 일반적인 상황에서 기존의 용량 + 기존 용량/2 만큼 크기가 늘어난 배열에 기존 elementData를 copy한다.

 

이런 원리로 arrayList가 동적으로 크기가 늘어날 수 있는 것이다.

---

 

grow() 메서드로 용량을 늘린 뒤, 추가하려는 element를 할당하면 클라이언트 입장에서는 자동으로 사이즈를 늘려주면서 element가 추가된 것으로 보인다.

 

실제로는 가지고 있던 용량이 꽉 찼을 때, 용량이 기존의 1.5배를 늘린 새로운 배열에 기존 배열을 copy하는 것이다.