Unit 5.2 — ArrayList 내부 (배열 확장 정책)

F-LAB JAVA · 2주차 · Phase 5 · 컬렉션 프레임워크 내부 구조

---

📌 학습 목표

이 Unit을 끝내면 다음을 답할 수 있어야 한다.

• ArrayList의 내부 데이터 구조는?
• 기본 초기 크기가 10인 이유는?
• 공간 부족 시 1.5배 확장의 정확한 동작은?
• 1.5배인 이유 — 왜 2배도, 3배도 아닌가?
• amortized O(1) 이란 무엇인가?
• 중간 삽입/삭제가 O(n) 인 정확한 이유는?
• new ArrayList<>(1000) 의 진짜 의미와 효과는?

---

🎯 핵심 한 문장

ArrayList = "Object[] 배열을 감싼 동적 컬렉션"이다.
내부는 단순한 배열이지만, 공간 부족 시 1.5배로 새 배열 생성 + 데이터 복사하는 메커니즘이 핵심.
이 메커니즘 덕에 평균 O(1)로 추가 가능하지만, 중간 삽입/삭제는 O(n) 의 메모리 복사 비용을 가진다.

비유 — 자동 확장 책장

시스템	비유
ArrayList	책 10권 들어가는 책장
공간 부족	11번째 책 들어왔는데 자리 없음
1.5배 확장	15권짜리 새 책장 사고 → 10권 옮기고 → 11번째 추가
amortized O(1)	평균적으로는 빠름. 가끔 비싼 작업
중간 삽입	5번 위치에 책 끼우려면 → 5번 이후 모든 책 한 칸씩 밀어내기

---

🧭 9개 섹션 로드맵

1. ArrayList의 내부 — Object[] 배열
2. 기본 크기 10의 의미
3. 1.5배 확장 정책 정밀
4. 1.5배인 이유 — 트레이드오프
5. amortized O(1) 분석
6. 중간 삽입/삭제의 O(n) 비용
7. ILIC 실무 — 초기 크기와 성능
8. 흔한 실수 + 디버깅
9. 면접 질문 + 자기 점검

---

1️⃣ ArrayList의 내부 — Object[] 배열

1.1 핵심 필드

public class ArrayList<E> {
    transient Object[] elementData;     // 실제 데이터 저장
    private int size;                    // 현재 요소 개수
    
    private static final int DEFAULT_CAPACITY = 10;
}

→ ArrayList는 단순한 Object 배열 + 카운터.

1.2 배열의 본질

Object[] elementData:
  ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
  │  │  │  │  │  │  │  │  │  │  │   ← 10칸 (기본 크기)
  └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
   0  1  2  3  4  5  6  7  8  9

ArrayList의 size:
  현재 들어있는 요소 수
  
ArrayList의 capacity:
  배열의 총 크기 (elementData.length)

size ≠ capacity 가 핵심.

1.3 추가 동작 추적

ArrayList<String> list = new ArrayList<>();   // size=0, capacity=10 (lazy)
list.add("A");   // size=1
list.add("B");   // size=2
list.add("C");   // size=3

메모리:

elementData:
  ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
  │A │B │C │  │  │  │  │  │  │  │
  └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
   0  1  2  3  4  ...

size = 3
capacity = 10

get(i):

public E get(int index) {
    return (E) elementData[index];   // 배열 인덱스 직접 접근
}

→ O(1). 매우 빠름.

1.4 Lazy 초기화 — Java 8+

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

DEFAULTCAPACITY_EMPTY_ELEMENTDATA = 빈 배열 (크기 0).

처음 add() 호출 시 비로소 크기 10 배열 생성.

new ArrayList<>() 직후:
  elementData = []  (크기 0)
  size = 0

list.add("A") 호출 후:
  elementData = [A, null, null, ..., null]  (크기 10)
  size = 1

이유:

• 빈 ArrayList가 자주 만들어지는데 사용 안 되면 메모리 낭비
• Lazy 초기화로 절약

1.5 generic이지만 내부는 Object[]

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

내부적으로 Object[] 사용.
컴파일 시점에 제네릭 타입 정보 소거 (Type Erasure).

런타임:
  Object[] elementData = new Object[10];
  
get(0):
  Object obj = elementData[0];
  return (String) obj;   // 컴파일러가 자동 캐스팅

→ Java 제네릭의 한계 (primitive 사용 불가, 배열 생성 어려움).
→ Phase 6에서 Reflection과 함께 더 깊이.

---

2️⃣ 기본 크기 10의 의미

2.1 코드 확인

private static final int DEFAULT_CAPACITY = 10;

왜 10?

2.2 역사적 선택

1998년 Java 1.2 컬렉션 프레임워크 도입 시:
  - Java 1.0/1.1 의 Vector도 기본 10
  - 호환성 + 익숙함 유지
  - 10은 "인간이 다루는 작은 수" 의 자연스러운 선택

2.3 트레이드오프 분석

작은 크기 (예: 4):

• 작은 List 메모리 효율 ↑
• 단점: 자주 사용 시 확장 자주 발생 → 비효율

큰 크기 (예: 100):

• 확장 적음
• 단점: 작은 List에서 메모리 낭비

10:

• 적당한 균형
• 대부분의 작은 List 한 번에 수용
• 메모리 낭비 적음

2.4 실제 데이터

가상 통계:

조사: 일반 Java 앱에서 만들어지는 ArrayList의 크기 분포

크기 0-5:   45%   ← 매우 작은 리스트
크기 6-15:  30%   ← 10에 잘 맞는 크기
크기 16-100: 15%
크기 100+:   10%

→ 10이 75% 케이스 커버

2.5 ILIC에서의 영향

// 무심코 자주 만드는 ArrayList
public ShipmentResponse process(Shipment s) {
    List<String> warnings = new ArrayList<>();
    // ... 보통 0-3개 추가
    
    return new ShipmentResponse(s, warnings);
}

대부분 0-3개 → 10이면 충분. 확장 한 번도 안 일어남.

---

3️⃣ 1.5배 확장 정책 정밀

3.1 ensureCapacity 메서드

// ArrayList 내부 (Java 8+)
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배!
    
    if (newCapacity < minCapacity) {
        newCapacity = minCapacity;
    }
    
    elementData = Arrays.copyOf(elementData, newCapacity);
}

핵심: oldCapacity + (oldCapacity >> 1)

• >> 1 = 비트 시프트 = 2로 나눔
• oldCapacity + oldCapacity/2 = oldCapacity * 1.5

3.2 확장 시퀀스

초기:          capacity 10
1번 확장:      10 + 5 = 15
2번 확장:      15 + 7 = 22
3번 확장:      22 + 11 = 33
4번 확장:      33 + 16 = 49
5번 확장:      49 + 24 = 73
6번 확장:      73 + 36 = 109
7번 확장:      109 + 54 = 163
8번 확장:      163 + 81 = 244
9번 확장:      244 + 122 = 366
10번 확장:     366 + 183 = 549
...

→ 크기가 1.5의 지수로 증가.

3.3 확장의 5단계 동작

add() 호출 → 공간 부족 감지

Step 1: 새 capacity 계산
  newCapacity = oldCapacity + oldCapacity/2

Step 2: 새 배열 할당 (Heap)
  Object[] newArray = new Object[newCapacity];

Step 3: 기존 데이터 복사
  System.arraycopy(elementData, 0, newArray, 0, size);
  
Step 4: 참조 교체
  elementData = newArray;
  (기존 배열은 GC 대상)

Step 5: 새 요소 추가
  elementData[size++] = newElement;

3.4 메모리 다이어그램

시점 1: capacity 10, size 9
  
  elementData ───► ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
                   │A │B │C │D │E │F │G │H │I │  │
                   └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘

시점 2: add("J") — 아직 자리 있음
  
  elementData ───► ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
                   │A │B │C │D │E │F │G │H │I │J │   size=10
                   └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘

시점 3: add("K") — 자리 없음! 확장 발동
  
  1. 새 배열 (15) 생성
                   ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
                   │  │  │  │  │  │  │  │  │  │  │  │  │  │  │  │
                   └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
  
  2. 데이터 복사
                   ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
                   │A │B │C │D │E │F │G │H │I │J │  │  │  │  │  │
                   └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
  
  3. K 추가
                   ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
                   │A │B │C │D │E │F │G │H │I │J │K │  │  │  │  │   size=11
                   └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
  
  4. elementData를 새 배열로 교체
     기존 배열은 GC 대상

→ 확장 = 새 배열 + 데이터 복사.
→ O(n) 비용.

3.5 size vs capacity 추적

ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < 100; i++) {
    list.add(i);
    // i=9 시점: capacity 10, size 10
    // i=10 시점: 확장! capacity 15
    // i=14 시점: size 15
    // i=15 시점: 확장! capacity 22
    // ...
}

# Reflection으로 capacity 확인
java -cp ... com.example.CapacityCheck

---

4️⃣ 1.5배인 이유 — 트레이드오프

4.1 다른 언어/라이브러리의 선택

Java ArrayList: 1.5배
C++ std::vector: 2배 (구현마다 다름)
Python list: 1.125배 + 작은 패딩
JavaScript Array: 보통 2배
Rust Vec: 2배

→ 1.5배 vs 2배가 가장 일반적.

4.2 1.5배의 장점

장점 1 — 메모리 절약

2배 확장:
  10 → 20 → 40 → 80 → 160 → 320 → ...
  
1.5배 확장:
  10 → 15 → 22 → 33 → 49 → 73 → ...

같은 요소 수에서:
  2배: 더 많은 미사용 공간
  1.5배: 더 빡빡한 사용
  
예: 100개 요소 보관
  2배: capacity 128 (28개 낭비)
  1.5배: capacity 109 (9개 낭비)

장점 2 — 메모리 재사용

가설:

2배 확장 시:
  capacity: 4 → 8 → 16 → 32 → 64
  
  64 확장 시점에:
  - 새 배열 64
  - 기존 비워진 메모리: 4+8+16+32 = 60
  - 새 배열 64 > 60
  → 비워진 공간 재사용 불가

1.5배 확장 시:
  capacity: 4 → 6 → 9 → 13 → 19 → 28 → 42
  
  42 확장 시점에:
  - 새 배열 42
  - 기존: 4+6+9+13+19+28 = 79 > 42
  → 이론적으로 재사용 가능

실제로는 GC가 처리해서 큰 차이 없지만, 이론적 근거.

4.3 1.5배의 단점

단점 1 — 확장 횟수 더 많음

1억 요소까지 도달:
  2배: log2(10⁸) ≈ 27번 확장
  1.5배: log1.5(10⁸) ≈ 46번 확장

→ 1.5배가 확장 더 자주.

4.4 자기 점검 답변

1.5배인 이유는? (3배·2배가 아닌)

답:
1. 2배는 메모리 낭비 ↑ (사용 안 한 공간 많음)
2. 3배는 더 심함
3. 1.5배가 균형점:

• 적당한 메모리 효율
• 확장 횟수 합리적
• 이론적 메모리 재사용 가능

4.5 ArrayList의 한계 — Integer.MAX_VALUE

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

배열 최대 크기는 약 21억 (Integer.MAX_VALUE).

• -8 은 일부 JVM의 헤더 영역 고려
• 이 이상 add 시도 → OutOfMemoryError

ILIC에서 21억 요소 ArrayList는 만들 일 없음.
→ 그러나 알아둘 만한 한계.

---

5️⃣ amortized O(1) 분석

5.1 amortized 분석이란

일반 O(1): 항상 상수 시간
amortized O(1): 평균적으로 상수 시간
  (일부 작업은 O(n)이지만, 그 비용을 다음 작업들이 분담)

5.2 ArrayList add의 시간 분석

list.add(e);   // 보통 O(1)
              // 확장 시점에만 O(n)

시나리오: 100개 요소 추가.

i=0~9   : 빠른 add (10번)
i=10    : 확장 발생 → 10개 복사 (10 작업)
i=11~14 : 빠른 add (4번)
i=15    : 확장 발생 → 15개 복사 (15 작업)
i=16~21 : 빠른 add (6번)
i=22    : 확장 발생 → 22개 복사 (22 작업)
...

총 작업량:

빠른 add: 100번
확장 시 복사: 10 + 15 + 22 + 33 + 49 + 73 = 202

총: 302 작업으로 100개 추가
평균: 3.02 작업 / 추가

→ 100개 → 300작업. 100만개 → ~300만 작업.
→ 선형 증가 → amortized O(1).

5.3 amortized 의 직관

가끔 비싼 작업 (확장)이 있지만,
빠른 작업들의 평균치로 분담되어
평균은 상수 시간

비유:

• 휘발유 차 운행: 보통 빠름
• 가끔 주유소 들름 (느린 작업)
• 1000km 운행 시 주유 1시간 = 평균은 빠름

5.4 worst case는 다름

amortized O(1): 평균 O(1)
worst case: O(n) (확장 시점)

실시간 시스템에서는 worst case가 중요.

• 게임의 한 프레임 안에 확장 발동하면 → 끊김
• 실시간 거래 시스템에서 응답 시간 폭발

→ 실시간 환경에선 미리 capacity 지정.

5.5 측정 — 실제 비용

JMH 벤치마크 (가상):

list.add() 평균 시간:
  capacity 미지정: ~30ns (확장 포함)
  capacity 지정:   ~10ns (확장 없음)

→ 큰 List 생성 시 capacity 지정이 3배 빠름.

---

6️⃣ 중간 삽입/삭제의 O(n) 비용

6.1 중간 삽입 동작

List<String> list = new ArrayList<>();
list.add("A"); list.add("B"); list.add("D"); list.add("E");

// 1번 위치에 "C" 삽입
list.add(1, "C");

내부 동작:

Before:
  ┌──┬──┬──┬──┐
  │A │B │D │E │
  └──┴──┴──┴──┘
   0  1  2  3

Step 1: 인덱스 1 이후를 한 칸씩 뒤로 이동
  arraycopy(elementData, 1, elementData, 2, 3)  ← 3개 이동
  
  ┌──┬──┬──┬──┬──┐
  │A │B │B │D │E │   ← 잠시 중복
  └──┴──┴──┴──┴──┘
   0  1  2  3  4

Step 2: 인덱스 1에 "C" 저장
  elementData[1] = "C"
  
  ┌──┬──┬──┬──┬──┐
  │A │C │B │D │E │
  └──┴──┴──┴──┴──┘
  
  ❌ 아직 잘못됨. 위 그림은 단계 설명 위해 잠시.

실제로는:
  Step 1: arraycopy로 [B, D, E]를 1번에서 2번부터 복사
  Step 2: 1번에 C
  
결과:
  ┌──┬──┬──┬──┬──┐
  │A │C │B │D │E │
  └──┴──┴──┴──┴──┘

→ 1번 이후의 모든 요소 이동.
→ 최악의 경우 (앞에 삽입) n번 이동 → O(n).

6.2 중간 삭제 동작

list.remove(1);   // 1번 요소 삭제

내부 동작:

Before:
  ┌──┬──┬──┬──┬──┐
  │A │C │B │D │E │
  └──┴──┴──┴──┴──┘

Step 1: 2번 이후를 한 칸씩 앞으로 이동
  arraycopy(elementData, 2, elementData, 1, 3)
  
  ┌──┬──┬──┬──┬──┐
  │A │B │D │E │E │   ← 마지막에 중복
  └──┴──┴──┴──┴──┘

Step 2: 마지막 슬롯을 null로
  elementData[size-1] = null;
  size--;
  
  ┌──┬──┬──┬──┬──┐
  │A │B │D │E │  │
  └──┴──┴──┴──┴──┘
   size = 4

→ 삭제도 O(n).

6.3 끝 추가/삭제 vs 중간

list.add(e):              O(1) amortized
list.add(0, e):           O(n) — 모든 요소 이동
list.add(i, e):           O(n-i)

list.remove(size-1):      O(1) — 끝만
list.remove(0):           O(n) — 모든 요소 이동
list.remove(i):           O(n-i)

→ 끝은 빠름, 중간/앞은 느림.

6.4 ILIC 시나리오

// 잘못된 사용
List<Shipment> queue = new ArrayList<>();

while (hasNext()) {
    queue.add(0, next());   // ❌ 매번 O(n) 이동!
}

while (!queue.isEmpty()) {
    process(queue.remove(0));   // ❌ 매번 O(n)!
}

10000건 처리 시:

• add(0): 10000² / 2 = 5천만 작업
• remove(0): 또 5천만
• 총 1억 작업

해결:

// LinkedList 또는 ArrayDeque 사용
Deque<Shipment> queue = new ArrayDeque<>();
queue.offerFirst(s);   // O(1)
queue.pollFirst();     // O(1)

6.5 자기 점검 답변

ArrayList의 중간 삽입/삭제 비용이 O(n)인 이유?

답:

• 배열은 연속된 메모리
• 한 자리 비우려면 → 그 이후 요소를 모두 한 칸씩 이동
• 메모리 복사 비용 = 이동할 요소 수에 비례
• → 최악 O(n)

---

7️⃣ ILIC 실무 — 초기 크기와 성능

7.1 초기 크기 지정의 효과

// 큰 List 알면 미리 지정
List<Shipment> shipments = new ArrayList<>(1000);

// vs
List<Shipment> shipments = new ArrayList<>();   // 기본 10

벤치마크 (1000개 추가):

• 미지정: 확장 7번 발생, 약 30ns × 1000 = 30μs
• 지정 1000: 확장 0번, 약 10ns × 1000 = 10μs

→ 3배 빠름.

7.2 자기 점검 답변

new ArrayList<>(1000)처럼 초기 크기를 지정하는 게 왜 효율적인가?

답:
1. 확장 발생 안 함 (10 → 15 → 22 → ... → 1000+)
2. 메모리 복사 비용 0
3. 새 배열 할당도 1번뿐
4. GC 부담 적음 (중간 배열들 만들지 않음)
5. amortized 효과 의존 안 함

7.3 적정 초기 크기

// DB 쿼리 결과 — Page 정보로 크기 알면
Page<Shipment> page = repository.findAll(PageRequest.of(0, 100));
List<Shipment> result = new ArrayList<>(page.getTotalElements());
for (Shipment s : page) {
    result.add(s);
}

// Map → List 변환 — 크기 명확
List<Shipment> shipmentList = new ArrayList<>(shipmentMap.values());

// Stream → List
// Collectors.toList()는 내부적으로 ArrayList 만듦. 크기 모르므로 기본
List<Shipment> list = stream.collect(Collectors.toList());

7.4 ILIC에서 자주 보는 패턴

// 패턴 1: 보통 작은 List → 기본 크기
public ShipmentResponse process(Shipment s) {
    List<String> warnings = new ArrayList<>();
    if (s.isOverweight()) warnings.add("Overweight");
    if (s.isHazardous()) warnings.add("Hazardous");
    return ShipmentResponse.from(s, warnings);
}

// 패턴 2: 큰 List 예상 → 크기 지정
public List<Shipment> findByRoute(String route) {
    long count = repository.countByRoute(route);
    List<Shipment> result = new ArrayList<>((int) count);
    // ...
}

// 패턴 3: 정확한 크기 변환
public List<Long> extractIds(Collection<Shipment> shipments) {
    List<Long> ids = new ArrayList<>(shipments.size());
    for (Shipment s : shipments) {
        ids.add(s.getId());
    }
    return ids;
}

7.5 trimToSize() — 메모리 절약

List<Shipment> list = new ArrayList<>(10000);
// ... 100개만 add
list.add(...);
// ...

// 메모리 절약을 위해
((ArrayList<Shipment>) list).trimToSize();
// elementData 크기를 size(=100)에 맞춤
// → 9900개 슬롯 메모리 회수

ILIC에서:

• 매우 큰 List 생성 후 일부만 사용 시
• 장기 보관 객체에서
• 메모리 압박 환경에서

7.6 Streaming vs ArrayList

큰 데이터 처리 시:

// ❌ 메모리 폭발
List<Shipment> all = repository.findAll();   // 100만 건
for (Shipment s : all) {
    process(s);
}

// ✓ 스트림
try (Stream<Shipment> stream = repository.findAllStream()) {
    stream.forEach(this::process);
}

→ Unit 4.4 거대 객체와 연결.

---

8️⃣ 흔한 실수 + 디버깅

실수 1 — 중간 삽입/삭제 빈번

// ❌ 큐처럼 사용
List<Task> queue = new ArrayList<>();
queue.add(0, task);
queue.remove(0);

→ ArrayDeque, LinkedList 사용.

실수 2 — 큰 List에 초기 크기 미지정

// ❌
List<Shipment> result = new ArrayList<>();
for (Shipment s : huge1MillionStream) {
    result.add(s);
}
// 확장 약 27번 발생!

해결:

• 크기 알면 미리 지정
• 모르면 Stream.toList()

실수 3 — for 루프에서 remove

List<Shipment> list = ...;
for (int i = 0; i < list.size(); i++) {
    if (list.get(i).isExpired()) {
        list.remove(i);   // ❌ 인덱스 꼬임
    }
}

해결:

// 방법 1: Iterator
Iterator<Shipment> it = list.iterator();
while (it.hasNext()) {
    if (it.next().isExpired()) {
        it.remove();   // ✓ 안전
    }
}

// 방법 2: removeIf (Java 8+)
list.removeIf(Shipment::isExpired);

// 방법 3: Stream
list = list.stream()
    .filter(s -> !s.isExpired())
    .collect(Collectors.toList());

실수 4 — subList 함정

List<Shipment> big = ...;
List<Shipment> sub = big.subList(0, 10);

big.clear();   // ❌ sub도 영향받음!

subList는 원본의 view.

• 원본 변경 → sub도 변경
• sub 변경 → 원본도 변경
• 원본을 변형하면 sub는 ConcurrentModificationException

해결:

List<Shipment> sub = new ArrayList<>(big.subList(0, 10));   // 복사본

실수 5 — Arrays.asList 오해

List<String> list = Arrays.asList("A", "B", "C");
list.add("D");   // ❌ UnsupportedOperationException

Arrays.asList:

• 고정 크기 List 반환
• add/remove 불가
• set/get는 가능

해결:

List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
// 또는 Java 9+
List<String> list = List.of("A", "B", "C");   // 완전 불변

실수 6 — 비효율적인 contains

List<Long> ids = ...;   // 10000건
for (Item i : items) {
    if (ids.contains(i.getId())) {   // O(n) × m
        // ...
    }
}

→ Unit 5.1 흔한 실수 1과 동일. Set으로 변환.

실수 7 — Capacity 정보 못 보고 헤맴

ArrayList<Shipment> list = ...;
list.size();        // ✓ 보임 (요소 개수)
// list.capacity(); // ❌ ArrayList에 없음!

ArrayList는 public capacity() 메서드 없음.

• 알고 싶으면 Reflection
• 또는 trimToSize() 후 size와 같음

실수 8 — Vector를 ArrayList 대용

// ❌ Vector 사용
Vector<Shipment> v = new Vector<>();

Vector:

• Java 1.0 클래스 (legacy)
• 모든 메서드 synchronized → 느림
• 멀티스레드 필요 시에도 ConcurrentHashMap 등 권장

→ Vector는 절대 사용 X.

---

9️⃣ 면접 질문 + 자기 점검

9.1 면접 단골 질문 매핑

Q	핵심 답변
ArrayList 내부?	Object[] 배열 + size
기본 크기?	10 (Lazy 초기화)
확장 정책?	1.5배. oldCapacity + (oldCapacity >> 1)
1.5배인 이유?	2배보다 메모리 효율. 3배보다 균형
add() 시간 복잡도?	amortized O(1)
중간 삽입 비용?	O(n). 메모리 복사
초기 크기 지정 효과?	확장 0회. 성능 ↑
trimToSize?	size에 맞게 capacity 축소
Arrays.asList?	고정 크기. add/remove 불가
Vector?	Legacy. synchronized 무거움

9.2 자기 점검 체크리스트

기본 이해

• ArrayList 내부 구조를 안다
• 1.5배 확장 메커니즘을 다이어그램으로 그릴 수 있다
• amortized O(1) 의 의미를 안다
• 중간 삽입/삭제 O(n)을 설명할 수 있다
• size vs capacity 차이를 안다

실전 적용

• 큰 List 생성 시 초기 크기 지정
• 큐가 필요하면 ArrayDeque 사용
• removeIf, Iterator로 안전 삭제
• subList의 view 특성 이해
• Arrays.asList 함정 회피

면접 대비 — 5분 답변

• ArrayList의 내부 메모리 구조
• 1.5배 확장의 트레이드오프
• amortized 분석
• 중간 작업 비용
• 실무 최적화 패턴

---

🎯 핵심 요약 — 3줄 정리

1. ArrayList = Object[] + size

• 기본 크기 10 (Lazy 초기화)
• size는 요소 수, capacity는 배열 크기

2. 1.5배 확장 정책

• oldCapacity + (oldCapacity >> 1)
• 2배보다 메모리 효율, 3배보다 균형
• 확장 = 새 배열 + 데이터 복사 = O(n)
• add()는 amortized O(1)

3. 성능 최적화

• 끝 추가/삭제: O(1)
• 중간 추가/삭제: O(n)
• 초기 크기 지정으로 확장 회피
• contains 빈번 시 Set으로 전환

---

📚 다음으로...

Unit 5.3 — LinkedList 내부 (노드 연결)

이번 Unit에서 ArrayList의 배열 기반을 봤다면, 다음은 LinkedList의 노드 연결 구조.

• Node 클래스의 구조
• 이중 연결 리스트 (Doubly Linked List)
• 메모리 단위가 흩어진 결과
• head/tail의 의미
• 인덱스 접근의 O(n) 이유

Phase 5 진행 상황

🚀 Phase 5 — 컬렉션 내부 구조
  ✅ Unit 5.1 List/Set/Map의 본질적 차이
  ✅ Unit 5.2 ArrayList 내부 ← 여기
  ⏭ Unit 5.3 LinkedList 내부
  ⏭ Unit 5.4 삽입/삭제 효율의 진짜 이유

2주차 진행 상황

✅ Phase 1 (1.1 ~ 1.6 완주)
✅ Phase 2 (2.1 ~ 2.4 완주)
✅ Phase 3 (3.1 ~ 3.4 완주, 정점)
✅ Phase 4 (4.1 ~ 4.5 완주)
🚀 Phase 5 (2/4 진행)
⏭ Phase 6
⏭ Phase 7