[Java] ArrayList 동작원리

 

 

ArrayList 라는 자료구조는 코딩테스트에 워낙 많이 쓰이기 때문에 모든 자바 개발자들은 익숙한 자료구조일 것이다. 

 

ArrayList의 특징으로는 인덱스로 원소를 관리하고 원소를 빠르게 탐색할 수 있다. 

하지만 중간에 원소를 추가하거나 삭제하게되면 원소의 인덱스가 밀리거나 줄어들게 되어 성능적인 측면에서 안좋다. 

이 정도의 개념은 알테지만 내부적으로 어떻게 동작하는지 모르는 분들이 대부분일 것이다. 필자 또한 그렇다! 

 

배열과 arrayList 차이점은 아래 클릭!

 

1. 배열은 크기가 고정되어있지만 arrayList는 사이즈가 동적인 배열이다.

 

2. 배열은 primitive type(int, byte, char 등)과 object 모두를 담을 수 있지만, arrayList는 object element만 담을 수 있다.

 

3. 배열은 제네릭을 사용할 수 없지만, arrayList는 타입 안정성을 보장해주는 제네릭을 사용할 수 있다.

 

4. 길이에 대해 배열은 length 변수를 쓰고, arrayList는 size() 메서드를 써야한다.

 

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

 

그래서 오늘의 포스팅은  ArrayList 의 내부 동작 원리에 대해서 파헤져보려고 한다. 

즉, ArrayList 가 어떻게 동적으로 크기가 늘어나는지 분석해보자는 의미이다. 

 

---

상속

 

[ArrayList 의 상속관계]

java.lang.Object -> java.util.AbstractCollection<E> -> java.util.AbstractList<E> -> java.util.ArrayList<E>

 

ArrayList 의 최상위 부모 클래스는 Object이며 위의 순으로 확장된다. 

Object를 제외한 클래스들은 이름 앞에 Abstract으로 추상 클래스이다. 즉, 몇몇 메소드는 자식 클래스에서 구현해야한다. 

 

 

동작

 

ArrayList 자료구조를 선언할 때 아래와 같이 사용한다. 

ArrayList arrayList = new ArrayList<>();

 

여기서 알고 있어야하는 부분은 ArrayList 의 크기를 지정하지 않으면 기본 사이즈는 10이라는 것!

즉, ArrayList 에 inital size를 따로 명시하지 않았을 때 default size라는 뜻이다. 

 

그렇다면 ArrayList 생성 후에 크기가 10을 넘어가면 어떻게 되는 것일까? 

먼저 ArrayList 의 add 메소드를 한 번 파헤쳐보자. 

 

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) {
  
        if (s == elementData.length) {
            elementData = this.grow(); 
        }
        elementData[s] = e;
        this.size = s + 1; 
}

 

add 메소드가 실행되면 위와 같이 코드문이 보인다. 

두번째 파라미터는 오브젝트형 배열이며, 세번째 파라미터는 int형 정수(size)를 받고 있다. 

여기서 핵심은 " s == elementData.length " 조건문이다. 

즉, s(size) 와 elementData의 길이를 비교해서 배열의 사이즈를 조정해야하는 지 체크한다. 

만약 해당 조건문이 성립될 경우 this.grow() 메소드가 호출된다. 

 

 private Object[] grow() {
        // 현재 사이즈에서 + 1을 인자로 넘긴다.
        return this.grow(this.size + 1);
    }

    private Object[] grow(int minCapacity) {
        // 기존 elementData를 newCapacity 길이만큼 새로 할당한 배열에 복사한다.
        return this.elementData = Arrays.copyOf(this.elementData, this.newCapacity(minCapacity));
    }

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

 

    int newCapacity = oldCapacity + (oldCapacity >> 1);

 

여기서 핵심은 기존 용량 + 기존 용량/2 만큼 배열을 새로 생성한다는 것이다. 

즉, 현재의 배열보다 1.5배의 크기로 메모리를 할당 받아 기존의 배열의 원소들을 새로 할당받은 메모리 공간으로 복사하게 되는 것이다. 

 

특별한 조건이 아니면 위의 로직이 수행되고 나머지 로직들은 특정 바이트를 넘어갈 경우 어떠한 값으로 대체될 지 또는 어떠한 에러가 발생될지, 현재 arrayList가 비어있을 때 어떠한 값으로 저장될 지에 대한 로직들이다.

 

---

 

지금까지 ArrayList 의 동작원리에 대해서 살펴보았다.  

배열의 크기를 특정할 수 없을 때 현재의 배열이 꽉차게 되면 현재 배열의 크기보다 1.5배의 크기의 빈 배열을 할당하여 기존의 배열 원소들을 복사하기 때문에 동적으로 원소를 추가해줄 수 있다는 것을 알게되었다. 하지만 배열의 크기를 특정할 수 있을 때는 ArrayList 보다는 배열을 쓰는 것이 낫다라는 결과가 나온다.