아래 코드는 java11(temurin open JDK 11)버전을 기준으로 참조했습니다.

생성자

List<Integer> arrayList = new Array<>();

위 코드를 실행하면 내부적으로 배열이 어떻게 생성될까? 👀

ArrayList.java

public class ArrayList<E> extends AbstractList<E> 
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    ...
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object[] elementData; 
    ...
    
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    ...
}

✅ Object[] 배열타입에 {} 크기 0인 배열로 초기화한다.

add

arrayList.add(100);

arrayList에 요소 하나를 추가하면 어떻게 될까

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

전역 변수 size는 클래스 상단에 선언되어 있다.

modCount: 상위 클래스인 AbstractList 의 필드이다. “구조적으로 수정된 횟수를 카운팅한다”고 설명하고 있다.
"The number of times this list has been structurally modified"

이 필드를 왜 선언했는지는 다음 시간에 알아보겠다. 😃

매개변수 3개를 받는 내부 메서드 add()를 따라가본다. 👉

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}

if s(0) == elementData.length(0) 조건이 성립되어 grow() 메서드를 호출한다.

private Object[] grow() {
    return grow(size + 1);
}

반환타입 Object[]의 grow() 메서드이다.
매개변수를 가진 내부 메서드 grow(int minCapacity)를 호출한다.

private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity));
    // 새로운 배열 = Arrays.copyof(원본 배열, 원본 배열에서 복사하고 싶은 요소들의 길이) 
}

✅ 배열을 복사한다. 🙃
newCapacity(int minCapacity) 메서드는 어떤 역할을 할까

...
private static final int DEFAULT_CAPACITY = 10;
...

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);
}

코드가 많아 보이지만 차근차근 하나씩 살펴봅시다.

✅ oldCapacity = 0
✅ newCapacity = 0 + 0
✅ shift( oldCapacity >> 1) 연산은 oldCapacity / 2로 생각하면 된다.

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) 조건이 성립되어
return Math.max(10, 0); 반환값은 10이 된다.

요소 1개가 추가되면 배열 크기는 10을 가지게 되고
요소 10개가 추가되면 grow() 메서드를 다시 호출하게 된다.

int newCapacity = oldCapacity + (oldCapacity >> 1);

위 로직에 따라 배열 크기는 15로 증가한다. 10 + (10 >> 1)

요소 15개 추가되면 22로 증가 15 + (15 >> 1)

요소 22개 추가되면 33로 증가 22 + (22 >> 1)

요소 33개 추가되면 49로 증가 33 + (33 >> 1)

요소 49개 추가되면 73로 증가 49 + (49 >> 1)

요소 73개 추가되면 109로 증가 73 + (73 >> 1)

이렇게 해서 배열의 크기는 증가한다.

❗ 하지만 크기의 제한은 있다.

...
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
...
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE)
        ? Integer.MAX_VALUE
        : MAX_ARRAY_SIZE;
}

위와 같이 일정 크기(MAX_ARRAY_SIZE) 이하로 제한하고 있다.

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;
}

👉 마지막으로 addAll() 메서드를 확인해보자.

• 여기서도 grow() 메서드를 찾아볼 수 있다.
• 매개변수 Collection 타입의 c 의 길이를 확인하고 이를 활용하여 배열의 크기를 늘려준다.

remove

✂ 요소 삭제 메서드 remove()를 호출하면 어떻게 될까?

• 내부 메서드 fastRemove(Object[] es, int i)를 호출하게 되는데 해당 인덱스를 null 처리한다.

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}