ArrayList

ArrayList

ArrayList는 배열 기반으로 구현된 동적으로 크기 조절 가능한 List 인터페이스의 구현 클래스다.

내부적으로 배열을 사용해서 데이터를 저장하고, 크기가 동적으로 조절되며 순서를 유지하고 중복을 허용하는 List 인터페이스의 구현체다.

ArrayList 내부 구현

ArrayList 내부 필드

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    transient Object[] elementData;  
    private int size;                
}

• elementData: 실제 요소들을 저장하는 Object 배열

(transient 키워드는 직렬화 시 배열 전체가 아닌 실제 사용 중인 요소만 직렬화하기 위해서 사용한다.)

• size: 실제 저장된 요소의 개수

ArrayList의 생성자 3가지

1. 기본 생성자

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

기본 생성자로 ArrayList를 만들면, 처음에는 size와 capacity가 모두 0이고,
첫 요소를 추가하면 capacity가 10으로 확장되고 size는 1이 된다.

(사용하지 않을 ArrayList에 대한 메모리 낭비 방지와 잦은 재할당 방지를 위해 저렇게 구현되었다.)

2. 용량 지정 생성자

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
}

용량 지정 생성자로 ArrayList를 만들면, 생성 시점에 내부 배열이 지정한 capacity로 즉시 생성된다.

(초기 데이터 개수가 예상되는 경우, 불필요한 배열 확장과 복사를 방지하기 위해 이렇게 구현되었다.)

3. 컬렉션 생성자

public ArrayList(Collection<? extends E> c) {
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else {
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        elementData = EMPTY_ELEMENTDATA;
    }
}

컬렉션 생성자로 ArrayList를 만들면, 전달된 컬렉션의 요소 개수만큼 size가 즉시 설정되고, 내부 배열도 그 크기에 맞게 한 번에 생성된다.

(기존 컬렉션의 데이터를 복사하면서 불필요한 확장 과정을 제거하고, ArrayList가 전달된 경우 내부 배열을 재사용하여 추가적인 복사를 피하기 위해 저렇게 구현되었다.)

일반 배열 vs ArrayList

비교표

특성	배열 (Array)	ArrayList
크기	고정 (생성 시 결정)	동적 (자동 확장/축소)
타입 안전성	컴파일 타임 체크	제네릭으로 컴파일 타임 체크
원시 타입	직접 저장 가능	래퍼 클래스 필요 (오토박싱)
메모리 오버헤드	최소 (데이터만)	추가 필드(size, capacity) + 여유 공간
성능	직접 접근 (최고 성능)	약간의 오버헤드 (메소드 호출)
다차원	네이티브 지원	ArrayList<ArrayList<T>> 형태
편의 메소드	없음 (Arrays 유틸 사용)	API (add, remove, contains 등)
길이 확인	array.length (필드)	list.size() (메소드)

메모리 레이아웃 비교

배열

int[] arr = new int[100];

메모리: [헤더 16바이트] + [100 * 4바이트] = 416바이트

ArrayList

ArrayList<Integer> list = new ArrayList<>(100);

메모리: [ArrayList 객체 ~32바이트] + [Object[] 배열 헤더 16바이트] + [100 * 8바이트 (참조)] + [Integer 객체들 각 16바이트]

최소 ~1,648바이트 (오토박싱 시)

그래서

-> 원시 타입 대량 데이터는 배열이 5~10배 메모리 효율적이다.

동적 크기 조정 메커니즘

요소 추가 시 확장 프로세스

public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}
// 구조 변경 횟수를 기록하고 실제 추가 로직을 내부 메서드에 위임한다.

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}
// 현재 배열이 가득 찼는지 확인하고, 필요하면 확장한 뒤 요소를 추가하고 size를 증가시킨다.

grow()

private Object[] grow() {
    return grow(size + 1);
}
// 최소 한 칸 이상을 확보하기 위해 필요한 최소 용량을 계산해 확장 메서드를 호출한다.

private Object[] grow(int minCapacity) {
    int oldCapacity = elementData.length;
    if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        int newCapacity = ArraysSupport.newLength(
            oldCapacity,
            minCapacity - oldCapacity,  // 최소 증가량
            oldCapacity >> 1            // 선호 증가량: 50% 증가
        );
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}
/*기존 용량이 있으면 약 1.5배로 확장하고,
기본 생성자로 만들어진 빈 리스트라면 기본 용량(10)으로 초기화한다.*/

확장 전략

확장 비율: 1.5배

초기: 10
1차: 15  (10 + 10/2)
2차: 22  (15 + 15/2)
3차: 33  (22 + 22/2)
4차: 49
5차: 73
6차: 109
7차: 163
8차: 244
9차: 366
10차: 549

1.5배인 이유
잦은 배열 복사를 방지하면서도 과도한 메모리 낭비를 막기 위해서 1.5배씩 확장한다.

분할상환 분석

n개 요소를 추가하면,

실제 복사 횟수: log₁.₅(n)
총 복사된 요소 수: ~2n (기하급수 합)
요소당 평균 비용: O(1)

증명:

총 비용 = n (삽입) + Σ 2^i (복사, i=0 to log₂n)
        = n + 2n
        = 3n
평균 = 3n/n = O(1)

명시적 크기 조정

// 용량 확보 (resizing 방지)
public void ensureCapacity(int minCapacity)

// 여유 공간 제거 (메모리 최적화)
public void trimToSize()

사용예시

// 나쁜 예시
ArrayList<String> list = new ArrayList<>();
for (int i = 0; i < 1000000; i++) {
    list.add("item" + i);  // 많은 resizing 발생
}

// 좋은 예시
ArrayList<String> list = new ArrayList<>(1000000);
for (int i = 0; i < 1000000; i++) {
    list.add("item" + i);  // resizing 없음
}

주요 메소드 시간복잡도

메소드	최선	평균	최악	비고
add(E e)	O(1)	O(1)*	O(n)	*분할상환, 최악은 resizing 시
add(int index, E e)	O(n)	O(n)	O(n)	뒤 요소들 shift + 잠재적 resizing
get(int index)	O(1)	O(1)	O(1)	배열 직접 접근
set(int index, E e)	O(1)	O(1)	O(1)	배열 직접 쓰기
remove(int index)	O(1)	O(n)	O(n)	마지막 요소 O(1), 평균은 shift
remove(Object o)	O(n)	O(n)	O(n)	검색 + 삭제
contains(Object o)	O(1)	O(n)	O(n)	선형 검색
indexOf(Object o)	O(1)	O(n)	O(n)	선형 검색
clear()	O(n)	O(n)	O(n)	모든 참조 null 처리 (GC 위해)
size()	O(1)	O(1)	O(1)	필드 반환
isEmpty()	O(1)	O(1)	O(1)	size == 0 체크
toArray()	O(n)	O(n)	O(n)	전체 복사
iterator()	O(1)	O(1)	O(1)	Iterator 객체 생성만
sort(Comparator)	O(n)	O(n log n)	O(n log n)	TimSort (최선은 정렬된 경우)

인덱스를 통한 접근과 수정은 배열에 직접 접근하므로 O(1)이다.

반면에 검색, 중간 삽입, 중간 삭제는 요소들을 하나씩 검사하거나 이동해야 해서 O(n)이다.

끝에 요소를 추가하는 경우는 대부분 공간이 남아 있어 O(1)이지만,
배열이 가득 찼을 때는 확장(resizing)으로 인해 O(n)이 발생할 수 있다.