엘리
ArrayList에는 elementData라는 배열이 있다.
실제 요소는 이 배열에 저장된다.
우리가 알기로 배열은 그 크기가 고정되어 있다.
그렇다면 ArrayList에서는 어떻게 가변 길이를 지원해주는 것일까?
ArrayList의 내의 배열이 꽉 차면 1.5배 크기의 배열을 새로 할당해준다.
ArrayList에서는 add()를 할 때마다 현재 size와 elementData의 크기를 비교하고, 같으면(배열이 꽉 차있으면) elementData의 크기를 늘리는 grow()를 수행한다.
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}grow()에서는 Arrays.copyOf()를 이용해 새로운 크기의 배열을 만들고, 원래 있던 배열의 값을 복제한다. Arrays.copyOf()의 두번째 파라미터는 새로운 배열의 크기를 의미한다. 이때 newCapacity()로 새로운 배열의 크기를 결정한다.
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity));
}newCapacity()의 파라미터로 (size + 1)을 넘겨주는 이유는 배열이 비어있거나, 너무 커서 overflow가 발생하는 상황에 대비하기 위함이다.
보통의 경우 newCapacity는 기존 배열 크기의 1.5배가 된다.
이때 배열의 크기는 최대 MAX_ARRAY_SIZE(Integer.MAX_VALUE - 8)를 가질 수 있다.
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}만약 배열이 비어있는 경우 배열의 크기를 DEFAULT_CAPACITY(=10)로 늘린다.
대부분 크기를 지정하지 않고 new로 ArrayList를 생성하면 elementData의 크기가 10으로 초기화된다고 생각하겠지만 사실 크기는 0으로 초기화된다.
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}- ArrayList는 내부적으로 배열을 이용해 요소를 저장한다. (고정된 크기)
- add() 시 배열이 꽉 차 있으면 기존 배열을 복사 해 1.5배 크기의 배열을 새로 할당한다.(기존의 배열은 GC가 제거해주겠지?)
- ArrayList의 크기를 예상할 수 있다면 생성 시점에 크기를 지정해주자!
- ArrayList는 add() 시 내부 배열의 크기를 자동으로 조절하지만 remove() 시에는 자동으로 조절해 주지 않는다. 대신 현재 size로 배열의 크기를 조절해주는 trimToSize()를 제공한다. 이 또한 새로운 크기의 배열을 할당해 기존의 배열의 복제하는 방식을 사용한다.
- ArrayList에 한번에 여러 요소를 추가할 때, 그 크기를 알고 있다면 먼저 ensureCapacity()로 배열의 크기를 늘린 후 추가해주면 자원 낭비를 줄일 수 있다.