[Data Structure] 동적 배열(Dynamic Array)

고정 배열(static array)은 생성 시 크기가 결정되어 선택의 폭이 좁다. 얼마나 많은 요소를 저장할지 미리 알 수 없을 때 동적 배열(dynamic array)이 필요하다. Java에서는 ArrayList와 Vector가 동적 배열의 역할을 하지만, 내부 구조와 성능 특성이 다르다.

이 글에서는 두 클래스의 차이점, 내부 동작 원리, 실무에서의 최적화 전략까지 다룬다. 소스 코드와 실행 결과는 JDK 21 기준으로 확인했다.

---

1. ArrayList와 Vector: 무엇이 같고 무엇이 다른가?

1.1 공통점: 모두 내부적으로 Object[] 배열 사용

ArrayList와 Vector는 모두 안쪽에 Object[] elementData라는 필드(클래스 안에 든 변수)를 하나 들고 있고, 요소는 이 배열에 담긴다. 배열 자체는 자바의 보통 배열이라 크기가 고정이다. 무엇이 “동적”이냐 하면, 배열이 꽉 찬 상태에서 요소를 더 넣으려 하면 더 큰 배열을 new로 새로 만들고(이걸 “할당한다”고 한다) 기존 요소를 거기로 복사한 뒤, elementData가 새 배열을 가리키게 바꿔 끼운다. 바깥에서 보면 리스트가 저절로 커지는 것처럼 보이는 것이다.

graph TB A["ArrayList / Vector"] B["Object[] elementData
(내부 배열)"] C["int size
(현재 요소 개수)"] D["용량 = elementData.length
(따로 필드가 없다)"] A --> B A --> C B --> D style A fill:#4a90e2,stroke:#357abd,stroke-width:2px,color:#fff style B fill:#50c878,stroke:#2d7a4a,stroke-width:2px,color:#fff style C fill:#f39c12,stroke:#a86904,stroke-width:2px,color:#fff style D fill:#e74c3c,stroke:#a93226,stroke-width:2px,color:#fff

size는 실제로 들어 있는 요소 개수이고, 용량(capacity) 은 내부 배열의 칸 수, 즉 elementData.length다. 용량을 담는 필드가 따로 있는 게 아니다. 그래서 size는 늘 용량보다 작거나 같고, 둘의 차이가 아직 비어 있는 칸이다.

1.2 주요 차이점: 동기화와 성장률

ArrayList와 Vector의 가장 큰 차이는 동기화 여부다. 동기화란 여러 스레드가 같은 데이터를 동시에 건드려도 값이 꼬이지 않도록, 한 번에 하나의 스레드만 건드리게 순서를 맞추는 것이다. Vector는 모든 메서드에 이 동기화를 걸어 두어서 여러 스레드가 동시에 접근해도 안전하지만, 스레드가 하나뿐인 평소 상황에서도 매번 순서를 맞추는 비용, 즉 자물쇠를 걸고 푸는 데 드는 추가 비용(락 오버헤드)을 치른다. 반대로 ArrayList는 동기화를 걸지 않아서 빠르지만, 멀티스레드 환경에서 여러 스레드가 동시에 값을 바꾸면 결과가 꼬일 수 있다. 아래 표는 이 차이를 포함해 두 클래스를 비교한 것이다.

특성	ArrayList	Vector
동기화	비동기화 (Unsynchronized)	전체 메서드 동기화 (Synchronized)
성장률	1.5배 (newCap = old + (old » 1))	기본 2배. 생성자에서 capacityIncrement를 주면 그 수만큼씩 늘린다
기본 초기 용량	10 (첫 add 시)	10
성능 (단일 스레드)	빠름	느림 (락 오버헤드)
멀티스레드 안전	아님	함 (낮은 확장성)
도입 시기	JDK 1.2 (컬렉션 프레임워크)	JDK 1.0 (레거시)

표의 말 몇 개를 풀면 이렇다.

• old >> 1의 >>는 오른쪽 시프트 연산자다. 양수에서 old >> 1은 old / 2의 몫과 같아서, old + (old >> 1)은 “지금 크기에 절반을 더한다”, 즉 1.5배다.
• capacityIncrement는 Vector 생성자 new Vector<>(초기 용량, capacityIncrement)의 두 번째 인자다. 0보다 크게 주면 배열이 찰 때마다 그 수만큼 칸을 늘리고, 주지 않으면(0이면) 지금 용량만큼 더해서 2배가 된다. JDK 소스(Vector.grow)가 capacityIncrement > 0 ? capacityIncrement : oldCapacity만큼 늘리고, 실제로 기본 Vector에 11개를 넣으면 용량이 10에서 20이 된다.
• “낮은 확장성”의 확장성은 스레드를 늘렸을 때 그만큼 빨라지는 정도다. Vector는 메서드마다 한 번에 한 스레드만 들어가게 막으므로, 스레드를 늘려도 서로 기다리는 시간만 늘고 빨라지지 않는다.
• 기본 초기 용량의 “첫 add 시”: new ArrayList<>()로 만든 직후의 ArrayList는 0칸짜리 빈 배열을 들고 있다가, 처음 add할 때 10칸 배열을 만든다(JDK 소스의 grow가 이 경우 Math.max(10, 필요한 칸 수)로 만든다). Vector는 만들 때 바로 10칸을 만든다.
• JDK 1.0, 1.2는 자바 개발 도구 묶음인 JDK의 버전 번호다. Vector는 첫 버전부터 있었고, ArrayList는 1.2에서 리스트·맵 같은 자료구조를 한 체계로 정리한 컬렉션 프레임워크와 함께 들어왔다. 레거시는 “옛날에 만들어져 호환 때문에 남아 있는 것”이라는 뜻이다.

---

2. ArrayList의 내부 동작: 용량 확장 메커니즘

2.1 성장률 1.5배의 의미

ArrayList가 추가할 요소를 위한 공간이 없을 때, grow() 메서드가 호출되어 현재 용량의 1.5배로 확장한다.

초기 상태: capacity = 10
1번째 확장: capacity = 10 + (10 >> 1) = 15
2번째 확장: capacity = 15 + (15 >> 1) = 22
3번째 확장: capacity = 22 + (22 >> 1) = 33
...

15 >> 1은 15를 2로 나눈 몫 7이라서 22가 된다. 소수점이 버려지니 정확히 1.5배가 아니라 1.5배에 가까운 값이다. 실제로 빈 ArrayList에 하나씩 넣어 보면 용량이 10, 15, 22, 33, 49 순서로 커진다.

왜 1.5배일까?

• 2배(Vector의 기본값)보다는 메모리 낭비가 적다. 막 늘린 직후를 보면, 2배로 늘리면 새 배열의 절반 가까이가 비어 있고, 1.5배로 늘리면 3분의 1 정도가 비어 있다(늘어난 몫 0.5를 전체 1.5로 나눈 값).
• 동시에 리사이징(배열을 더 큰 것으로 새로 만들어 기존 요소를 복사하는 일) 횟수도 적절히 제어한다. 배열을 복사할 때마다 들어있는 요소를 전부 옮겨야 해서 비용이 O(n)이다 — 리사이징 횟수를 줄이면 이 복사 오버헤드도 함께 줄어든다.
• 매번 같은 배수로 곱해 커지는 성장(기하급수적 성장)이라서, 요소를 n개 넣는 동안 복사하는 총량이 n에 일정한 수를 곱한 값을 넘지 않는다: 총 복사량 ≤ 3n. 왜 3인지는 2.2에서 따라간다.

아래 그림은 add를 부를 때 ArrayList 안에서 일어나는 순서다(JDK 21 소스 기준).

graph TD A["사용자가 add 호출"] --> B["size == elementData.length?
(배열이 꽉 찼나)"] B -->|Yes| C["grow 호출"] B -->|No| H["빈 칸에 요소 추가"] C -->|"newCap = oldCap + (oldCap>>1)"| E["새 배열 할당"] E -->|Arrays.copyOf| F["기존 요소 복사
O(n) 비용"] F -->|elementData가 새 배열을 가리킴| G["새 배열로 교체"] G --> H

add는 먼저 배열이 꽉 찼는지(size가 배열 칸 수와 같은지) 본다. 아직 빈 칸이 있으면 바로 넣고 끝이다. 꽉 찼으면 grow가 1.5배 크기의 새 배열을 만들고 Arrays.copyOf로 기존 요소를 복사한다(Arrays.copyOf는 안에서 System.arraycopy로 복사한다). 그다음 elementData 필드에 새 배열의 참조를 넣는다. 이제 필드가 새 배열을 가리키므로 옛 배열은 아무도 안 쓰게 되고, 그 빈 칸에 요소를 넣는다.

2.2 복사 비용 분석

동적 배열이 n개의 요소를 추가할 때, 1.5배 성장으로 인한 총 복사 횟수를 추정할 수 있다.

기하급수적 성장의 총 이동량 (상한값):

\[\text{총 복사량} \approx \sum_{i=0}^{k-1} 10 \cdot 1.5^i \le 3n, \quad k \approx \log_{1.5}(n/10)\]

즉, 각 요소가 많아야 평균 3번쯤 복사된다. 실제로 빈 ArrayList에 100만 개를 넣으면서 옮겨진 요소 수를 모두 더해 보니 약 243만 개, 요소 하나당 2.43번이었다.

이 식을 한 줄씩 따라가면:

• Σ(시그마)는 “뒤에 오는 값을 전부 더한다”는 기호다. i를 0부터 k-1까지(리사이징 k번) 하나씩 늘려가며 나오는 값을 모두 더하라는 뜻이다.
• k ≈ $\log_{1.5}(n/10)$은 “10에서 시작해 1.5배씩 몇 번 곱해야 n이 되는가”를 뜻한다(로그의 밑이 2가 아니라 1.5인 경우다). 용량이 1.5배씩 커지면서 n에 도달할 때까지 걸리는 리사이징(배열을 새로 만들어 복사하는 일) 횟수가 바로 이 값이다.
• $10 \cdot 1.5^i$는 i번째 리사이징이 일어난 시점의 용량이고, 그 시점에 복사해야 하는 요소 수와 같다(꽉 찼을 때만 늘리니까 용량 = 들어 있는 요소 수다). 실제로는 소수점을 버리므로 22.5가 아니라 22, 50.6이 아니라 49처럼 조금씩 작다. 그래서 식 전체가 대략값(≈)이다.
• 그러니까 이 식 전체는 “리사이징이 일어날 때마다 그 시점의 용량만큼 복사하고, 그 복사량을 전부 더하라”는 뜻이다. 왜 3인지는 마지막 항부터 거꾸로 보면 나온다. 마지막 복사량을 L이라 하면 그 앞은 L의 2/3(1.5로 나눈 값), 그 앞은 다시 2/3인 4/9, … 이다. 그래서 합은 L × (1 + 2/3 + 4/9 + 8/27 + …)이고, 괄호 안은 1, 1.67, 2.11, 2.41, … 로 더할수록 커지지만 3에 다가갈 뿐 3을 넘지 않는다(남은 몫이 매번 3분의 1로 줄어서다). 즉 총 복사량은 마지막 항의 3배를 넘지 않는다. 마지막 항은 n보다 작으므로, 전체 삽입 n번에 대해 총 복사량이 3n 정도를 넘지 않는다.

구체적 예시:

• 용량 예약 없이 1,000,000개 추가: ~30회 리사이징 (각 O(n)). 재 보니 처음 10칸 배열을 만드는 것까지 세어 30회였다.
• ensureCapacity로 미리 할당: 큰 배열을 1회 새로 만든다. 빈 리스트에서 부르면 옮길 요소가 0개라 복사는 일어나지 않는다.
• 생성자로 초기 용량 지정 (new ArrayList<>(1_000_000)): 리사이징 0회 (가장 빠름). 빈 리스트에 ensureCapacity를 부른 것과 하는 일(그 크기의 배열을 한 번 만든다)은 같다.

---

3. ensureCapacity와 trimToSize: 실무 최적화 도구

3.1 ensureCapacity: 대량 삽입 전 용량 미리 확보

대량의 요소를 한 번에 추가할 예정이면, ensureCapacity로 미리 용량을 확보한다.

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

// 미리 용량 확보 (100만 칸짜리 배열을 한 번에 만든다)
list.ensureCapacity(1_000_000);

// 이후 추가 시 리사이징 없음
for (int i = 0; i < 1_000_000; i++) {
    list.add(i);
}

// 성능: 약 2배 이상 빠름 (리사이징 오버헤드 제거) — 이 수치는 재 보지 않았다

숫자 사이의 _는 자릿수를 읽기 쉽게 끊는 표기라 1_000_000은 1000000과 같다.

원리:

• ensureCapacity(minCapacity)를 호출하면, 현재 용량이 minCapacity보다 작으면 grow(minCapacity)가 호출된다. 2.1의 grow()와 같은 이름인데, JDK 소스에서 인자 없는 grow()는 grow(size + 1), 즉 “한 칸만 더 있으면 된다”로 부르는 줄임 버전이다.
• 충분한 크기의 배열이 한 번에 할당되므로 이후 리사이징이 발생하지 않는다.
• 이미 요소가 들어 있는 리스트라면 그 요소들을 한 번 복사한다. 리사이징이 여러 번 나눠 하던 복사가 많아야 1회로 줄어든다.

3.2 trimToSize: 메모리 정리

리스트에 데이터를 대량으로 적재한 후, 거의 읽기만 할 예정이면 trimToSize로 초과 용량을 제거한다.

ArrayList<Integer> list = new ArrayList<>();
list.ensureCapacity(1_000_000);
// ... 대량 삽입 (50만 개만 들어왔다) ...
list.size(); // 500_000 (실제 요소)

// 초과 용량 제거 (메모리 절약)
list.trimToSize();
// 내부 배열 크기: 1_000_000 → 500_000

// 읽기 전용으로 감싸기
List<Integer> readOnly = Collections.unmodifiableList(list);

한 줄씩 따라가기:

• 100만 칸을 확보했는데 실제로는 50만 개만 들어온 상황이다. 남은 50만 칸은 비어 있다.
• trimToSize()는 50만 칸짜리 배열을 새로 만들어 요소를 옮기고, 100만 칸짜리 옛 배열을 버린다. 실행해 보면 배열 크기가 정말 500,000이 된다.
• Collections.unmodifiableList(list)는 리스트를 복사하지 않고 “고치는 메서드를 부르면 예외를 던지는 겉포장”을 씌워 돌려준다. readOnly.add(...)를 부르면 UnsupportedOperationException이 난다. 다만 포장일 뿐이라 원래 list는 여전히 고칠 수 있고, 고치면 readOnly로 읽어도 바뀐 값이 보인다. 실제로 list.add(9)를 하고 readOnly를 찍으면 9가 들어 있다. 진짜 읽기 전용으로 쓰려면 원래 list를 더 건드리지 않아야 한다.

trimToSize는 내부 배열의 크기를 실제 요소 개수에 맞춰 줄인다. 자바에서 new로 만든 배열이나 객체는 힙 메모리라는 공간에 들어가는데, 배열 칸이 줄면 그만큼 힙을 덜 쓰게 되고, 더는 쓰지 않는 객체의 자리를 되찾는 GC가 훑어야 할 칸도 함께 줄어든다.

성능 트레이드오프(얻는 것과 잃는 것):

• 장점: 내부 배열이 차지하는 힙이 줄어든다(위 예시에서는 칸 수가 절반이 됐다), GC가 훑을 배열 칸 감소
• 단점: 이후 추가 삽입 필요 시 다시 리사이징 발생

---

4. 실무 시나리오별 최적화 전략

4.1 시나리오 1: 최종 크기를 아는 경우

// Case 1: 생성자에서 정확한 크기 지정 (가장 빠름)
List<Integer> listA = new ArrayList<>(1_000_000);
for (int i = 0; i < 1_000_000; i++) {
    listA.add(i);
}

// Case 2: ensureCapacity 사용
ArrayList<Integer> listB = new ArrayList<>();
listB.ensureCapacity(1_000_000);
// ... 삽입 로직 ...

비용:

• 생성자: 100만 칸 배열을 처음에 한 번 만든다. 이후 리사이징 0회, 복사 0회
• ensureCapacity: 빈 리스트에서 부르면 100만 칸 배열을 한 번 만든다. 옮길 요소가 없어 복사 0회이고, 이후 리사이징 0회다. 이미 요소가 든 리스트라면 그 요소를 한 번 복사한다

빈 리스트라면 둘이 하는 일은 같다. ensureCapacity는 리스트가 이미 만들어져 있어서 생성자를 고를 수 없을 때(예: 다른 메서드가 만들어 넘겨준 리스트) 쓴다.

---

4.2 시나리오 2: 최종 크기를 모르는 경우 (안전 버퍼 전략)

여기서 버퍼는 “혹시 몰라 더 잡아 두는 여유분”이다. 예상 평균 크기가 있을 때, 10~20% 과할당으로 리사이징 횟수를 줄이면서 메모리 낭비를 최소화한다.

// 예상 크기: 1,000,000개 (실제로는 이보다 많을 수도 적을 수도 있다)
int estimatedSize = 1_000_000;
int safeBuffer = (int)(estimatedSize * 1.2); // 20% 과할당

ArrayList<Integer> list = new ArrayList<>();
list.ensureCapacity(safeBuffer); // 1,200,000으로 미리 확보

// 데이터 적재 — data는 들어올 데이터를 담은 배열, actualSize는 실제로 들어온 개수라고 하자
for (int i = 0; i < actualSize; i++) {
    list.add(data[i]);
}

// 메모리 정리
list.trimToSize();

한 줄씩 따라가기:

• estimatedSize * 1.2는 double 값이라 (int)로 정수로 바꾼다. 예상보다 20% 넉넉한 120만이 된다.
• ensureCapacity(safeBuffer)로 120만 칸 배열을 미리 만든다. 빈 리스트라 복사는 없다.
• 반복문이 실제로 들어온 actualSize개를 넣는다. 120만 개 이하면 리사이징이 한 번도 안 일어난다.
• 다 넣은 뒤 trimToSize()로 남은 칸을 정리한다(3.2).

효과:

• 메모리 낭비: 20% (예측 가능, 관리 가능). 끝에 trimToSize를 하면 그것도 돌려받는다
• 리사이징 횟수: 1회 이하 (대부분 0회). 120만을 넘어야 한 번 일어나고, 그때 1.5배인 180만 칸이 되므로 두 번째는 180만을 넘을 때까지 없다
• 총 복사 비용: 버퍼 안에 들면 0, 넘쳐도 120만 개를 한 번 복사하는 약 1.2n이다 (예약 없을 때의 3n 대비 60% 절감). 여기서 n은 예상 크기 100만이다. 넘쳤다는 건 실제로 120만 개보다 많이 넣었다는 뜻이라, 예약 없이 넣었을 때의 상한은 3n보다 크다 — 60%는 줄여 잡은 값이다

---

4.3 시나리오 3: 배치 단위 적재

데이터가 배치(batch, 여러 개를 한 묶음으로 모은 것)로 들어올 때, 각 배치 도착 시점에 용량을 동적으로 조정한다.

ArrayList에는 지금 용량을 알려주는 메서드가 없다(capacity()는 Vector에만 있고, ArrayList에 쓰면 컴파일 에러가 난다). 그래서 내가 확보해 둔 용량을 reserved라는 변수로 직접 기억한다.

ArrayList<Integer> list = new ArrayList<>();
int reserved = 0; // 지금까지 ensureCapacity로 확보한 칸 수

// 배치별 적재 — moreDataAvailable · readBatchSize · readData는
// 데이터를 읽어 오는 가상의 메서드다(남은 배치가 있나 / 이번 배치 개수 / 요소 하나)
while (moreDataAvailable()) {
    int batchSize = readBatchSize();
    
    // 이번 배치를 더하면 확보한 용량의 70%를 넘을 때 미리 확장
    if (list.size() + batchSize > reserved * 0.7) {
        reserved = reserved + batchSize + 10_000; // 배치 크기 + 마진
        list.ensureCapacity(reserved);
    }
    
    // 배치 추가
    for (int i = 0; i < batchSize; i++) {
        list.add(readData());
    }
}

// 완료 후 메모리 정리
list.trimToSize();

한 줄씩 따라가기:

• while은 읽을 배치가 남아 있는 동안 돈다. 한 바퀴가 배치 하나다.
• if는 “지금 든 개수 + 이번 배치 개수”가 확보한 칸의 70%를 넘는지 본다. 넘으면 꽉 차기 전에 미리 넓힌다.
• 넓힐 때는 지금 확보량에 이번 배치 크기와 여유분 1만 칸을 더한 만큼으로 ensureCapacity를 부르고, 그 값을 reserved에 기억한다. 70%와 1만은 이 예시에서 정한 값이고, 재서 고른 값은 아니다.
• 안쪽 for가 배치 안의 요소를 하나씩 넣는다. 미리 넓혀 두었으니 여기서는 리사이징이 일어나지 않는다.
• 모든 배치가 끝나면 trimToSize()로 여유분을 정리한다.

---

4.4 시나리오 4: 병렬 적재 (멀티스레드)

여러 스레드에서 동시에 데이터를 수집한 뒤, 단일 스레드에서 병합한다.

아래 코드에 나오는 executor는 스레드 풀이다. 스레드를 미리 여러 개 만들어 두고 빌려 쓰는 곳으로, executor.submit(작업)은 괄호 안의 작업을 스레드 풀에서 꺼낸 스레드 하나에게 맡겨서 지금 코드와 동시에 돌리라는 뜻이다. 여기서는 스레드 수만큼 이 작업을 반복해서 맡기는데, 각 작업이 threadLists.get(threadId)로 자기 전용 리스트에만 데이터를 쌓기 때문에 스레드끼리 같은 데이터를 건드리지 않는다 — 그래서 동기화가 필요 없다.

int numThreads = 4;
ExecutorService executor = Executors.newFixedThreadPool(numThreads);

// 스레드별 리스트 생성
List<ArrayList<Integer>> threadLists = new ArrayList<>();
for (int i = 0; i < numThreads; i++) {
    threadLists.add(new ArrayList<>());
}

// 각 스레드에서 독립적으로 데이터 적재 (동기화 불필요)
for (int t = 0; t < numThreads; t++) {
    int threadId = t;
    executor.submit(() -> {
        ArrayList<Integer> threadList = threadLists.get(threadId);
        for (int i = 0; i < 1_000; i++) {
            threadList.add(threadId * 1_000 + i);
        }
    });
}

// 모든 스레드 완료 대기 (InterruptedException을 던질 수 있다)
executor.shutdown();
executor.awaitTermination(1, TimeUnit.MINUTES);

// 단일 스레드에서 최종 리스트 생성
ArrayList<Integer> finalList = new ArrayList<>();
int totalSize = 0;
for (ArrayList<Integer> tl : threadLists) {
    totalSize += tl.size();
}

// 한 번에 충분한 용량 확보 후 병합
finalList.ensureCapacity(totalSize);
for (ArrayList<Integer> tl : threadLists) {
    finalList.addAll(tl);
}

// 메모리 정리
finalList.trimToSize();

한 줄씩 따라가기:

• Executors.newFixedThreadPool(numThreads)로 스레드 4개짜리 스레드 풀을 만든다.
• threadLists에 스레드 수만큼 빈 ArrayList를 만들어 둔다. 스레드마다 쓸 전용 리스트다.
• 두 번째 for가 작업을 4번 맡긴다. () -> { ... }는 람다로, “이 블록을 실행하는 작업”을 그 자리에서 적어 넘기는 문법이다. 바깥 변수 t는 반복마다 바뀌므로, 람다 안에서는 그 순간의 값을 threadId에 담아 쓴다(자바는 람다 안에서 값이 바뀌는 바깥 변수를 쓰지 못하게 한다). 각 작업은 자기 번호의 리스트에만 1,000개를 채운다.
• executor.shutdown()은 “더 이상 새 작업은 받지 않는다”는 뜻이고, executor.awaitTermination(1, TimeUnit.MINUTES)은 “지금 돌고 있는 작업이 다 끝날 때까지 최대 1분 여기서 기다린다”는 뜻이다. 즉 모든 스레드가 자기 몫을 다 채울 때까지 멈춰서 기다리는 줄이다. 1분 안에 다 끝나면 true, 시간이 다 되도록 안 끝나면 false를 돌려주고 그냥 다음 줄로 넘어간다(이 예시는 반환값을 확인하지 않는다). 기다리는 도중 끊기면 InterruptedException이 나므로, 이 코드를 담은 메서드는 throws InterruptedException을 붙이거나 try/catch로 감싸야 한다.
• 모든 스레드가 끝나면 각 리스트의 크기(tl.size())를 더해 전체 크기(totalSize)를 구한다.
• finalList.ensureCapacity(totalSize)로 최종 리스트의 용량을 미리 한 번에 확보한 뒤, addAll로 스레드별 리스트를 하나로 합친다. 용량을 미리 확보했기 때문에 합치는 동안 리사이징이 일어나지 않는다. 실행해 보면 finalList에 4,000개가 들어 있다.
• 마지막으로 trimToSize()로 다 쓰고 남은 용량을 정리한다.

장점:

• 리사이징 충돌 회피 (각 스레드는 독립적). 한 ArrayList를 여러 스레드가 같이 늘리다 1.2에서 말한 것처럼 값이 꼬이는 일이 없다
• 최종 병합 때 배열을 한 번만 만들고, 합치는 동안 리사이징은 없다
• 불필요한 동기화 없음 (확장성 우수)

---

5. ArrayList vs Vector: 언제 어떤 것을 쓸까?

5.1 ArrayList를 쓰는 경우 (대부분의 상황)

기본 선택지다.

// 네 가지 예를 한곳에 모았다. 각각 따로 쓰는 코드다.
// data는 이미 있는 List<String>이라고 하자.

// 1. 단일 스레드 환경
List<String> names = new ArrayList<>();

// 2. 멀티스레드지만 외부 동기화로 제어
List<String> sharedNames = new ArrayList<>();
Lock lock = new ReentrantLock();
lock.lock();
try {
    sharedNames.add("kim");
    sharedNames.add("lee");
} finally {
    lock.unlock();
}

// 3. 읽기 전용 버전 필요
List<String> immutable = Collections.unmodifiableList(new ArrayList<>(data));

// 4. 복사 기반 동시성 필요
List<String> copyOnWrite = new CopyOnWriteArrayList<>(data);

번호별로 무엇을 하는 코드인지 보면:

• 1번은 스레드가 하나뿐이라 애초에 동기화가 필요 없는 경우다.
• 2번은 스레드가 여럿이지만, ArrayList 자체의 동기화 대신 내가 직접 자물쇠를 걸어 제어하겠다는 뜻이다. Lock은 자바가 제공하는 자물쇠의 설계도(인터페이스)이고, ReentrantLock은 그걸 실제로 구현한 클래스다. 리스트를 건드리기 전에 lock.lock()으로 잠그고 다 쓴 뒤 lock.unlock()으로 풀어서(중간에 예외가 나도 꼭 풀리도록 finally에 둔다), 한 번에 한 스레드만 접근하게 만든다. Vector처럼 메서드 하나하나에 자동으로 자물쇠가 걸리는 게 아니라, 여러 메서드 호출을 한 덩어리로 묶어 한 번만 잠그는 식으로 더 세밀하게 제어할 수 있다는 뜻이다.
• 3번은 new ArrayList<>(data)로 복사본을 먼저 만들고 그걸 읽기 전용 포장(3.2)으로 감싼다. 복사본은 이 포장 말고는 아무도 들고 있지 않으니 더는 바뀌지 않고, 여러 스레드가 동시에 읽기만 하므로 동기화가 필요 없다.
• 4번은 CopyOnWriteArrayList를 쓰는 경우다. 이건 ArrayList가 아니라 같은 List 인터페이스를 구현한 다른 클래스인데, Vector 대신 고를 수 있는 선택지라 여기 같이 적었다. 이 리스트는 쓰기(추가·삭제)가 일어날 때마다 내부 배열을 통째로 복사해서 바꿔치기하기 때문에, 읽는 스레드는 동기화 없이도 항상 안전한 배열을 본다. 쓰기가 드물고 읽기가 훨씬 많은 상황에 맞는다.

이유:

• 락 오버헤드 없음 (빠름)
• 외부 동기화로 세밀한 제어 가능 (확장성)
• 메모리 효율적 (1.5배로 늘리니 늘린 직후 빈 칸이 2배인 Vector보다 적다, 2.1)

5.2 Vector를 쓰는 경우 (거의 없음)

레거시 호환이 필요한 경우에만.

// 아주 오래된 API(다른 코드가 불러 쓰도록 열어 둔 메서드)와의 호환성 때문에 Vector를 받아야 한다
/**
 * @deprecated List를 받는 새 메서드 processData(List) 를 쓴다
 */
@Deprecated
void processData(Vector<String> data) {
    // 기존 코드...
}

이 메서드는 옛 코드가 Vector를 넘기기 때문에 남겨 두지만, 새 코드는 쓰지 말라고 @Deprecated를 붙였다. @Deprecated는 괄호 안에 설명 문자열을 받지 않는다(@Deprecated("...")라고 쓰면 컴파일 에러가 난다). 그래서 “대신 무엇을 쓰라”는 말은 위의 주석 @deprecated 태그에 적었다. /**로 시작하는 주석은 Javadoc 주석이라고 해서, 보통 주석과 달리 API 문서로 뽑히고, 그 안의 @deprecated가 문서의 “쓰지 말라” 설명 자리가 된다.

왜 추천하지 않나?

• 모든 메서드가 synchronized → 락 경합 비용 높음. 락 경합은 여러 스레드가 같은 자물쇠를 잡으려고 줄을 서서 기다리는 것이다
• capacityIncrement 정책도 대부분 필요 없음 (늘릴 크기를 정하고 싶으면 ensureCapacity로 그때그때 정하면 된다)
• ArrayList + 외부 동기화가 훨씬 효율적. 필요한 구간만 잠글 수 있기 때문이다(얼마나 빠른지는 재 보지 않았다)

---

6. 성장률 1.5배의 복사 비용 추정 및 의사결정

6.1 예측 불가능한 크기에서의 전략

3단계 의사결정:

Step 1: 최댓값을 추정할 수 있는가?
  ├─ Yes → ensureCapacity(추정한 최댓값) + add + trimToSize
  └─ No  → Step 2

Step 2: 예상 평균값 * 1.2를 과할당할 여유가 있는가?
  ├─ Yes (메모리 넉넉함) → ensureCapacity(estimatedSize * 1.2)
  ├─ Maybe (빡빡함)      → ensureCapacity(estimatedSize * 1.1)
  └─ No (매우 제약)      → ensureCapacity(estimatedSize)를 과할당 없이 1회

Step 3: (Step 1·2를 정한 뒤) 데이터가 배치로 들어오는가?
  ├─ Yes → 배치마다 용량 체크 및 미리 확장
  └─ No  → 한 번에 다 넣는다

위에서 아래로 한 번 따라가면 된다. 넣을 개수의 최댓값을 짐작할 수 있으면 그만큼 한 번에 확보하고(4.1의 ensureCapacity), 다 넣은 뒤 trimToSize로 남는 칸을 돌려받는다(3.2). 최댓값은 몰라도 평균은 짐작할 수 있으면, 메모리 여유에 따라 평균보다 20%나 10% 넉넉하게, 여유가 전혀 없으면 평균 그대로 확보한다(4.2). 데이터가 묶음으로 띄엄띄엄 들어오면 4.3처럼 묶음마다 확인한다.

6.2 메모리 vs 속도 트레이드오프 표

여기서 리사이징 횟수와 복사 비용은 “이미 든 요소를 새 배열로 옮기는 일”만 센다. 빈 리스트에 처음 배열을 만드는 것은 옮길 것이 없어 세지 않는다.

전략	메모리 낭비	리사이징 횟수	복사 비용	추천 상황
예약 없음	0%	~log1.5(n/10) (100만 개면 약 29회)	3n 이하	메모리 극도로 제약
10% 과할당	~10%	0~1회	0 (넘치면 ~1.1n)	균형잡힌 상황
20% 과할당	~20%	0~1회	0 (넘치면 ~1.2n)	메모리 충분
정확한 예측	0%	0회	0	최적 (가능하면 추천)

“예약 없음”은 ensureCapacity를 아예 부르지 않고 add만 하는 경우다. 메모리 낭비 0%는 처음에 넉넉히 잡아 두지 않는다는 뜻이고, 1.5배로 늘린 직후에는 2.1에서 본 것처럼 빈 칸이 생긴다. 6.1의 “No (매우 제약)”처럼 예상 크기 그대로 한 번 예약하면, 그 크기 안에서는 “정확한 예측” 줄처럼 리사이징이 없다.

---

7. 제거(remove) 연산의 O(n) 비용

ArrayList의 중간 요소 제거 시 뒷부분 전체를 앞으로 이동해야 한다.

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));

// 인덱스 2 제거 (요소 3 제거)
list.remove(2);
// 내부: System.arraycopy(elementData, 3, elementData, 2, 2)
// 옮기는 요소: 4와 5, 2개 (size - index - 1 = 5 - 2 - 1)

한 줄씩 따라가기:

• Arrays.asList(1, 2, 3, 4, 5)는 1부터 5까지 든 리스트를 만들고, new ArrayList<>(...)가 그 내용을 복사해 고칠 수 있는 ArrayList로 만든다.
• list.remove(2)의 2는 값이 아니라 인덱스다. ArrayList에는 인덱스를 받는 remove(int)와 값을 받는 remove(Object)가 둘 다 있는데(오버로딩), 2는 int라서 remove(int)가 불린다. 그래서 인덱스 2에 있는 요소 3이 지워지고 결과는 [1, 2, 4, 5]다. 값 2를 지우고 싶으면 list.remove(Integer.valueOf(2))처럼 객체로 넘긴다.
• 지운 자리를 메우려고 System.arraycopy가 인덱스 3부터 2칸(4와 5)을 인덱스 2 자리로 당긴다. 그다음 맨 끝 칸을 비우고(null) size를 하나 줄인다.
• 옮기는 칸 수는 지운 자리 뒤에 남은 요소 수다. 앞쪽을 지울수록 많아지고, 맨 앞을 지우면 n-1개를 전부 당긴다. 그래서 O(n)이다.

성능 특성:

연산	복잡도	이유
add(size, element)	평균 O(1)	맨 뒤에만 추가. 꽉 찼을 때 한 번은 O(n) 복사가 들지만 평균을 내면 O(1)이다(상각)
add(0, element)	O(n)	전체를 뒤로 밀어야 함
remove(size-1)	O(1)	맨 뒤만 제거
remove(0)	O(n)	전체를 앞으로 당겨야 함

LinkedList를 선택할 기준:

• 중간/앞쪽 위치에서의 빈번한 삽입/삭제 필요 → LinkedList(연결 리스트) 고려. 다만 끼울 위치까지 앞에서부터 하나씩 따라가야 하므로, 그 위치를 이미 쥐고 있을 때(예: 반복하면서 지울 때) 이득이 난다
• 무작위 접근(get(i)처럼 인덱스로 아무 위치나 바로 읽는 것)과 삭제가 섞여 있음 → ArrayList를 쓰되, 앞쪽·중간을 인덱스로 지우는 remove(i)를 자주 부르지 않게 짠다

---

8. 결론 및 실무 체크리스트

체크리스트

• 최종 크기를 아는가? → 생성자 또는 ensureCapacity(최종 크기) 사용
• 대량 삽입 후 읽기 전용인가? → trimToSize + Collections.unmodifiableList
• 멀티스레드인가? → ArrayList + 외부 Lock, 또는 CopyOnWriteArrayList
• 중간 삽입/삭제가 빈번한가? → LinkedList 고려
• 메모리가 극도로 제약인가? → 과할당 최소화, 다 쌓은 뒤 trimToSize (계속 넣는 중에 줄이면 다시 리사이징이 일어난다, 3.2)
• Vector 사용 중인가? → ArrayList로 옮겨 가는 것(마이그레이션) 검토

성능 개선 우선순위

1. 높음: 크기를 미리 확보한다 — 새로 만드는 리스트면 생성자, 이미 있는 리스트면 ensureCapacity. 100만 개를 넣을 때 복사가 일어나는 리사이징 29회가 0회가 된다
2. 중간: 크기를 정확히 모르면 예측값에 과할당한다 (4.2, 리사이징 0~1회)
3. 낮음: 과할당 비율(10%, 20% 등)을 상황마다 조금씩 바꿔 보는 세밀한 튜닝 (5~10% 개선 — 이 수치는 재 보지 않았다)

---

다음 시간에 읽을 자료:

• 동적 배열의 역순 반복과 캐시 친화성 — 배열이 메모리에 붙어 있어서 CPU 캐시를 잘 쓰는가
• CopyOnWriteArrayList와 멀티스레드 동시성 전략
• 박싱 오버헤드와 원시 배열 래퍼의 대안 — ArrayList<Integer>는 int를 래퍼 클래스 Integer 객체로 감싸 담는데(이렇게 감싸는 것을 박싱이라 한다), 그 비용과, int[] 같은 기본형(원시) 배열을 감싼 리스트를 쓰는 방법

---

자신만의 철학을 만들어가는 중입니다.

---

최상단으로 이동했습니다!