[Java] ArrayList 파헤쳐 보기
Java 개발에서 Collection의 데이터 타입을 사용하면서 내부 코드를 볼 생각을 하지는 않았었는데, 직접 ArrayList 클래스를 살펴보며 어떻게 동작하는지 공부해보니 흥미로운 부분이 많았다. 여기서는 ArrayList의 생성자, 삽입/삭제/초기화/정렬 메소드 중심으로 정리해보려 한다.
Resizable-array implementation of the List
ArrayList란 Size가 변하는 배열을 말한다. 그리고 다음과 같은 몇가지 특징을 가진다.
o 중간에 데이터를 삽입, 삭제하는 것이 가능
o Reference Data Type만 넣을 수 있음
o Thread Safe 하지 않음
그럼 코드를 한 번 살펴보자.
o 인스턴스 변수
: ArrayList는 값을 담고있는 Object배열과 실제 존재하는 element의 갯수를 담는 size를 인스턴스 변수로 가진다.
transient Object[] elementData;
private int size;o 생성자
: default는 { }, 생성자로 데이터 개수를 입력받을 시 new Object[initialCapacity] 로 element 배열 생성
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA; // {}
} else {//...}
}o 데이터 삽입
: List 인터페이스를 구현한 add() 메소드로 데이터를 추가하는 경우는 두가지 케이스로 나뉜다.
(1) 데이터의 맨 끝에 삽입하는 경우
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow(); // 배열의 크기 증가시키기
elementData[s] = e;
size = s + 1;
}
(2) 특정 index에 삽입하는 경우
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow(); // 배열의 크기 증가시키기
System.arraycopy(elementData, index,
elementData, index + 1,
s - index); // index위치 부터의 데이터를 index+1 위치부터 시작하도록 바꾸어줌
elementData[index] = element;
size = s + 1;
}
여기서 주의할 부분은 grow() 메소드이다. ArrayLisr의 elementData는 배열이기 때문에 제한된 length를 가지는데, 실제 값이 들어있는 size가 이와 같아지게 되면 배열의 크기를 증가시키는 작업이 필요하다.
* grow()
: 이는 내부적으로 다음과 같이 현재 size/2만큼 length를 증가시키고 이전 elements들을 copy한다.
private Object[] grow(int minCapacity) {
//생략..
return elementData = Arrays.copyOf(elementData, newCapacity);
}
맨 뒤에 데이터를 추가하는 경우에는 size위치에, index가 주어진 경우에는 기존에 index~end 까지의 데이터를 index+1~end+1 위치로 옮긴 뒤에 해당 위치에 값을 넣어주고 size를 증가시킨다.
o 데이터 삭제
: List 인터페이스에 선언된 메소드들을 구현한 부분이다.
(1) 특정 인덱스의 데이터를 삭제하는 경우
--> remove() 메소드
: fastRemove() 에서 System.arraycopy(es, i + 1, es, i, newSize - i); 를 수행한 뒤, 삭제하는 element값을 return한다.
(2) 모든 데이터를 삭제하는 경우
--> clear() 메소드
: 모든 elementData를 모두 순회하며 값을 null로 바꿔준다.
o 정렬
: List 인터페이스에 선언된 메소드를 구현하고 있는데, Arrays.sort() 메소드를 통해 정렬하고 있다.
그렇다면 한 번 더 들어가서 Arrays.sort()는 어떻게 구현되어져 있을까?
public static <T> void sort(T[] a, int fromIndex, int toIndex,
Comparator<? super T> c) {
//...
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, fromIndex, toIndex, c);
else
TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
// 생략...
}이는 개발자가 system.property 값을 설정하여 LegacyMergeSort를 사용하거나 merge sort보다 최적화된 TimSort를 사용하도록 구현되어있다. 여기서는 자세한 해당 정렬 방법은 생략하고, TimSort가 사용되는 것만 확인하고 넘어가자.
이 외에 get(), set() 같은 메소드는 구현이 너무 간단하여 설명을 생략하였다.
추가로 ArrayList 내부에는 훨씬 더 많은 메소드들이 존재하지만, 주요 메소드만 정리해보았으니 개발하면서 한번씩 ArrayList에서 사용하는 메소드들은 실제로 해당 소스파일에서 확인해보는 것도 좋을 것 같다.