[ Java ] ArrayList의 add() 메서드는 정말 O(1)일까?

자바로 타닥타닥 하다 보면, ArrayList를 정말 자주 사용하게 됩니다.

 

그런데 문득 이런 생각이 들지 않나요?

"ArrayList.add()의 시간복잡도가 O(1)이라고 하는데, 배열이 꽉 차면 크기를 늘려야 하잖아? 그럼 그때는 O(n)이 아닌가?"

(나만 궁금한가..)

 

흠.. 좀 더 알아보겠습니다

 ArrayList의 내부 동작 살펴보기

먼저 ArrayList가 어떻게 동작하는지 간단히 뜯어보겠씁니다!

 

 

public class ArrayList<E> extends AbstractList<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private Object[] elementData;
    private int size;
    
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 용량 체크
        elementData[size++] = e;           // 요소 추가
        return true;
    }
    
    private void ensureCapacityInternal(int minCapacity) {
        if (minCapacity > elementData.length) {
            grow(minCapacity);  // 배열 크기 증가!
        }
    }
    
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);  // 1.5배 증가
        elementData = Arrays.copyOf(elementData, newCapacity);  // O(n) 연산!
    }
}

 

( 해당 부분은 모든 부분이 아닙니다! 필요한 부분만 제가 뽑아왔습니다! 직접 ArrayList 타고 들어가서 보시는걸 추천드립니다 ! )

 

간단하게 설명해드리자면, add 연산을 수행하고자 하면, 먼저 용량을 체크합니다.

용량이 부족하다면, grow를 하는데 이전 용량의 1.5배를 해서 새롭게 만듭니다!

 

왜 1.5배냐?

 

oldCapacity >> 1을 더하기 때문입니다.

 

예를 들어, oldCapacity가 8이라고 가정한다면, 이진수로 00001000입니다. 이걸 오른쪽으로 1비트 시프트하면, 00000100이 되죠. 해당 값은 4입니다. 즉, 이전값의 절반을 기존값에 추가로 더하는 행위가 되겠습니다.

 

우리가 주의 깊게 봐야하는 점은 아래와 같습니다!

핵심 포인트:

- 일반적인 경우: 그냥 배열에 요소 추가 → O(1)
- 배열이 꽉 찬 경우: 새 배열 생성 + 기존 요소 복사 → O(n)

 

이 두 경우를 잘 생각하시고, 아래 예제를 한 번 봐보시면 될 것 같습니다.

 

실제 동작 시나리오

10개 요소를 추가하는 과정을 살펴보겠습니다

ArrayList<String> list = new ArrayList<>();  // 초기 용량: 10

// 1~10번째 add(): 각각 O(1)
for (int i = 1; i <= 10; i++) {
    list.add("item" + i);  // 단순히 배열에 추가
}

// 11번째 add(): O(n) - 배열 크기 증가!
list.add("item11");  // 10 → 15로 확장, 기존 10개 요소 복사

// 12~15번째 add(): 각각 O(1)
for (int i = 12; i <= 15; i++) {
    list.add("item" + i);
}

// 16번째 add(): O(n) - 다시 배열 크기 증가!
list.add("item16");  // 15 → 22로 확장, 기존 15개 요소 복사

시간복잡도 분석

 

상각 분석(Amortized Analysis)

이제 핵심 질문입니다: "N번의 add() 연산을 수행했을 때 전체 시간복잡도는?"

 

??? : 너 ! 핵심을 찔렀어 !

계산 과정

// N번 add() 연산의 총 비용 계산
총 비용 = 일반 add() 비용 + 배열 확장 비용

// 일반 add() 비용: N번 × O(1) = O(N)

// 배열 확장 비용 계산:
// 초기: 10 → 복사 비용 0
// 1번째 확장: 10 → 15, 복사 비용 10
// 2번째 확장: 15 → 22, 복사 비용 15  
// 3번째 확장: 22 → 33, 복사 비용 22
// ...

// 확장 시점에서의 복사 비용 합계
복사 비용 총합 = 10 + 15 + 22 + 33 + ... 
               ≈ 초기값 + (1 + 1.5 + 2.25 + 3.375 + ...)
               < 3N (등비급수 수렴)

총 시간복잡도 = N + 3N = 4N = O(N)

따라서 N번 연산의 평균 시간복잡도는:

 

쉽게 풀어서 정리하자면?

 

add를 N번 할 때, 시간 복잡도는 O(N)이다.

그렇다면? add를 1번을 수행하는 것은? O(N)/N = O(1)이다.

 

하지만, 배열을 확장하는 경우에는 O(N)까지 치솟기 떄문에 전체적으로 보면  Amortized O(1)다 라는 표현을 쓴다.

 

그렇지만, 우리는 그냥 거의 O(1)로 생각하고 쓰면 된다. 최악의 경우인 배열 확장만 쓰는 경우는 거의 발생하지 않는다 라고 보면 되기 때문이다.

 

마지막으로 !

만약 대략적인 크기를 안다면??

 

 List<String> list = new ArrayList<>(expectedSize);  

 

이렇게 하면 배열 확장 자체를 줄일 수 있어서 더 효율적으로 쓸 수 잇따!