ArrayList 상세 분석

ArrayList는 본질적으로 클래스이며, 내부에 배열을 유지해 요소를 저장하고 size 변수로 "실제로 몇 개가 들어 있는지"를 기록합니다.

추상화하면 다음과 같습니다.

Java

        public class ArrayList<E> {
    transient Object[] elementData;
    private int size;
}

핵심은 두 가지입니다.

elementData: 실제 데이터를 담는 내부 배열
size: 현재 유효한 요소 개수

elementData.length 는 size 와 같지 않습니다.

예를 들어:

elementData.length = 10: 내부 용량은 10
size = 3: 실제 사용 중인 칸은 3개

즉 앞의 3칸에만 데이터가 있고, 나머지 7칸은 비어 있을 수 있습니다.

내부가 왜 Object 인가

소스 코드에서는 E[] 대신 보통 Object[] 를 사용합니다.

이유는 Java 제네릭의 타입 소거(type erasure) 때문입니다. 런타임에는 E 의 실제 타입을 알 수 없어서, 많은 제네릭 컬렉션이 Object[] 에 저장하고 꺼낼 때 캐스팅합니다.

즉:

저장할 때: Object[] 에 저장
꺼낼 때: E 로 캐스팅

그래서 ArrayList는 다양한 객체 타입을 담을 수 있지만, 타입 안정성을 위해 제네릭 사용은 필수입니다.

초기화는 어떻게 되는가

ArrayList의 대표 생성자는 다음과 같습니다.

Java

        new ArrayList<>();
new ArrayList<>(20);
new ArrayList<>(collection);

소스 관점에서는 앞의 두 가지가 핵심입니다.

기본 생성자
처음부터 길이 10 배열을 만들지 않고, 우선 빈 배열을 가리킵니다.
예:
Java
```
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

    
```
의미:
- new ArrayList<>() 직후에는 기본 용량을 아직 할당하지 않음
- 첫 add 시점에만 기본 용량으로 확장
사용되지 않는 리스트에 메모리를 낭비하지 않기 위한 설계입니다.

초기 용량 지정 생성자
new ArrayList<>(20); 을 쓰면 길이 20 배열을 바로 만듭니다.
예:

Java

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

대략적인 데이터 규모를 알 때 리사이즈 횟수를 줄일 수 있어 유용합니다.

add는 실제로 무엇을 하나

가장 흔한 호출은 list.add(e); 입니다.

대략적인 로직:

Java

        public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

두 단계로 볼 수 있습니다.

용량 확인 ensureCapacityInternal(size + 1) 는 추가 후 size + 1 개를 담을 수 있는지 확인하고, 부족하면 확장합니다.
맨 뒤에 저장

Java

        elementData[size] = e;
size++;

또는:

Java

        elementData[size++] = e;

끝에 추가가 빠른 이유:

위치 탐색이 필요 없음
기존 요소 이동이 필요 없음
대부분 배열 끝에 값 하나만 기록

그래서 끝 삽입은 보통 분할상환 O(1)입니다.

첫 add에서 왜 기본 용량 10이 되는가

많이 헷갈리는 부분입니다.

기본 생성자 호출 시에는 길이 10 배열을 바로 만들지 않습니다. 첫 요소 추가 시 기본 용량 초기화가 일어납니다.

로직은 대략 다음과 같습니다.

Java

        private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

기본 용량은 보통 private static final int DEFAULT_CAPACITY = 10; 입니다.

즉:

new ArrayList<>(): 여전히 빈 배열
첫 add: 용량이 10으로 설정

이것이 지연 할당 전략입니다.

확장 메커니즘은 어떻게 구현되는가

용량이 부족하면 grow() 를 타게 됩니다.

Java

        // JDK 8
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    elementData = Arrays.copyOf(elementData, newCapacity);
}

// JDK 17
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             // 기대 증가량: 1.5배
        );
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        // 첫 확장: 바로 10
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
    }
}

핵심 한 줄: int newCapacity = oldCapacity + (oldCapacity >> 1);

oldCapacity >> 1 은 2로 나누기이므로 새 용량은 대략 1.5배가 됩니다.

예:

10 -> 15
15 -> 22
22 -> 33

왜 2배도 아니고 +1도 아닌 1.5배인가? 공간과 시간의 절충입니다.

매번 +1이면:

확장이 너무 자주 발생
매번 배열 복사 필요
성능 저하

매번 2배면:

확장 횟수는 줄지만
메모리 낭비가 커질 수 있음

그래서 1.5배가 균형점으로 많이 쓰입니다.

실제 비용이 큰 부분은 Arrays.copyOf(elementData, newCapacity); 입니다.

더 큰 새 배열 생성
기존 요소 복사
참조를 새 배열로 교체

즉 확장은 "기존 배열 늘리기"가 아니라 "새로 만들고 복사"입니다.

인덱스 삽입이 느린 이유

list.add(index, element); 는 단순한 끝 삽입이 아닙니다.

Java

        public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

핵심은 System.arraycopy(...) 입니다.

index 뒤 요소들을 한 칸씩 오른쪽으로 밀어야 합니다.

예: [A, B, C, D] 에서 1번 위치에 X 삽입

B, C, D를 뒤로 이동
1번 위치에 X 저장

결과: [A, X, B, C, D]

느린 이유는 위치를 못 찾아서가 아니라 이동 비용 때문입니다. 시간 복잡도는 O(n).

remove도 느린 이유

삭제는 삽입의 반대입니다.

list.remove(index); 의 대략적인 로직:

Java

        public E remove(int index) {
    rangeCheck(index);
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    elementData[--size] = null;
    return oldValue;
}

과정은 3단계입니다.

기존 값 보관
뒤 요소를 앞으로 당김
마지막 칸을 null 로 설정

elementData[--size] = null; 이 중요한 이유는 GC가 회수할 수 있도록 참조를 끊기 위해서입니다.

get이 빠른 이유

get(index) 는 사실상 배열 인덱스 접근입니다.

Java

        public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

연속 배열 기반이라 직접 접근 가능하고 순회가 필요 없어 O(1)입니다.

set도 빠른 이유

set(index, element) 는 지정 위치를 덮어쓰기만 합니다.

Java

        public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

요소 이동이 없어 보통 O(1)입니다.

null과 중복 요소를 허용하는 이유

ArrayList는 중복 제거를 하지 않고 null 도 제한하지 않습니다.

순서와 위치를 다루는 컨테이너이지, 유일성을 강제하는 집합이 아니기 때문입니다.

Java

        list.add(null);
list.add("A");
list.add("A");

모두 정상입니다.

순회 중 ConcurrentModificationException 이 나는 이유

소스의 modCount 와 관련이 있습니다.

ArrayList 계층에는 protected transient int modCount = 0; 가 있습니다.

add/remove/clear 같은 구조적 변경이 일어나면 보통 modCount 가 증가합니다. 이터레이터 생성 시점에 int expectedModCount = modCount; 를 저장합니다.

이후 순회할 때마다 현재 modCount 와 expectedModCount 를 비교하고, 다르면 ConcurrentModificationException 을 던집니다.

이것이 fail-fast 메커니즘입니다. 스레드 안전을 보장하려는 것이 아니라 잘못된 사용을 빨리 드러내기 위한 장치입니다.

Java

        for (String s : list) {
    if (s.equals("A")) {
        list.remove(s);
    }
}

향상된 for는 내부적으로 이터레이터를 사용하므로, 순회 중 리스트 본체를 직접 수정하면 즉시 예외가 납니다.

Iterator.remove 는 이터레이터 상태와 expectedModCount 를 함께 갱신하기 때문에 허용됩니다.

왜 ArrayList는 스레드 안전하지 않은가

대부분 연산에 락이 없습니다.

예를 들어 두 스레드가 동시에 다음을 실행하면:

Java

        list.add("A");
list.add("B");

add 내부에는

size 읽기
용량 확인
배열 쓰기
size++

가 포함되며, 이 단계들은 원자적이지 않습니다. 동시 실행 시 덮어쓰기, size 꼬임, 범위 초과, 데이터 유실이 발생할 수 있습니다.

toArray가 의미 있는 이유

ArrayList 내부가 배열이라고 해도, 내부 배열을 그대로 노출하지 않는 이유는 다음과 같습니다.

내부 용량이 실제 요소 수보다 클 수 있음
직접 노출하면 캡슐화가 깨짐

그래서 toArray() 는

유효 요소만 담은 새 배열 복사본을 반환하고
외부에서 내부 저장소를 직접 건드리지 못하게 합니다.

이해를 위한 간단한 ArrayList 구현

Java

        class MyArrayList<E> {
    private Object[] data = new Object[10];
    private int size = 0;

    public void add(E e) {
        if (size == data.length) {
            grow();
        }
        data[size++] = e;
    }

    public E get(int index) {
        checkIndex(index);
        return (E) data[index];
    }

    public E remove(int index) {
        checkIndex(index);
        E oldValue = (E) data[index];
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        data[--size] = null;
        return oldValue;
    }

    private void grow() {
        int newCapacity = data.length + (data.length >> 1);
        Object[] newData = new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException();
        }
    }
}

접기

시간 복잡도

인덱스 접근: O(1) 배열 기반이라 바로 접근 가능
끝 삽입: 분할상환 O(1) 대부분 끝에 바로 추가, 확장 시에는 복사로 O(n)
중간 삽입: O(n) 뒤 요소들을 오른쪽으로 이동해야 함
중간 삭제: O(n) 뒤 요소들을 왼쪽으로 당겨야 함
값 검색: O(n) 보통 선형 탐색 필요

정리하면 ArrayList의

장점: 인덱스 조회가 빠르고 끝 삽입도 효율적

단점: 중간 삽입/삭제가 느림

Fonnpo

Spring 프레임워크 완전 가이드

HashMap 상세 분석

LinkedList 상세 분석