[Java] ArrayList.java (add 메서드 내부 동작)

ArrayList가 가변배열이라는 건 알겠는데 한 번 늘 때 얼마나 늘어날까? 궁금해서 알아보았습니다.

ArrayList

평소 알고리즘을 풀거나 비즈니스 로직을 개발하다보면 List 인터페이스를 구현한 ArrayList 혹은 LinkedList 클래스를 사용할 때가 많았습니다.

오늘은 문득 ArrayList.add() 라는 메서드를 수행하면 내부적으로 어떤 일들이 일어나는지, 배열 길이를 넘는 데이터를 저장할 때 어떤식으로 가변 동작이 일어나는지 궁금해서 클래스 내부를 한번 들여다보았고 한번 정리해보았습니다.

 

---

ArrayList Concept

순서가 있는 데이터의 집합으로 ArrayList는 내부적으로 배열을 사용하여 데이터를 연속적으로 저장합니다.

또한 내부가 배열로 이루어져있다보니 길이를 넘어서는 데이터가 들어올 경우 C++의 동적배열(malloc)처럼 가변적으로 크기를 재할당하여 데이터를 저장하는 방식으로 이루어져있습니다.

배열 특성 상 중간 위치에 데이터를 추가하거나 삭제할 경우 해당 위치를 기반으로 뒷 요소들을 밀어야하기에 최악 경우 O(N)시간이 소요됩니다.

ArrayList는 요소의 순서가 있어, 인덱스를 통해 접근할 수 있습니다. 이는 조회 성능이 O(1)의 시간복잡도가 소요된다는 걸 알 수 있습니다.

 

---

ArrayList.add() !

ArrayList.java

ArrayList는 내부적으로 배열로 선언이 되어 있습니다.

 

다음은 ArrayList의 생성자로 매개변수로 초기 배열의 크기를 받거나 매개변수없는 생성자를 통해 생성할 시 다음과 같은 default길이로 배열이 생성됩니다.

DEFAULT_CAPACITY

 

add함수를 보면 modCount라는 변수를 1증가시키며, 3개의 매개변수를 받는 add메서드를 다시 호출합니다.

modCount는 AbstractList를 상속받은 변수로 iterator, listiterator 메서드에서 반복 구현에 사용되는 변수입니다.

 

해당 메서드는 삽입하려는 요소(e)와 데이터를 저장하고 있는 배열(elementData), 현재 배열의 길이(s)를 매개변수로 받습니다.

 

핵심로직으로는 요소를 추가하기 전 데이터의 개수가 배열의 길이와 같다면 데이터를 넣을 공간이 부족하기에 배열의 길이를 증가시키는 grow() 메서드를 호출합니다.

 

grow() 메서드의 핵심 로직으로는 Arrays.copyOf로

기존 배열의 데이터를 newCapacity()메서드를 통해 생성되는 새로운 배열에 복사합니다.

minCapacity는 상위메서드의 매개변수로 size+1의 값입니다.

 

복사하는 부분으로 인해 ArrayList는 LinkedList에 비해 데이터의 추가 및 삭제 시간복잡도가 안좋은 것 같네요.

 

가변 배열 핵심 로직

다음으로는 newCapacity 메서드의 핵심로직입니다.

newCapacity 변수는 기존 배열 크기 + 기존 배열 크기 / 2 (shift연산)이라는 새로운 값으로 설정됩니다.

 

예로 원래 배열의 길이가 10이였다면 새로운 배열의 길이(newCapacity) = 10 + (10/2) = 15가 됩니다.

15일 경우 최종적으로 하단 return문을 거치게 되고 참이므로 15를 return 하게 됩니다.

 

중간 로직의 경우 배열의 길이를 증가하는 과정에서 발생할 수 있는 Overflow같은 예외를 처리하는 구문입니다.

 

호출한 메서드를 따라 다시 grow 메서드에 도달하게 되면 elementData라는 배열은 길이 15의 배열로 기존 배열의 데이터를 복사하게 된 새로운 배열이 됩니다.

 

 

최종적으로 호출한 메서드로 돌아가게 되고 다음 index에 데이터 e가 삽입되고 size를 1 늘려줌으로써 add() 메서드가 종료됩니다.

 

---

정리

알고리즘 풀이를 하다 문득 궁금해진 ArrayList는 어떤식으로 가변배열을 형성할까 하는  궁금증으로 ArrayList.java 클래스 파일을 적잖이 바라보고 있었습니다.

평소 아무 생각없이 지원하는 메서드들을 사용하다 내부적으로 어떻게 구현이 되어있는지 보는 건 생각보다 늘 유익한 것 같아요.

여유로울 때 add를 제외한 나머지 remove, equals 등의 메서드도 한번 찾아보면 재미있을 것 같아요!