[자료구조] ArrayList는 배열이 꽉찼을때 어떻게 하는가

Java의 ArrayList는 내부적으로 배열을 사용한다. 그런데 배열은 고정 크기를 가지고 있어서

ArrayList가 꽉 찼을 때는 어떻게 새로운 데이터를 추가할수 있을까?

 

이번 글에서는 ArrayList의 내부 구현을 통해서 배열이 꽉 찼을 때 어떤 일이 벌어지는지 알아보겠다.

---

1. 요소 추가 메서드 : add(E e)

• 먼저 리스트에 요소를 추가하는 메서드인 add()를 알아볼것이다. 코드로 알아보자

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}

 

 

1-1. modCount++;

 

modCount는 ArrayList의 부모 클래스인 AbstractList에 정의된 필드 이다.

 

✔️ modCount란?

• modCount는 ArrayList의 구조적 변경 횟수를 기록하는 필드 값이다.
• 구조적 변경은 리스트의 크기를 변경하거나 순회 중 결과에 영향을 줄 수 있는 변경을 의미하는데 
• 쉽게 말해 이 리스트가 얼마나 바뀌었는지 추적하는 역할을 한다.

 

✔️ 그럼 왜 할까?

• ArrayList를 iterator()로 순회 중 외부에서 리스트를 수정하면 예상치 못한 동작이 발생할 수 있다.
• 이럴 때 modCount의 값이 변경되었는지 감지하고 다음 next(), remove() 호출 시에 ConcurrentModificationException을 던진다.

"fail-fast 동작이란?"

fail-fast: 데이터를 순회 중일 때 구조적 변경이 감지되면 즉시 예외를 던져 비정상적인 상태를 방지하는 동작 방식이다.

 

서브 클래스에서 fail-fast Iterator를 제공하고자 한다면 add(), remove() 등의 메서드에서 modCount++를 반드시 호출해야 한다.

 

 

1-2. add(E e, Object[] elementData, int size);

 

 

1-2-1 if(s == elementData.length) elementData = grow();

• 배열이 꽉 찼는지 확인한다.
• 현재 요소 개수가 배열의 길이와 같다면 배열이 꽉 찼다는 의미이다.
• 이때 grow()를 호출하여 배열을 확장한다.

 

1-2-2 배열 확장 grow();

 

grow() 메서드가 호출되면 그 안에서 또 grow 메서드가 호출이 되는데 파라미터 값으로 size + 1를 줬다.

 

차례대로 보면

 

 동작 단계 요약

 

1. 현재 배열 크기 확인

int oldCapacity = elementData.length;

 

2. 기존 배열이 초기 상태가 아니라면

• 새로운 크기를 계산한다.
• 기본적으로 1.5배 크기로 늘어나도록 설계되어 있다.

3. 새 배열로 기존 배열 복사

return elementData = Arrays.copyOf(elementData, newCapacity);

 

4. 초기 상태였다면

• 기본 크기(DEFAULT_CAPACITY, 보통 10) 또는 minCapacity 중 큰 값으로 배열을 새로 생성 한다.

 

 

1-3 요소 삽입

elementData[s] = e;

배열 확장이 완료되면 새 요소 e 를 s 번째 위치에 삽입한다.

 

 

1-4 사이즈 증가

size = s + 1;

마지막으로 size 값을 1 증가시켜 현재 요소 개수를 반영한다.

 

---

정리

 

ArrayList는 내부 배열이 꽉 찼을 경우 grow() 메서드를 호출하여 배열을 기존 크기의 1.5배로 확장하고

기존 데이터를 복사한 뒤 새로운 요소를 추가합니다.

이 과정에서 modCount로 변경을 추적하여 fail-fast 동작을 제공한다.