ArrayList 자료 구조 분석

개요

C에 Vector가 있다면 Java에 ArrayList가 있습니다. 물론 Java에도 멀티 스레딩 환경에서 최적화된 ArrayList인 Vector가 있긴하지만, 오늘은 기본적으로 ArrayList에 대해서만 정리하도록 하겠습니다.

 

일반적인 Array는 그 크기가 정적(Static)입니다. Array를 생성하면서 크기를 설정하면 할당된 해당 Array는 크기 변경이 불가능합니다. 메모리에 Random-Access하기 위해서는 메모리 위에 한번에 그 영역을 설정해야하므로 이렇게 만들어졌다고 생각됩니다.

 

실제로 프로그래밍을 하다보면, Array를 사용하다가 그 크기를 변경해야할 때가 있습니다. 혹은 Array의 특성 때문에 초기에 너무 큰 공간을 할당해서 공간을 낭비하는 경우도 있습니다. 이런 경우 적합한 크기를 가진 새로운 Array를 만들어야하는 불편한 상황이 생깁니다.

 

우리는 이러한 문제를 해결하기 위해, 동적인 Array를 만들게 되는데, 이것이 바로 ArrayList입니다. ArrayList는 List Interface를 구현한 클래스로, 크기가 동적으로 변하는 Array라고 볼 수 있습니다.

 

동작 원리

ArrayList는 List Interface를 구현했기 때문에 List가 가진 메서드를 사용할 수 있습니다. 대표적으로 get, set, contains, Iterate와 같은 것들이 있습니다.

그리고 배열의 특성을 지니기 때문에 Random-Access가 가능합니다. Random-Access는 하단에 링크로 추가해놓겠습니다. 연결 리스트처럼 Sequential하게 접근하는 것이 아닌, 원하는 Index로 상수시간에 접근 가능한 것을 말합니다. Array의 가장 큰 장점이자 특징이죠. 왜 ArrayList는 배열의 특성을 지닐까요?

 

ArrayList 명세를 들어가면 다음과 같이 내부적으로 elementData라는 Object타입의 Array를 가지고 있습니다. 이를 통해서 Random Access가 가능한 것이죠.

명세에 보면 Default Size가 10이라는 것도 알 수 있네요. 이는 ArrayList에 initial size를 따로 명시하지 않았을 때 가지는 사이즈 입니다.

 

가장 중요한 ArrayList의 크기 확장은 어떻게 일어나는 걸까요? 다음과 같은 순서로 진행됩니다.

 

1. 힙 메모리에 현재 가진 배열 크기의 두배가 되는 배열을 새로 생성합니다. (ArrayList 내부적으로 정의된 상수인 MAX_ARRAY_SIZE보다는 반드시 작은 크기로 할당되므로 이 경우는 두배보다 작은 크기로 할당됩니다)

2. 현재 배열의 element들을 새로 생성한 배열로 복사합니다.

3. 기존 배열을 메모리에서 제거합니다.

 

다음과 같이 기존 힙에 크기 확장이 필요한 ArrayList가 존재한다면,

 

다음과 같이 현재 크기의 두배의 크기를 가진 배열을 내부적으로 생성합니다.

 

그리고 이전 배열은 힙에서 삭제됩니다.

마찬 가지로 구현 명세서에 이를 확인할 수 있는 부분이 있습니다.

우리가 add나 addAll이라는 ArrayList의 api를 호출하면 내부적으로 호출되는 메서드들이 있습니다.

 

우리가 일반적으로 호출하는 add는 하단의 add이고 상단의 add를 Wrapping한 형태인데요, 상단의 private으로 구현된 add는 내부적으로 grow라는 메서드를 호출하고 있습니다.

 

grow는 newCapacity를 통해 계산된 새로운 배열크기만큼 배열을 복사하는 기능을 수행하고 있습니다.

이를 통해 새로운 배열을 생성하고 복사한다는 것을 확인할 수 있네요.

 

ArrayList는 Array와 LinkedList와 비교가 자주 되므로 이 자료구조들과의 차이점을 생각해보면 더 좋을 것 같습니다.

 

참고 문헌

https://en.wikipedia.org/wiki/Random_access

Random access - Wikipedia

 

https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html

ArrayList (Java Platform SE 8 )

https://www.geeksforgeeks.org/arraylist-in-java/

ArrayList in Java - GeeksforGeeks