[Java] ArrayList에 데이터를 추가할 때 add는 어떻게 동작할까?

평소에 ArrayList를 자주 사용하지만 데이터를 추가했을 때 어떤 방식으로 공간이 더 늘어나는지 갑자기 궁금해졌다.

그래서 오늘은 ArrayList의 add를 호출했을 때 일어나는 동작을 정리해보려 한다.

 

출처:https://www.testingdocs.com/questions/what-is-an-arraylist/

List<String> arrayList = new ArrayList<>();
arrayList.add("A");

....

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

ArrayList를 생성하면 elementData라는 필드에 빈 배열을 할당한다.

이 때 size는 0이고 DEFAULT_CAPACITY는 10으로 설정된다.

---

 

add()를 사용하면 아래의 코드가 호출된다.

• modCount : 해당 ArrayList가 수정된 횟수이다. 
• size : ArrayList의 내부 필드로서 ArrayList의 현재 사이즈를 나타낸다.

내부적으로 add()를 한 번 더 호출하는데 아래의 코드이다. 

• E e
  • 추가하고자 하는 데이터 객체
• Object[] elementData 
  • 실질적으로 ArrayList에 추가되는 인스턴스가 저장되는 배열
  • capacity를 설정하지않으면 기본사이즈는 10으로 설정된다.
• int s : 현재 ArrayList의 사이즈

---

"데이터를 추가하기에 충분한 공간이 있다면?"

• 현재 배열에서 인덱스 s에 데이터를 넣고 사이즈를 1 증가시키는 방식으로 add()메서드는 동작한다.

"데이터를 추가하기에 공간이 부족하다면?"

• grow()라는 메서드를 호출하고 이 결과값을 elementData가 참조하도록 하고 있다. 

grow()메서드를 호출하면 내부의 다른 grow() 또 호출하고 있는데 이 때 매개변수로 "size(현재사이즈) + 1"을 넘기고 있다.

 

실질적으로 호출되는 grow(int minCapacity)이다.

"첫 데이터를 추가한다고 가정하면?"

첫 데이터를 add한다고 가정하면 size는 0이고 DEFAULT_CAPACITY는 10일 것이다.

즉, 현재 size가 0이고 elementData는 비어있기에 oldCapacity 또한 0일 것이고 if-else 문에서 else로 들어가서 

DEFAULT_CAPACITY 크기(10)만큼의 배열이 생성되어 elementData가 참조하게 한다.

 

"데이터를 추가하려하는데 공간이 부족하다면?"

그렇게 DEFAULT_CAPACITY 만큼 데이터를 넣고 나면 grow() 메서드의 if절 내부로 들어가는데 newLength 메서드를 통해 새로운 capacity를 구하게 된다.

newCapacity(새 용량)는 위 코드를 통해 구해지는데 "oldCapacity(현재 사이즈)"와 "minCapacity(size+1)-oldCapacity" 중 큰 값을 구하고 "oldCapacity/2" 한 값을 더하는 방식으로 새로운 capacity를 구했다.

 

즉, ArrayList의 크기는 현재 사이즈의 절반 사이즈만큼 공간이 확장되는 것을 확인할 수 있다.

 

이렇게 새로운 capacity가 구해지면 Arrays.copyOf(Object[], capacity)가 호출되서 내부에 capacity 만큼의 배열이 생성되고 이전의 요소가 복사되어 저장되는 방식으로 ArrayList의 공간이 가변적으로 변한다.

---

ArrayList의 Copy 때문에 발생하는 성능문제

위의 코드를 봤을 때 ArrayList는 공간이 가변적이기 때문에 Array보다는 더욱 유연하게 사용할 수 있다는 장점이 있다.

하지만 이러한 장점이 곧 단점이 될 수도 있다.

 

위에서 봤듯이 ArrayList는 add할 때 현재 elementData의 크기를 넘어설 경우 더 큰 크기의 공간이 할당되고 해당공간에 현재 데이터를 모두 복사하는 방식으로 동작한다.

Arrays.copyOf()는 내부에서 System.arrayCopy() 메서드를 호출한다.

System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

• src : 복사할 원래 배열
• srcPos : 복사를 시작할 위치
• dest : 복사본을 저장할 대상 배열
• destPos : 복사본의 시작 위치
• length : 복사할 요소 수

System.arraycopy()에서 매개변수를 전달할 때 srcPos가 0이고, length가 Math.min(original.length, newLength)인 것을 확인할 수 있는데 이는 데이터를 처음부터 끝까지 복사한다는 의미인 것이다.

 

즉, ArrayList에서 데이터를 add()할 때 현재 capacity를 넘어섰다면 이 때 시간복잡도는 O(n)이 되는 것이고 프로그램 성능에 영향을 끼칠 수 있다.

---

그럼 언제 사용할까?

• 데이터의 추가/삭제가 빈번하지 않은 경우
  • 내부적으로는 배열을 사용하기에 데이터를 순차삽입/삭제를 하지 않는다면 성능에 영향을 끼칠 수 있다.
  • 순차삽입/삭제의 경우는 괜찮은거 같다. 단, copy가 이뤄지지 않는다면
• 데이터의 크기를 예측할 수 있는 경우
  • ArrayList를 생성할 때 초기 capacity를 설정할 수 있으므로 데이터의 크기를 예측할 수 있는 경우 더욱 효율적으로 사용할 수 있다.
• 단일 쓰레드 환경
  • 이번 글에서 설명하진 않았지만 ArrayList는 Thread-Safe하지 않기에 단일 쓰레드 환경에서 적합하다.