[Java 파헤쳐보기] Java에서 ArrayList가 어떻게 구현되어 있을까?

지난 포스팅에서 JCF를 다루었습니다. 이번 포스팅에서는 JCF의 ArrayList에 대해 살펴보겠습니다.

 

ArrayList와 LinkedList 차이

우선, ArrayList와 LinkedList의 개념적인 차이를 통해 ArrayList를 살펴보겠습니다.

 

ArrayList

출처 : https://suyeon96.tistory.com/27

ArrayList는 데이터들이 쭉 늘어선 배열의 형식입니다.

 

 ArrayList는 데이터의 인덱스를 가지고 있어서, 탐색(시간 복잡도: O(1))이 매우 용이하지만 데이터의 삽입과 삭제에서는 인덱스들의 위치를 조절해주어야 하기 때문에 O(n)의 시간 복잡도를 가집니다.

 

 

LinkedList

출처 : https://suyeon96.tistory.com/27

 반면, LinkedList는 자료의 주소값으로 서로 연결되어있는 구조입니다. 내부적으로 양방향의 연결리스트로 구현되어있습니다.

 

탐색 시에 순차적으로 접근하기 때문에 탐색의 속도가 느리다는 단점이 있습니다. (시간 복잡도 O(n))

하지만, 데이터의 삽입과 삭제 시에는 가리키는 주소 값만 변경해주면 되기 때문에 ArrayList에 비해 매우 빠릅니다. 

 

※ 물론 순차적인 추가/삭제 시에는 ArrayList가 LinkedList보다 조금 빠를 수 있습니다. 처음과 마지막만 삭제한다면 요소의 재배치가 필요하지 않기 때문입니다.

 

JCF에서의 ArrayList와 LinkedList의 차이

JCF 계층 구조에서 ArrayList와 LinkedList는 아래와 같습니다.

 

우선 ArrayList와 LinkedList는 모두 List 인터페이스에 속한 클래스입니다. 

 

출처: https://www.java-forums.org

 

 하지만 JCF 계층 구조를 조금 더 자세히 들여다 보면, ArrayList는 List 인터페이스를 구현한 AbstractList를 상속받고, LinkedList는 AbstractList 인터페이스를 구현한 AbstractSequentialList를 상속하고 있는 것을 알 수 있습니다. 

 

그리고 이것은 실제 자바 코드에서도 확인할 수 있습니다.

 

 AbstractList 는 리스트 구현을 위한 기본적인 기능( get, set 등의 메서드) 을 제공하는 반면, AbstractSequentialList 클래스는 순차적인 엑세스를 가진 리스트를 구현하는 데 특화되어 있습니다.

 

 

 

 

ArrayList의 add 메서드를 통해 내부 구조 살펴보기

 위와 같은 특성을 가진 ArrayList가 자바에서 내부적으로 어떻게 구현되었는지 궁금해졌습니다. 이번 포스팅에서는 ArrayList를 살펴보고, 다음 포스팅에서 LinkedList에 대해 살펴볼 것입니다.

 

ArrayList는 인덱스로 객체를 관리하는 점에서 배열과 동일하지만, 크기를 동적으로 늘릴 수 있다는 것에서 차이점이 있습니다.

동적으로 배열을 늘린다는 것에서 배열 외에 다른 자료 구조라도 사용하는 것 같지만,  ArrayList는 배열을 사용하는 클래스입니다.

 

ArrayList에 add() 하는 내부 구현 코드를 살펴보겠습니다.

add 메서드는 값의 마지막에 삽입하는 add와, index를 지정해서 삽입하는 add가 있습니다.

 

그리고 두 메서드는 모두 ensureCapacityInternal()를 호출합니다.

 

 ensureCapacityInternal()는 ensureExplicitCapacity()를 호출하는데, 만약 배열 크기를 늘려주어야하는 상황이라는 grow()메서드를 호출하는 것을 볼 수 있습니다.

 

 

 그리고 배열의 크기를 전달할 때에 DEFAULT_CAPACITY값과 비교해 최대 값을 전달해주는 것을 볼 수 있습니다. 

 DEFAULT_CAPACITY는 ArrayList의 기본 할당 사이즈로 10인 것을 알 수 있습니다.

 

 배열 크기가 DEFAULT_CAPACITY보다 작다면, DEFAULT_CAPACITY (10)을 전달하고, 보다 크다면 배열 크기를 grow() 메서드에 전달합니다.

 

 

grow 메서드에서는 배열 크기를 minCapacity로 받아 Arrays.java 의 copyOf 메서드를 호출하는 것을 볼 수 있습니다.

 

여기서 minCapacity값이 newCapacity로 생기게 됩니다.

 

 배열의 크기가 이전 배열의 크기보다 늘어야하는 상황이라면, 이전 elementData의 길이에 해당 길이의 반을 더한 길이를 리턴해주는 것을 볼 수 있습니다. (  newCapacity = oldCapacity + (oldCapacity >> 1);  )

 

 즉, 용량을 키운 배열을 복제해서 넘겨주는 것입니다.

 

 

이 과정에서 중요한 포인트는 아래와 같습니다.

 

---

1. ArrayList는 기본 배열 크기가 10으로 정해져있다.
   DEFAULT_CAPACITY = 10;

2. 배열의 크기를 늘려야하는 상황에서, 기존 배열 크기의 1.5배로 늘린다.
   newCapacity = oldCapacity + (oldCapacity >> 1); 

3. ArrayList는 배열을 복제해서 리턴해주는 방식이다.
   elementData = Arrays.copyOf(elementData, newCapacity)

---

 

 

 

내부 구조를 보고, ArrayList는 바쁜 배열이라는 느낌을 받았습니다.

 

 

 

 

 

번외 : ArrayList의 trimToSize()

 그리고 내부 구조를 구경 중에 trimToSize() 라는 익숙하지 않는 메서드를 발견했습니다. 

 

trimToSize()는 객체 공간의 크기를 데이터의 개수만큼 변경해주는 메서드입니다. 사용할 공간을 만들어 놓았는데, 사용하지 않는다면 해당 공간을 없애버리는 메서드입니다.

 

일반적으로 잘 사용하진 않겠지만, 만약 메모리 용량을 줄여야할 때가 있다면 효율적으로 사용할 수 있겠다고 생각했습니다.

 

 

 

 

참고자료

https://bepoz-study-diary.tistory.com/236

https://velog.io/@korea3611/JAVA-ArrayList-VS-LinkedList

https://www.nextree.co.kr/p6506/#:~:text=LinkedList%EB%8A%94%20ArrayList%EC%99%80%20%EB%B9%84%EA%B5%90,%EC%95%88%EC%97%90%20%EC%88%98%ED%96%89%20%ED%95%A0%20%EC%88%98%20%EC%9E%88%EC%8A%B5%EB%8B%88%EB%8B%A4