Java ArrayList
ArrayList는 List 인터페이스의 구현체로, 새로운 원소가 추가되면 그에 맞게 동적 할당을 해주는 열거형(List형) Collection이다. 배열은 한번 선언할 때 크기를 정해주고, 그 크기를 넘어가는 수의 요소를 저장할 수 없지만, ArrayList는 빈공간이 부족하다면 알아서 그 크기를 늘려준다.
이런 ArrayList도 내부 코드는 배열을 사용하고 있다. 아래에서 코드를 살펴보며 더 자세히 알게 되겠지만, 미리 선언해둔 배열에 빈공간이 부족하면 더 큰 배열을 선언하고 기존 배열의 값을 복사하는 식으로 구현돼있다.
이 ArrayList는 JDK 6, 7, 8 버전을 거치며, 더 효율적으로 동적할당을 하는 방향으로 개선되어 왔다. 이제부터 Java 6, 7, 8 버전의 코드를 비교해보며 어떤 점이 개선되었는지 살펴보려한다.
JDK 6 코드
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacity(size+1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}JDK6의 ArrayList add 메소드는 이렇게 생겼다.
아래에서 하나하나 살펴 보면
public boolean add(E e)
ArrayList의 가장 마지막에 원소를 추가하는 메소드
public boolean add(E e) {
ensureCapacity(size + 1); // modCount를 증가시킨다.
elementData[size++] = e; // e를 배열에 추가하고 size(ArrayList의 마지막 부분을 가리키는 포인터 역할)를 1 증가 시킨다.
return true;
}- ensureCapacity에서 modCount를 증가 시킨다.
- 새로운 원소를 배열에 가장 끝에 저장하고, size를 1 증가 시킨다.
- 성공하면 true를 반환한다.
그렇다면 add 메소드 내부에서 호출되는 ensureCapacity() 메소드는 어떤 일을 하는 메소드일까?
public void ensureCapacity(int minCapacity)
public void ensureCapacity(int minCapacity) {
modCount++; // 1. modCount를 증가 시킨다.
int oldCapacity = elementData.length; // 2. elementData 배열의 길이를 oldCapacity에 저장한다.
if (minCapacity > oldCapacity) { // 3. minCapacity가 oldCapacity보다 크다면 배열의 크기를 늘려줘야하는 상황이다.
Object oldData[] = elementData; // 4. 기존 데이터의 주소값을 oldData에 복사해준다.
int newCapacity = (oldCapacity * 3)/2 + 1; // 5. newCapacity에 기존 capacity의 약 1.5배인 수를 저장한다.
if (newCapacity < minCapacity)
newCapacity = minCapacity; // 6. 만약 newCapacity가 minCapacity보다 더 작다면 newCapacity에 minCapacity를 저장해준다.
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity); //
}
}한줄 한줄 살펴보자.
- modCount를 증가시킨다.
- elementData 배열의 길이를 oldCapacity에 저장한다.
- minCapacity(add를 했을 때, 배열에 있는 원소 개수)가 oldCapacity보다 크다면 배열의 크기를 늘려주어야하는 상황이다.
- 기존 데이터의 주소값을 oldData에 저장해준다.
- newCapacity에 oldCapacity에 약 1.5배에 해당하는 값을 저장해준다.
- 만약 minCapacity가 newCapacity보다 크다면 newCapacity에 minCapacity 값을 저장한다.
- Arrays.copyOf()로 배열을 복사한다.
- 3번에서 만약 minCapacity가 oldCapacity보다 작다면 그냥 메소드를 빠져나오게 된다.
즉 위 과정을 요약해보자면, 새로운 원소를 추가했을 때(add(E e) 호출) 배열에 여분 공간이 있다면 modCount를 증가시키고 그냥 요소를 배열에 저장한다.
만약 여분 공간이 없는 상황이라면 배열의 크기를 늘려주어야 하는데, 기존 배열의 약 1.5배로 늘려주고 늘린 후에도 공간이 부족하다면 minCapacity만큼 늘려주는 것으로 한다. 그리고 기존 배열의 값을 모두 복사한 새로운 배열을 만든다. (Arrays.copyOf())
ArrayList가 배열을 확장하는 방법. 공간이 부족할 때마다 약 50%를 늘려준다. (length: 6 -> 10)
Arrays.copyOf(자료형[] original, int newLength)
Arrays.copyOf(원본 배열, newLength) 메소드는 newLength 크기의 새로운 배열을 만들고, 원본 배열의 값을 newLength개 만큼 복사해 리턴하는 메소드이다. 만약 원본 배열의 길이가 newLength보다 작다면, 원본 배열의 값들을 복사한 뒤, 남은 공간은 0으로 채워지게 된다.
modCount란?
modCount란 해당 리스트가 변경된 횟수를 가리킨다. 이는 ArrayList가 상속한 추상 클래스인 AbstractList에 선언되어있다.
ArrayList 같은 List 자료구조는 foreach문을 도는 동안 수정이 생기면 안된다. 따라서 modCount와 expectedModCount라는 변수의 값이 동일한지 비교를 하여 다를 경우 예기치 않은 변형으로 간주하며 ConcurrentModificationException을 발생시킨다. expectedModCount는 ListItr 클래스에 존재하는 필드이며, iterator가 생성될 때 expectedModCount에 modCount값이 저장되고, next()로 다음 요소를 돌 때마다 두 변수값이 비교되는 것이다.
public void add(int index, E element)
public void add(int index, E element) {
rangeCheckForAdd(index); // 1. 인덱스가 유효한지 체크
ensureCapacity(size+1); // 2. modCount 늘리기
System.arraycopy(elementData, index, elementData, index + 1,
size - index); // 3. index번째 자리를 비우기 위해 원소를 index번째부터 한 칸씩 뒤로 밀기
elementData[index] = element; // 4. index 위치에 새로 들어온 element를 저장
size++; // 5. size를 증가시킴
}add(int index, E element) 메소드는 인자로 넘어온 인덱스 위치에 element를 저장하는 메소드이다. 주석의 번호와 같이 코드를 한줄 한줄 살펴보자.
- 인자로 넘어온 인덱스가 유효한 수인지 체크한다. Index가 현재 배열의 크키(size)보다 크거나, 0보다 작다면 IndexOutOfBoundsException을 던진다.
- modCount를 늘린다
- elementData의 index부터 (size-index)개의 원소를 복사해서 elementData의 index+1 위치부터 붙여넣기 한다. 즉, index번째 위치를 비우려고 index번째에 있는 요소부터 한칸씩 뒤로 미는 것과 같다.
- index 위치에 새로 들어온 element를 저장
- size(ArrayList에 저장된 요소의 개수)를 증가시켜준다.
즉 이 과정도 요약을 하자면, 배열의 자리가 모자르다면 더 큰 배열을 만들어서 그곳으로 옮긴다. (ensureCapacity() 메소드 안에서)
그리고 index번째의 자리를 만들기 위해서 (index)~(size-1)에 있는 원소를 복사하여 index+1번째로 옮긴다.
JDK 7 코드
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
if (minCapacity > 0)
ensureCapacityInternal(minCapacity);
}
private void ensureCapacityInternal(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}JDK 7 ArrayList add() 메소드의 코드는 이렇다. 아래에서 메소드 하나하나씩 살펴보자
public boolean add(E e)
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}JDK 6의 코드와 비슷해 보이지만 ensureCapacity() 메소드가 아닌 ensureCapacityInternal()이 호출되고 있다.
public void add(int index, E element)
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}public void add(int index, E element) 메소드도 ensureCapacityInternal(size + 1)을 호출하고 있다는 점 말고는 달라진 점이 없다.
private void ensureCapacityInternal(int minCapacity)
private void ensureCapacityInternal(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}ensureCapacityInternal() 메소드 안에서는 배열의 빈공간이 부족하다면 grow()라는 메소드를 호출하게 된다.
grow() 추가되는 요소를 저장할 공간이 부족할 때, 배열의 길이를 늘려주는 메소드이다. 아래에서 grow() 메소드에 대해 살펴보자.
private void grow(int minCapacity)
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 중요 1. 1.5배를 비트 시프트와 덧셈으로 처리
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity); // 오버 플로우
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}grow() 메소드에서 잘 봐야하는 부분은 주석으로 "중요"라고 써놓은 부분이다.
//jdk 6
int newCapacity = (oldCapacity * 3)/2 + 1;
// jdk 7
int newCapacity = oldCapacity + (oldCapacity >> 1);jdk6에서 배열의 length를 늘릴 때, 기존 length에 약 1.5배를 해주었다. 그때는 3을 곱한 뒤 2로 나누고 1을 더하는 방법을 썼었는데, *, / 연산은 + 또는 비트 시프팅 연산 보다 느리다. (특히 나눗셈은 곱셈보다 더 느리다)
하지만 jdk에서는 1.5배의 연산을 곱하기, 나누기 대신 비트 시프트 연산과 + 연산으로 대체해서 최적화를 한 것을 확인할 수 있다.
int hugeCapacity(int minCapacity)
또한 JDK 7 버전에서 달라진 점은 배열의 크기를 결정하는 minCapacity에서 오버플로우가 발생했을 경우를 처리해주었다는 점이다. 만약 minCapacity가 MAX_ARRAY_SIZE보다 크다면 hugeCapacity()라는 메소드를 호출하게 되는데, 그 메소드의 내용은 아래와 같다.
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}minCapacity가 MAX_ARRAY_SIZE보다 크다면 Integer 클래스의 MAX_VALUE를 리턴하여 배열의 크기를 int형 범위의 최대값으로 설정한다.
만약 minCapacity가 음수라면 int 범위를 넘어가 오버플로우가 발생한 것이다. 이럴 때에는 OutOfMemory Exception을 던진다.
JDK 8
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != EMPTY_ELEMENTDATA)
// any size if real element table
? 0
// larger than default for empty table. It's already supposed to be
// at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}이것이 JDK 8의 ArrayList add() 메소드의 코드이다.
7 버전과 달라진 점은 아래 코드와 같은 부분이다.
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}만약 ArrayList가 새로 생성되어 EMPTY_ELEMENTDATA 상태라면 minCapacity를 DEFAULT_CAPACITY(=10)와 인자로 들어온 minCapacity 중 큰 값으로 설정한다.
이런 코드를 추가한 이유는 ArrayList에 요소를 추가할 때 ArrayList의 크기를 늘리는 과정을 효율적으로 하기 위해서라는 생각이 들었다.
ArrayList는 새로운 요소가 들어왔을 때 빈공간이 부족할 때마다 현재 크기의 약 1.5배로 늘리는 방법을 써왔다.
그렇다면 JDK 7 이전 버전에서 만약 다음과 같이 ArrayList가 선언되고 요소가 계속 추가된다면 어떨까?
ArrayList<Integer> list = new ArrayList<>(1);
요소 1개를 추가하고, 2개 째부터 공간이 모자르므로 더 큰 배열을 선언하고 그 배열로 모든 요소를 옮겨줄 것이다. jdk 7에서 늘려주는 방식으로 한다면 새로운 배열은 크기 2로 늘어난다. (이유는 oldCapacity + (oldCapacity >> 1) 한 결과가 1이고, minCapacity와 newCapacity 중 큰 것을 선택하기 때문에 1 대신 2가 선택된다.)
그리고 다시 세번째 요소를 추가하려고 하면 또 공간이 모자란다. 그러면 크기가 3인 배열을 다시 만들어 그 값을 옮겨주면 다시 네번째 원소를 추가하려고 해도 공간이 모자란다. 그러면 방금했던 배열 확장과 복사 과정을 반복하게 된다.
이렇게 ArrayList의 초기 크기가 지나치게 작게 설정되면 이렇게 배열 확장/복사가 빈번하게 발생하여 효율이 떨어지기 때문에 적당한 크기인 10으로 초기 크기를 설정해주는 것 같다.
메모리가 부족하지 않으면서, 배열의 확장, 복사가 적게 일어나려면 어떻게 ArrayList를 선언해야할까?
JDK 7 이전에서
- ArrayList의 크기가 지나치게 작게(ex. 1, 2, 3) 선언하는 것을 지양.
JDK 6, 7, 8에서
-
ArrayList에 들어갈 수를 예상할 수 있다면 그것에 맞게(근사한 수로) 선언하는 것이 좋을 것 같다. (ex. 많은 요소가 들어갈 것 같다면 처음부터 크게 선언)
-
여러 개의 요소를 추가할 것이라면 add로 하나씩 추가하는 것보다는 addAll로 한번에 추가하는 것이 좋을 것 같다. grow를 할때 s+numNew만큼으 크기로 한번에 배열에 크기를 증가시켜주기 때문이다. 아래는 Jdk 20의 addAll 메소드이다.
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;
return true;
}- 중간 인덱스 요소에 대한 삽입, 삭제가 빈번하다면 ArrayList 대신 LinkedList 클래스를 사용. LinkedList 구현체는 내부적으로 이중 연결 리스트로 되어있기에 중간 요소에 대한 삽입, 삭제가 ArrayList에 비해 연산량이 적다.
아래는 jdk 20의 LinkedList add(int index, E element) 메소드 코드이다.
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}Reference
https://seunghyunson.tistory.com/26
https://velog.io/@guswlsapdlf/Java-ArrayList-Add-Method
https://www.scientecheasy.com/2020/09/use-of-arraylist-in-java.html/
