ArrayList는 어떻게 크기가 조절될까?

ArrayList는 Java에서 List 인터페이스를 구현한 인기 있는 데이터 구조이다. 이번 글에서는 동적으로 크기가 조절되는 배열을 제공하는 ArrayList의 내부 저장 방식과 성능에 대해 살펴보려고 한다.

 

 

 

 

 

ArrayList의 초기화 과정

ArrayList를 생성할 때, 기본적으로 빈 배열을 사용하여 초기화된다.

 

기본 용량은 일반적으로 10이며 처음에는 빈 배열이 할당된다. 

+) 리스트의 size가 10이 아님!

 

 

 

 

 

add 메서드 작동 방식

add(E e) - 끝에 요소 추가

위 사진은 ArrayList의 리스트 끝에 요소를 추가하는 add 메서드 내부 코드이다.

 

코드를 하나하나 살펴보자.

• modCount++ : 리스트가 수정될 때마다 증가하는 값이다. 이 값은 여러 스레드에서 ArrayList를 사용할 때 동기화 문제를 방지하거나, 반복 중 리스트 변경을 감지하기 위해 사용된다.
• add(E e) 메서드는 add(e, elementData, size)를 호출해서 내부 배열(elementData)의 크기와 빈 공간을 확인한 후, 요소를 추가한다.
• 만약 현재 배열의 크기가 가득 차면, grow() 메서드를 호출해 배열 크기를 1.5배 늘리고, 기존 배열의 요소들을 새로운 배열로 복사한다.
• 배열에 요소를 추가한 후, 리스트 크기도 증가시킨다.

 

 

 

add(int index, E element) - 특정 위치에 요소 삽입

이번에는 특정 인덱스에 요소를 삽입하는 메서드를 보겠다. 기존의 요소들은 오른쪽으로 이동해 자리를 마련하게 된다. 이것도 코드를 하나하나 살펴보겠다.

 

• rangeCheckForAdd 메서드는 주어진 인덱스가 유효한지 확인한다. 만약 범위를 벗어나면 IndexOutOfBoundsException이 발생한다. (자주 봤던 예외!)
• 배열이 가득 차면 역시 grow() 메서드를 호출해 배열의 크기를 1.5배 늘리고, 새로운 배열로 교체한다.
• 새로운 요소를 삽입할 위치를 만들기 위해, 기존의 요소들을 오른쪽으로 한 칸씩 이동시킨다. 이 과정에서 System.arrayCopy() 메서드를 사용해 빠르게 요소를 복사한다.
• 지정된 인덱스에 새로운 요소를 삽입한 후, 리스트 크기를 증가시킨다.

 

 

 

grow() - 배열 크기 증가

두 add 메서드 모두 배열의 크기가 가득 차면 배열을 늘리는 작업을 수행한다. 이때 사용되는 grow() 메서드를 좀 더 자세히 보겠다.

• grow() 메서드는 현재 배열 크기를 확인하고, 크기를 1.5배 늘린다.
• 새로운 배열을 생성한 후, 기존 배열의 요소들을 새로운 배열로 복사한다.
• 배열이 동적으로 크기가 늘어나기 때문에 ArrayList는 요소를 계속 추가할 수 있지만, 배열이 늘어날 때마다 복사 작업이 발생하면서 성능에 영향을 줄 수 있다.

 

 

 

ArrayList의 성능 문제 및 고려사항

ArrayList는 동적으로 크기가 조절되는 배열을 제공하여 데이터의 크기가 가변적인 상황에서도 유연하게 사용할 수 있는 장점을 가지고 있다. 하지만 ArrayList의 내부 구조와 동작 방식으로 인해 성능 문제가 유발될 수 있다. 아래에서 문제점과 이를 잘 활용하기 위한 고려사항을 정리하려고 한다.

1. 배열 복사의 문제

• 크기 확장 시 성능 저하: ArrayList는 배열의 크기가 가득 찼을 때, 새로운 배열을 생성하고 기존 배열의 데이터를 모두 복사한다. 이 과정에서 Arrays.copyOf 메서드를 사용하고, 내부적으로 System.arraycopy가 호출된다. 이 복사 작업은 시간 복잡도가 O(n)이다. 따라서 요소를 추가할 때마다 평균적으로 O(n)의 시간 비용이 발생하여 성능에 상당한 영향을 미칠 수 있다. 
• 새 배열 객체의 생성: 배열을 확장할 때 새로운 배열 객체를 생성하는데, 이 과정에서도 성능 비용이 발생한다. 생성된 새로운 배열은 기존 배열의 참조를 잃게 되며, 이로 인해 가비지 컬렉터(GC)의 대상이 된다. GC가 작동할 때, 모든 다른 스레드의 작업이 멈추는 stop-the-world 이벤트가 발생하여 성능에 영향을 줄 수 있다. 자세한 건 2번에서 더 설명하겠다. GC가 뭘까? GC 자세히 살펴보기

2. 새로운 객체의 생성과 GC 문제

• GC의 작동: 새로운 배열 객체가 생성되면 기존 배열은 더 이상 사용되지 않게 되며, GC가 이를 수집한다. GC는 메모리 관리에 중요한 역할을 하지만, GC가 작동할 때 애플리케이션의 다른 스레드가 멈추는 stop-the-world 현상이 발생하여 애플리케이션의 전반적인 성능에 영향을 미칠 수 있다.

3. 효과적인 사용 방법

• 초기 용량 설정: ArrayList를 생성할 때 적절한 초기 용량을 설정하여 배열의 크기를 자주 변경하지 않도록 한다. 이렇게 하면 배열 복사 작업과 GC 호출을 줄일 수 있다.
• 대체 데이터 구조 고려: ArrayList가 자주 크기가 변경되는 경우에는 성능 문제가 발생할 수 있으므로, LinkedList와 같은 다른 데이터 구조를 고려할 수 있다. 
• 리스트 크기 조절: 데이터의 크기가 크게 변하지 않는 경우에는 ArrayList가 매우 효율적이다. 하지만 크기가 자주 변하는 경우에는 성능 저하를 피하기 위해 리스트의 크기를 신중하게 조절하는 것이 중요하다.

 

 

 

 

결론

ArrayList는 유연하게 크기를 조절할 수 있는 장점이 있지만, 배열 크기 확장 시 전체 요소를 복사하는 과정에서 성능 문제를 일으킬 수 있다. 이러한 문제를 최소화하기 위해 적절한 초기 용량 설정과 데이터 구조의 선택이 필요하며, 배열의 크기 조절과 GC 문제를 염두에 두고 사용해야 한다.