[Collection] ArrayList 특징 (add할 때의 내부동작)

• Overview
• ArrayList의 add 과정
• DEFAULT_CAPACITY를 넘겼을 때
• ArrayList는 copy의 문제를 가지고 있다.
• ArrayList는 어떻게 사용해야될까
• 정리

📌 Overview

ArrayList하면 코딩테스트나 실제 개발에 가장 많이 쓰이는 Collection Framework이지 않을까 생각합니다.그만큼 가장 기본적이면서도 아주아주 중요한 클래스이기 때문에 ArrayList의 내부 동작을 중점으로 특징을 한번 정리해보고자 합니다.

ArrayList에 대한 메서드나 어떤 클래스 계층구조를 가졌는지에 대해서는 잘 정리된 블로그 글들이 많기 때문에 이에 대한 설명은 줄이고 내부적으로 어떤 동작을 하는지에 초점을 맞추었습니다.

📌 ArrayList의 add 과정

public void makeArrayListObject() {
    List<String> list = new ArrayList<>();
 
    list.add("hello");
//...
}
 
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

우선 ArrayList new 생성자를 호출하면 생성자를 통해 빈 Array 객체를 elementData라는 Object 배열로 할당합니다. 빈 배열을 할당한다고 생각하면 됩니다.

이렇게 되면 빈 배열 하나가 할당돼있고 size는 0에 DEFAULT_CAPACITY는 10으로 설정된 ArrayList 객체가 생성이 됩니다.

여기에 add() 메소드를 통해 String 객체 하나를 넣으면 ArrayList 클래스 내부에 grow 메소드를 호출합니다.

private Object[] grow() {
    return grow(size + 1);
}
 
private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity));
}
 
private int newCapacity(int minCapacity) {
// overflow-conscious codeint oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
//...
        }
//...
}

위 코드 상에서 확인할 수 있듯이 grow에 기존의 size 값에서 1을 더한 값을 인자로 넣게됩니다.
(초기 생성자에 의해 처음 size는 0으로 설정)

newCapacity 메소드에서는 처음에는 elementData가 DEFAULTCAPACITY_EMPTY_ELEMENTDATA로 설정되었기에 DEFAULT_CAPACITY와 size 하나 증가한 값과 비교해서 큰 값으로 return하게 됩니다.

즉 처음에는 요소 한개를 add하면 Arrays.copyOf(elementData, newCapacity(minCapacity)); 이부분에서 10개의 저장공간을 가진 배열을 elementData 변수에 할당하게 됩니다.
(ArrayList size와 완전 별개입니다. 배열의 크기가 10개로 된 것뿐입니다.)

참고로 copyOf(A, capacity)에서 기존 A배열의 크기보다 더 큰 capacity 값을 설정하면 잉여공간에 해당 배열의 타입 default 값으로 설정됩니다.

int[] defaultInt = new int[10];// int type의 default 값인 0으로 10개 할당//...
 
Object[] defaultObj = {};
System.out.println(defaultObj.length);// length: 0
 
// 객체참조변수의 default 값인 null로 10개 할당
defaultObj = Arrays.copyOf(defaultObj, 10);
System.out.println(defaultObj.length); // length: 10

그리고 마지막에 size에 1을 더해주고 add 메소드 작업을 마무리합니다.

첫 요소를 ArrayList에 add했을 때 과정을 정리하면 다음과 같습니다.

• add 메소드 안에 grow 메소드를 호출
• newCapacity로 DEFAULT_CAPACITY 값인 10을 할당
• Arrays.copyOf를 통해 기존 elementData 배열을 newCapacity만큼 복사 후 다시 할당
• size 값 하나 증가

📌 DEFAULT_CAPACITY를 넘겼을 때

정확히는 ArrayList 안에 기존의 elementData의 길이와 size를 비교해서 같을 때 capacity를 더 늘려서 기존 객체를 복사하게 됩니다.이 때 newCapacity 메소드에서 capacity를 늘린 새로운 capa를 반환해줍니다.

private int newCapacity(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  int newCapacity = oldCapacity + (oldCapacity >> 1);
 
  //...
 
  return (newCapacity - MAX_ARRAY_SIZE <= 0)
  ? newCapacity
  : hugeCapacity(minCapacity);
}
 
/**
* The maximum size of array to allocate (unless necessary).
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

MAX_ARRAY_SIZE와 비교를 해서 새로운 capa를 return해주는데 Integer의 끝값(2^31 - 1)을 기준으로 하네요.

이렇게 해서 새로 할당받은 newCapacity를 적용한 새로운 Object Array에 기존 elementData안에 있는 데이터들을 복사해서 다시 할당을 해주게 됩니다.

📌 ArrayList는 copy의 문제를 가지고 있다.

크기를 확장할 때 전체 요소의 복사

기존 Array에서는 객체를 생성할 때 미리 크기를 설정해야 합니다. 이는 개발 과정에 있어서 유연성을 저해하는 요소이기도 합니다. 요구사항이 계속 바뀌고 In/Out Data가 가변적인 상황에서는 더욱이 Array를 적용하기가 어려워 보입니다. ArrayList는 이를 해결해준다고 할 수 있습니다.

User[] userArr = new User[10];// 10개까지 밖에 데이터를 넣을 수 없다.
 
List<User> userList = ArrayList<>();
userList.add(new User(...));// 계속 add할 수 있다.//...

하지만 여기서 ArrayList의 단점이 나옵니다. 바로 성능을 상당히 저해하는 Array Copy입니다.위에서 언급했듯이 ArrayList는 add할 때 capacity를 넘겨버리는 요청이 들어오면 capa를 더 늘려서 새로운 배열에다가 기존 데이터들을 싹 다 복사하는 방식으로 이루어집니다.

return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity));

Arrays.copyOf는 내부적으로 System.arraycopy로 동작하는데 해당 복사작업은 아래와 같이 이루어집니다.

// persons[0]에서부터 4개를 persons[1]부터 복사하겠다.
// index    0    1    2    3    4    ...
// data1    p1    p2    p3    p4    p5    ...
// data2    p1    p1    p2    p3    p4    ...
System.arraycopy(persons, 0, persons, 1, 4);
 
// ArrayList내의 Arrays.copyOf 작동방식
System.arraycopy(original, 0, copy, 0, length);

즉, original 원본데이터들을 copy에 전부 집어넣는 작업을 진행합니다. ArrayList에서의 add 작업의 시간복잡도는 O(n)이라고 할 수 있습니다. 요소를 하나 넣을 때마다 평균 O(n)의 시간 비용이 발생한다는 것이고 애플리케이션 성능에 상당한 영향을 주는 요소라고 할 수 있습니다.

새로운 객체의 생성

Arrays copy를 진행할 때 새로운 배열 객체를 생성하게 되는데 새로운 객체를 생성할 때도 비용이 발생하긴 하지만 성능에 큰 영향을 줄 수 있는 기존 객체의 처리 문제가 있습니다.

기존 배열을 새로운 배열에 copy를 하고 나면 쓸모가 없어지게 되는데 쓸모가 없어진다는 것은 JVM 환경에서 객체 참조를 잃게 된다는 것입니다. 이것은 곧 GC에게 좋은 먹잇감이 된다는 뜻입니다.

GC는 객체 참조를 잃은 객체를 찾아서 삭제 처리를 해주는 좋은 도구이지만 GC가 작동할 때 GC외 나머지 쓰레드의 모든 작업이 멈추게 됩니다. (stop-the-world). (stop-the-world)

ArrayList를 사용하게 되면 비효율적인 처리과정과 불필요한 GC의 호출이 발생하기 때문에 잘 사용하는 것이 중요합니다.

📌 ArrayList는 어떻게 사용해야될까

• 처리하는 데이터의 크기가 어느정도 정해져 있는 구간에 사용
• ArrayList 객체 생성시 어느정도 여유공간을 두고 사이즈를 정해서 생성
• LinkedList 등 다른 Collection Framework 대체제의 활용 가능성 생각해보기
• Random Access가 필요한 작업과정에서 사용할 것
• 차례대로 add하거나 뒤에서부터 remove하는 경우는 괜찮을 수 있다. (크기가 정해져 있을 때)

위와 같은 상황에서 ArrayList를 사용해보면 좋을 것 같다고 생각이 드는데 이것 외에도 또 활용방안이나 대체방안이 있을 것 같네요. 이 부분에 대해서는 저도 한 번 찾아봐야겠습니다 ㅎㅎ

크기가 정해져 있는 상황에서 차례대로 add하거나 뒤에서부터 remove하는 것은 모든 요소를 copy하지 않으면서 작업이 이루어지기 때문에 LinkedList보다 괜찮은 성능을 보일 수 있습니다.

중요한 것은 ArrayList에서 모든 element를 copy하게 만드는 어떠한 상황을 만들지 않는 것이라고 생각합니다.

📌 정리

• ArrayList는 Array와 다르게 크기를 정하지 않고도 객체를 생성해서 사용가능
• ArrayList의 newCapacity의 동작을 잘 살펴보자.
• capa를 넘어버리는 add 요청이 들어왔을 때 모든 요소의 copy를 주의하자. (add시 O(n) 시간복잡도 발생)
• ArrayList, LinkedList를 적절히 활용해보면 좋을 것 같다.

LinkedList와 ArrayList의 비교에 대해서도 추후에 정리해볼까 합니다 :)

틀린 내용이 있을 수 있습니다. 이에 대한 코멘트 언제나 환영입니다!