🎯 Unit 6.3 — ArrayList vs LinkedList ★★★

F-lab Java 1주차 / Phase 6 / Unit 6.3 본격 학습 자료
9-섹션 마스터 프롬프트 형식으로 깊이 파헤친다.

선수 지식: Phase 4-5 (메모리, GC), Unit 6.1-6.2 (String, StringBuilder)
다음 Unit: 6.4 — HashMap 내부 구조 ★★★

이 Unit의 의미: 자바 컬렉션의 시작점.
면접 단골 ("언제 ArrayList? 언제 LinkedList?") + 실무 (CPU 캐시 진실).
Big-O 만으로 결정하면 틀린다 — 이 Unit 의 핵심 메시지.

---

🌍 1. 세상 속 비유

ArrayList = 아파트 / LinkedList = 보물찾기 사슬

두 자료구조의 차이를 일상 비유로 풀어보겠습니다.

ArrayList — 아파트 단지

[101동] [102동] [103동] [104동] [105동] [106동] [107동]
   ↑                                                 ↑
  시작                                              끝

특징:

• 호수가 연속된 번호
• "104동 가주세요" → 즉시 (번호로 직접)
• 새 동을 중간에 넣으려면? → 뒤의 모든 동 번호 변경 ⚠️
• 마지막에 추가? → 빈 부지에 그냥 ✓

핵심: 인덱스 직접 접근 빠름, 중간 삽입/삭제 느림.

---

LinkedList — 보물찾기 사슬

[A 보물상자]
  → "다음 위치는 X 좌표"
[B 보물상자]
  → "다음 위치는 Y 좌표"
[C 보물상자]
  → "다음 위치는 Z 좌표"
[D 보물상자]
  → "여기가 마지막"

특징:

• 다음 보물 위치만 표시
• "3번째 보물 찾아주세요" → A → B → C 순차 탐색
• 새 보물상자를 중간에? → 앞뒤 화살표만 수정 ✓
• 끝에서 4번째? → 처음부터 다시 탐색? (이중 연결이면 끝부터 4번)

핵심: 순차 탐색 느림, 중간 삽입/삭제 빠름.

---

핵심 한 문장

"두 자료구조는 Big-O 가 다르다 — 그러나 실제 성능은 CPU 캐시 친화도가 결정한다."

비유 정리:

비유	자료구조	강점	약점
아파트 단지	ArrayList	인덱스 접근 (O(1))	중간 삽입 (O(n))
보물찾기 사슬	LinkedList	중간 삽입 (O(1))	인덱스 접근 (O(n))

→ 그런데 현대 CPU 에서는 ArrayList 가 거의 항상 빠름 (이유는 §5에서).

---

또 다른 비유 — "도서관 책장"

ArrayList = 책장의 책들:

• 모든 책이 연속해서 한 책장에
• 5번째 책 = 시작에서 5번째 (즉시 알 수 있음)
• 중간에 새 책 끼우려면 → 뒤의 모든 책을 한 칸씩 밀어야

LinkedList = 흩어진 책들 (편지로 연결):

• 책마다 다음 책의 위치 가 적힌 편지
• 5번째 책 = 1→2→3→4→5 따라가야
• 중간에 새 책? → 편지 두 개만 수정

---

🔥 2. 탄생 배경

"데이터를 어떻게 저장할까?" — 두 가지 답

배열과 연결 리스트는 CS 의 가장 기초적인 자료구조.

배열 (Array) — 1950s

• 연속된 메모리 에 데이터 저장
• 인덱스로 즉시 접근: array[i] = base_address + i * size
• → O(1) 접근

메모리 주소: 1000  1004  1008  1012  1016
데이터:      [10]  [20]  [30]  [40]  [50]
인덱스:        0     1     2     3     4

array[3] → 1000 + 3*4 = 1012 → 즉시 접근

문제:

• 고정 크기
• 가득 차면? → 새 배열 생성 + 복사
• 중간 삽입? → 뒤 요소 모두 이동

---

연결 리스트 (Linked List) — 1960s

• 흩어진 메모리 에 데이터 + 다음 위치 포인터
• 인덱스 접근 X, 순차 탐색 만 가능
• → O(n) 접근

주소 1000          주소 5000           주소 3000
[10][next=5000] → [20][next=3000] → [30][next=null]

장점:

• 동적 크기
• 중간 삽입/삭제 빠름

단점:

• 인덱스 접근 느림
• 메모리 오버헤드 (포인터)

---

자바의 답 — List 인터페이스 + 두 구현체

자바 1.2 (1998) 의 컬렉션 프레임워크 는 두 가지 모두 제공:

public interface List<E> extends Collection<E> {
    E get(int index);
    void add(E element);
    void add(int index, E element);
    E remove(int index);
    // ...
}

구현 1: ArrayList (배열 기반)

public class ArrayList<E> implements List<E> {
    transient Object[] elementData;  // 내부 배열
    private int size;
}

구현 2: LinkedList (이중 연결 리스트 기반)

public class LinkedList<E> implements List<E> {
    transient Node<E> first;  // 첫 노드
    transient Node<E> last;   // 마지막 노드
    transient int size;
    
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
    }
}

→ 같은 List 인터페이스, 완전히 다른 내부 구조.

---

시간 복잡도 비교

연산	ArrayList	LinkedList
get(i)	O(1) ⭐	O(n)
add(e) (끝)	O(1) amortized	O(1) ⭐
add(0, e) (앞)	O(n)	O(1) ⭐
add(i, e) (중간)	O(n)	O(n) 탐색 + O(1) 삽입
remove(i)	O(n)	O(n) (탐색이 비쌈)
contains(e)	O(n)	O(n)
size()	O(1)	O(1)

Big-O 만 보면:

• 인덱스 접근 → ArrayList 압도적
• 중간 삽입/삭제 → 비슷 (LinkedList 가 약간 유리?)

---

그러나 실제로는 — ArrayList 가 거의 항상 빠름

"이론과 실무의 괴리 — CPU 캐시 친화도."

LinkedList 의 모든 노드는 Heap 의 흩어진 위치:

• 메모리 주소 1000: Node A
• 메모리 주소 7300: Node B (전혀 다른 곳)
• 메모리 주소 4200: Node C

CPU 캐시 라인 (보통 64 바이트):

• 메모리 한 번 읽을 때 → 64 바이트 묶음
• ArrayList: 한 번 읽으면 다음 16개 (4 바이트 int) 가 캐시에
• LinkedList: 한 번 읽으면 그 노드만, 다음은 또 메모리 접근

결과:

• ArrayList: L1 캐시 히트 → 1 ns
• LinkedList: 메모리 접근 → 100 ns (L1 의 100배)

→ 순차 처리 시 LinkedList 가 100배 느릴 수 있음.

---

핵심 통찰

"Big-O 는 시작이지 끝이 아니다."

자료구조 선택은 알고리즘 복잡도 + 실제 메모리 동작 + 사용 패턴 의 종합. ArrayList 는 거의 모든 실무에서 정답. LinkedList 는 매우 특정한 상황에서만 의미. 이 사실을 아는 것이 시니어 차별화 포인트.

---

💣 3. 없으면 생기는 문제

시나리오 1: ILIC 의 화물 목록 처리

@Service
public class CargoService {
    
    public List<Cargo> processCargos(BookingRequest request) {
        // ❌ "삽입 많으니까 LinkedList!" — 흔한 오해
        List<Cargo> cargos = new LinkedList<>();
        
        // 1만 개 화물 추가
        for (CargoData data : request.getCargoDataList()) {
            cargos.add(parseCargo(data));  // 끝에 추가
        }
        
        // 처리
        for (Cargo cargo : cargos) {
            processCargo(cargo);  // 순차 처리
        }
        
        return cargos;
    }
}

문제:

• 추가는 둘 다 O(1) (끝에 추가)
• 순차 처리 에서 LinkedList 가 ArrayList 보다 5~10배 느림 (캐시 미스)
• ILIC API 응답 시간 ↑

해결:

List<Cargo> cargos = new ArrayList<>();  // 거의 항상 정답

---

시나리오 2: 면접 단골 질문

Q: "ArrayList 와 LinkedList 의 차이는?"
A: "ArrayList 는 배열 기반, LinkedList 는 연결 리스트 기반이에요"  ⭕ 기초

시니어 답변:

• 시간 복잡도 차이 (O(1) vs O(n) 인덱스 접근)
• 메모리 오버헤드 (LinkedList 노드의 prev/next 포인터)
• CPU 캐시 친화도 (ArrayList 가 캐시 히트율 높음)
• 실무 권장: 거의 항상 ArrayList
• LinkedList 의 진짜 사용처: Deque (양방향 큐), 한정된 경우만

---

시나리오 3: 잘못된 인덱스 접근

// ❌ LinkedList 에 인덱스 반복 접근
List<Booking> bookings = new LinkedList<>(loadBookings());

for (int i = 0; i < bookings.size(); i++) {
    Booking b = bookings.get(i);  // ⚠️ 매번 O(n) 탐색!
    process(b);
}

// 시간 복잡도: O(n²)
// 1만 개 → 1억 번 비교

문제:

• get(i) 가 LinkedList 에서는 O(n) 탐색
• 반복문 내부 → O(n²) 시간 복잡도
• 1만 개에서 수 분 걸림

해결 1: ArrayList

List<Booking> bookings = new ArrayList<>(loadBookings());
for (int i = 0; i < bookings.size(); i++) {
    Booking b = bookings.get(i);  // O(1)
}
// O(n) 시간 복잡도

해결 2: Iterator (LinkedList 라도)

List<Booking> bookings = ...;  // 어떤 List 든
for (Booking b : bookings) {  // 향상된 for = Iterator
    process(b);
}
// LinkedList 에서도 O(n)

---

시나리오 4: 메모리 사용량 충격

// 100만 개 Integer 저장
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkedList = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    arrayList.add(i);
    linkedList.add(i);
}

메모리 사용량 측정:

• ArrayList: ~16MB (Integer 객체 + 배열)
• LinkedList: ~48MB (3배!)

왜 3배?:

• ArrayList: 참조 1개 per 요소 (4~8 바이트)
• LinkedList: Node 객체 + prev + next + item = 4개 참조 + 객체 헤더 (16 + 24 = 40 바이트)

결과:

• 큰 데이터에서 LinkedList 는 메모리 압박 → GC 부담 ↑

---

시나리오 5: ConcurrentModificationException

// ❌ 순회 중 수정
List<Cargo> cargos = new ArrayList<>(allCargos);

for (Cargo c : cargos) {
    if (c.isExpired()) {
        cargos.remove(c);  // ⚠️ ConcurrentModificationException!
    }
}

문제:

• Iterator 가 modCount 를 추적
• 순회 중 외부에서 수정 → 예외 발생
• ArrayList, LinkedList 둘 다 적용

해결 1: Iterator.remove()

Iterator<Cargo> iter = cargos.iterator();
while (iter.hasNext()) {
    if (iter.next().isExpired()) {
        iter.remove();  // ✓ 안전
    }
}

해결 2: Java 8 removeIf

cargos.removeIf(Cargo::isExpired);  // ✓ 가장 깔끔

해결 3: Stream

cargos = cargos.stream()
    .filter(c -> !c.isExpired())
    .collect(Collectors.toList());

---

시나리오 6: ILIC 의 실시간 화물 위치 추적

// 시나리오: 화물 100만 건의 위치 업데이트
public class CargoTrackingService {
    
    private List<CargoLocation> locations;  // 어떤 List?
    
    public void updateLocation(int cargoId, Coordinate coord) {
        CargoLocation loc = locations.get(cargoId);  // O(?)
        loc.setCoordinate(coord);
    }
    
    public void addCargo(CargoLocation loc) {
        locations.add(loc);  // O(?)
    }
    
    public List<CargoLocation> getCargosNearby(Coordinate target) {
        // 순차 탐색
        return locations.stream()
            .filter(l -> distance(l, target) < 100)
            .collect(Collectors.toList());
    }
}

ArrayList 선택 시:

• get(cargoId): O(1) ⭐ (자주 호출되는 위치 업데이트)
• add(): O(1) amortized
• 순차 필터: 캐시 친화적

LinkedList 선택 시:

• get(cargoId): O(n) — 100만 번 탐색! ⚠️
• 100만 건 위치 업데이트 = O(n²) = 사실상 멈춤

→ ArrayList 압도적 승.

---

영향 정리

시나리오	LinkedList 잘못 선택	ArrayList 정답
화물 목록 순차 처리	5~10배 느림	빠름
인덱스 접근 반복	O(n²)	O(n)
메모리 사용	3배 사용	효율
위치 업데이트	사실상 멈춤	정상
면접 답변	표면적	시니어

→ 자료구조 선택은 시니어 자바 개발자의 핵심 역량.

---

✅ 4. 해결책 — 두 자료구조의 정확한 이해

ArrayList — 표준 ⭐

기본 사용

List<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");

System.out.println(list.get(1));  // "Banana"
System.out.println(list.size());   // 3

// 인덱스 기반 반복
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// 향상된 for (권장)
for (String fruit : list) {
    System.out.println(fruit);
}

---

주요 메서드와 시간 복잡도

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

// === 추가 ===
list.add("A");                 // O(1) amortized
list.add(0, "Front");          // O(n) — 모든 요소 이동
list.addAll(otherList);        // O(m)

// === 조회 ===
String s = list.get(0);        // O(1) ⭐
int idx = list.indexOf("A");   // O(n)
boolean has = list.contains("A");  // O(n)

// === 수정 ===
list.set(0, "X");              // O(1)

// === 삭제 ===
list.remove(0);                // O(n) — 뒤 요소 이동
list.remove("A");              // O(n)
list.removeIf(s -> s.startsWith("X"));  // O(n)

// === 정보 ===
list.size();                   // O(1)
list.isEmpty();                // O(1)
list.clear();                  // O(n)

// === 변환 ===
list.toArray();                // O(n)
list.subList(0, 2);            // O(1) view

---

초기 capacity 설정

// ❌ 기본 capacity (10)
List<Cargo> cargos = new ArrayList<>();
for (int i = 0; i < 100000; i++) {
    cargos.add(...);  // 약 14번 확장 발생
}

// ✓ 미리 설정
List<Cargo> cargos = new ArrayList<>(100000);
for (int i = 0; i < 100000; i++) {
    cargos.add(...);  // 확장 없음
}

효과: 30~50% 성능 향상 (큰 데이터일수록 큼).

---

LinkedList — 특수한 경우만

기본 사용

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.addFirst("Front");  // ★ 앞에 추가
list.addLast("Last");    // ★ 끝에 추가

// LinkedList 만의 메서드
list.peekFirst();  // "Front"
list.peekLast();   // "Last"
list.pollFirst();  // "Front" 제거 + 반환
list.pollLast();   // "Last" 제거 + 반환

---

LinkedList 의 진짜 강점 — Deque (양방향 큐)

// LinkedList 는 Deque 인터페이스도 구현
Deque<String> deque = new LinkedList<>();

// 스택처럼 사용
deque.push("A");
deque.push("B");
deque.pop();  // "B"

// 큐처럼 사용
deque.offer("A");
deque.offer("B");
deque.poll();  // "A"

그러나: Deque 가 필요하면 ArrayDeque 가 더 좋음 (캐시 친화).

---

LinkedList 가 의미 있는 경우 (희귀)

Case 1: 양 끝에서만 빈번한 삽입/삭제 + 순차 접근

// 작업 큐 (FIFO) — 그러나 ArrayDeque 가 더 좋음
LinkedList<Task> queue = new LinkedList<>();
queue.offer(task);  // 끝에 추가
queue.poll();       // 앞에서 제거

Case 2: 삽입/삭제만 매우 빈번 + 인덱스 접근 X

// 그러나 실무에서 거의 없음

→ 현실적으로 LinkedList 사용처는 거의 없음. ArrayList 또는 ArrayDeque 가 항상 더 좋음.

---

비교 표 ⭐⭐ (면접 답변 핵심)

항목	ArrayList	LinkedList
내부 구조	동적 배열	이중 연결 리스트
인덱스 접근	O(1) ⭐	O(n)
끝 추가	O(1) amortized	O(1)
앞 추가	O(n)	O(1)
중간 추가 (탐색 후)	O(n)	O(n)
메모리/요소	~8 바이트	~40 바이트 (5배)
캐시 친화도	높음 ⭐	낮음
순차 반복	빠름 ⭐	느림 (5~10배)
권장도	거의 모든 경우	매우 특수한 경우

---

선택 가이드 ⭐ (실용)

List 가 필요하다 → ArrayList ⭐ (90% 이상의 경우)
        ↓
정말 양 끝에서만 빈번한 삽입?
├── YES → ArrayDeque ⭐ (LinkedList 보다 좋음)
└── NO  → ArrayList

결론: 자바에서 LinkedList 는 거의 사용하지 않음.

---

Stream + List 패턴

// 자주 쓰는 패턴
List<Cargo> result = cargos.stream()
    .filter(c -> c.getWeight() > 100)
    .collect(Collectors.toList());  // 기본 ArrayList

// Java 16+ 의 toList()
List<Cargo> result = cargos.stream()
    .filter(c -> c.getWeight() > 100)
    .toList();  // 불변 List

Collectors.toList() 의 결과: 기본적으로 ArrayList.

---

불변 List

// Java 9+
List<String> immutable = List.of("A", "B", "C");

// 시도 시 UnsupportedOperationException
immutable.add("D");  // ❌ 예외

용도: 상수 리스트, 불변성 보장 필요 시.

---

🏗️ 5. 내부 동작 원리

ArrayList 의 내부 구조

public class ArrayList<E> {
    transient Object[] elementData;  // 내부 배열
    private int size;                // 실제 사용 중 개수
    
    // 기본 capacity
    private static final int DEFAULT_CAPACITY = 10;
}

핵심:

• elementData.length = capacity (배열 크기)
• size = 현재 사용 개수
• size ≤ capacity

---

ArrayList.add() 의 동작

public boolean add(E e) {
    modCount++;
    if (size == elementData.length) {
        elementData = grow();  // 확장!
    }
    elementData[size] = e;
    size++;
    return true;
}

private Object[] grow() {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 1.5배
    return Arrays.copyOf(elementData, newCapacity);
}

확장 공식: newCapacity = oldCapacity * 1.5

초기: 10
11번째 추가: 10 * 1.5 = 15
16번째 추가: 15 * 1.5 = 22
23번째 추가: 22 * 1.5 = 33
...

→ 점진적으로 큰 폭 확장, amortized O(1).

---

ArrayList.get() 의 동작

public E get(int index) {
    Objects.checkIndex(index, size);
    return (E) elementData[index];  // 배열 직접 접근
}

O(1): 메모리 주소 직접 계산.

---

ArrayList.add(0, e) 의 동작 (앞에 추가)

public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    if (size == elementData.length) {
        elementData = grow();
    }
    
    // 뒤 요소를 한 칸씩 뒤로 이동
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     size - index);
    
    elementData[index] = element;
    size++;
}

O(n): arraycopy 가 빠르긴 하지만 n 에 비례.

---

ArrayList 의 메모리 그림

elementData = [A][B][C][D][E][_][_][_][_][_]
              ↑                ↑              ↑
              0              size=5    capacity=10

JVM Heap:
  [ArrayList 객체]
    size: 5
    elementData: ────────────┐
                              ↓
  [Object[] 배열 — 연속 메모리]
    [A][B][C][D][E][null][null][null][null][null]

핵심: 배열은 하나의 연속된 메모리 블록.

---

LinkedList 의 내부 구조

public class LinkedList<E> {
    transient int size = 0;
    transient Node<E> first;  // 첫 노드
    transient Node<E> last;   // 마지막 노드
    
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}

핵심:

• 각 요소가 Node 객체로 감싸짐
• prev + next 포인터로 양방향 연결

---

LinkedList 의 메모리 그림

JVM Heap:
  [LinkedList 객체]
    size: 5
    first: ──┐
    last:  ──┼─┐
              │ │
  [Node A]   │ │
    prev: null
    item: "A"
    next: ──→[Node B]
              │ │       prev: ──→[Node A]
              │ │       item: "B"
              │ │       next: ──→[Node C]
              │ │
              │ │
              │ │     [Node E]
              │ └──→  prev: ──→[Node D]
                       item: "E"
                       next: null

핵심:

• Node 객체들이 Heap 의 흩어진 위치
• 각 Node 마다 객체 헤더 + 3개 참조 (prev, item, next)
• 64비트 JVM에서 Node 1개 ≈ 40 바이트

---

LinkedList.get() 의 동작 — 함정

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int index) {
    if (index < (size >> 1)) {
        // 앞쪽이면 first 부터
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;  // ★ 순차 탐색
        return x;
    } else {
        // 뒤쪽이면 last 부터
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;  // ★ 순차 탐색
        return x;
    }
}

O(n/2) = O(n): 그러나 양방향 탐색으로 절반은 절약.

→ 인덱스 접근에 LinkedList 사용 절대 X.

---

LinkedList.add() 의 동작 (끝에 추가)

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);  // ★ Node 객체 생성!
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
}

O(1): 마지막 노드에 직접 연결.

그러나:

• 매번 Node 객체 생성 → GC 부담
• 메모리 할당 비용 → ArrayList 보다 느릴 수 있음

---

CPU 캐시 친화도 (이 Unit 의 핵심) ⭐⭐⭐

CPU 캐시 계층

[CPU Core] ←── 1 ns
   ↑
[L1 Cache] (수십 KB)
   ↑ ── 5 ns
[L2 Cache] (수백 KB)
   ↑ ── 15 ns
[L3 Cache] (수 MB)
   ↑ ── 30 ns
[Main Memory (RAM)] ── 100 ns
   ↑
[Disk] ── 10ms

캐시 라인 (cache line):

• 한 번에 가져오는 메모리 크기 (보통 64 바이트)
• 1 바이트 읽어도 → 64 바이트 가져옴

---

ArrayList 의 캐시 친화도

List<Integer> list = new ArrayList<>(...);
for (Integer i : list) {
    // i 처리
}

메모리 그림:

배열 (연속):
[I0][I1][I2][I3][I4][I5][I6][I7]...
 ↑─── 64 바이트 캐시 라인 ────↑

L1 캐시에 한 번 로드 → 8개 처리 가능 (4 바이트 int 기준)
→ 평균 1 ns per 요소

이론: 1만 개 처리 시 약 0.01 ms.

---

LinkedList 의 캐시 친화도 (없음)

List<Integer> list = new LinkedList<>(...);
for (Integer i : list) {
    // i 처리
}

메모리 그림:

Node A (주소 1000)
  → Node B (주소 7300) — 캐시 라인 다름
    → Node C (주소 4200) — 또 다름
      → Node D (주소 12000) — 또 다름

매 요소마다:

• 캐시 미스
• L1 → L2 → L3 → RAM 까지 가야 할 수도
• 평균 30~100 ns

현실: 1만 개 처리 시 약 0.5 ms (50배 느림).

---

실제 측정 결과

public class CacheTest {
    public static void main(String[] args) {
        int N = 10_000_000;
        List<Integer> arr = new ArrayList<>(N);
        List<Integer> linked = new LinkedList<>();
        
        for (int i = 0; i < N; i++) {
            arr.add(i);
            linked.add(i);
        }
        
        // ArrayList 순회
        long start = System.nanoTime();
        long sum1 = 0;
        for (Integer i : arr) sum1 += i;
        long arrTime = System.nanoTime() - start;
        
        // LinkedList 순회
        start = System.nanoTime();
        long sum2 = 0;
        for (Integer i : linked) sum2 += i;
        long linkedTime = System.nanoTime() - start;
        
        System.out.println("ArrayList:  " + arrTime / 1_000_000 + " ms");
        // 약 30 ms
        
        System.out.println("LinkedList: " + linkedTime / 1_000_000 + " ms");
        // 약 200 ms (7배 느림)
    }
}

결과: 5~10배 차이 (메모리 단편화 정도에 따라 30배까지).

---

Big-O 가 거짓말하는 이유

Big-O 의 가정:

• 모든 메모리 접근이 같은 비용
• 실제로는 L1 캐시 1ns vs RAM 100ns = 100배 차이

현대 CPU 의 진실:

• 알고리즘 복잡도 < 메모리 접근 패턴
• "상수 100배 차이" 는 작은 N 에서 알고리즘 차이를 압도

---

modCount — Fail-Fast Iterator

public class ArrayList<E> {
    protected transient int modCount = 0;
    
    public boolean add(E e) {
        modCount++;  // 수정 시 증가
        // ...
    }
    
    private class Itr implements Iterator<E> {
        int expectedModCount = modCount;
        
        public E next() {
            checkForComodification();
            // ...
        }
        
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
}

Fail-Fast 원칙:

• 순회 중 외부 수정 발생 → 즉시 예외
• 데이터 일관성 보장

---

💻 6. 실전 코드 예시

예시 1: ILIC 의 화물 목록 — ArrayList

@Service
public class CargoService {
    
    public List<Cargo> getCargosByBooking(Long bookingId) {
        // ✓ ArrayList — 표준 선택
        List<Cargo> cargos = new ArrayList<>();
        
        // DB 에서 화물 로드
        try (PreparedStatement ps = conn.prepareStatement(
                "SELECT * FROM cargos WHERE booking_id = ?")) {
            ps.setLong(1, bookingId);
            try (ResultSet rs = ps.executeQuery()) {
                while (rs.next()) {
                    cargos.add(mapToCargo(rs));  // O(1)
                }
            }
        }
        
        return cargos;
    }
    
    public Cargo getCargoByIndex(List<Cargo> cargos, int index) {
        return cargos.get(index);  // O(1) ⭐ ArrayList 의 강점
    }
    
    public List<Cargo> filterHeavy(List<Cargo> cargos, double minWeight) {
        // 순차 처리 — ArrayList 의 캐시 친화도 활용
        return cargos.stream()
            .filter(c -> c.getWeight() >= minWeight)
            .collect(Collectors.toList());
    }
}

---

예시 2: 초기 capacity 설정

@Service
public class BookingReportService {
    
    public List<BookingItem> generateMonthlyReport(int year, int month) {
        int estimatedSize = bookingRepository.countByMonth(year, month);
        
        // ✓ 미리 capacity 설정
        List<BookingItem> items = new ArrayList<>(estimatedSize);
        
        bookingRepository.streamByMonth(year, month)
            .forEach(b -> items.add(toBookingItem(b)));
        
        return items;
    }
}

효과: 큰 데이터에서 30~50% 성능 향상.

---

예시 3: 안전한 순회 + 수정

public class CargoFilterService {
    
    // ❌ 위험
    public void removeExpiredUnsafe(List<Cargo> cargos) {
        for (Cargo c : cargos) {
            if (c.isExpired()) {
                cargos.remove(c);  // ConcurrentModificationException!
            }
        }
    }
    
    // ✓ Iterator
    public void removeExpiredIterator(List<Cargo> cargos) {
        Iterator<Cargo> iter = cargos.iterator();
        while (iter.hasNext()) {
            if (iter.next().isExpired()) {
                iter.remove();  // 안전
            }
        }
    }
    
    // ✓ removeIf (Java 8+)
    public void removeExpiredModern(List<Cargo> cargos) {
        cargos.removeIf(Cargo::isExpired);  // 가장 깔끔
    }
    
    // ✓ Stream (새 List 생성)
    public List<Cargo> filterAlive(List<Cargo> cargos) {
        return cargos.stream()
            .filter(c -> !c.isExpired())
            .collect(Collectors.toList());
    }
}

---

예시 4: 양방향 큐 — ArrayDeque (LinkedList 대신)

@Service
public class TaskQueueService {
    
    // ❌ LinkedList 로 큐 구현
    private LinkedList<Task> queue = new LinkedList<>();
    
    // ✓ ArrayDeque — 더 빠름!
    private ArrayDeque<Task> queue = new ArrayDeque<>();
    
    public void enqueue(Task task) {
        queue.offer(task);
    }
    
    public Task dequeue() {
        return queue.poll();
    }
}

왜 ArrayDeque 가 더 좋은가?:

• 원형 배열 기반
• 캐시 친화도 ↑
• LinkedList 보다 2~3배 빠름

---

예시 5: ILIC 의 페이지네이션

@Service
public class CargoSearchService {
    
    // ✓ ArrayList — 인덱스 기반 페이지네이션
    public List<Cargo> getPage(int page, int pageSize) {
        List<Cargo> all = loadAll();  // ArrayList
        
        int from = page * pageSize;
        int to = Math.min(from + pageSize, all.size());
        
        // O(1) — subList 는 view
        return all.subList(from, to);
    }
}

LinkedList 라면:

• subList 도 내부적으로 인덱스 탐색 → O(n) 추가 비용
• 페이지네이션이 느려짐

---

예시 6: 성능 비교 벤치마크

public class ListBenchmark {
    
    public static void main(String[] args) {
        int N = 1_000_000;
        
        // 1. 끝에 추가
        long arrayListAdd = benchmark(() -> {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < N; i++) list.add(i);
        });
        
        long linkedListAdd = benchmark(() -> {
            List<Integer> list = new LinkedList<>();
            for (int i = 0; i < N; i++) list.add(i);
        });
        
        // 2. 순차 순회
        List<Integer> arr = new ArrayList<>(/* 1M items */);
        List<Integer> lnk = new LinkedList<>(/* 1M items */);
        
        long arrIter = benchmark(() -> {
            long sum = 0;
            for (Integer i : arr) sum += i;
        });
        
        long lnkIter = benchmark(() -> {
            long sum = 0;
            for (Integer i : lnk) sum += i;
        });
        
        // 3. 인덱스 접근
        long arrGet = benchmark(() -> {
            for (int i = 0; i < N; i++) arr.get(i);
        });
        
        long lnkGet = benchmark(() -> {
            for (int i = 0; i < N; i++) lnk.get(i);  // ⚠️ O(n²)
        });
        
        System.out.println("Add (end):");
        System.out.println("  ArrayList:  " + arrayListAdd + "ms");   // ~30ms
        System.out.println("  LinkedList: " + linkedListAdd + "ms");  // ~40ms
        
        System.out.println("Iterate:");
        System.out.println("  ArrayList:  " + arrIter + "ms");   // ~5ms
        System.out.println("  LinkedList: " + lnkIter + "ms");   // ~50ms (10배)
        
        System.out.println("Get(i):");
        System.out.println("  ArrayList:  " + arrGet + "ms");    // ~10ms
        System.out.println("  LinkedList: " + lnkGet + "ms");    // ~수십 분 (사실상 멈춤)
    }
    
    static long benchmark(Runnable task) {
        long start = System.currentTimeMillis();
        task.run();
        return System.currentTimeMillis() - start;
    }
}

---

예시 7: 컬렉션 변환

public class CollectionConverter {
    
    // 배열 → ArrayList
    Cargo[] array = ...;
    List<Cargo> list1 = new ArrayList<>(Arrays.asList(array));
    List<Cargo> list2 = Arrays.stream(array).collect(Collectors.toList());
    
    // List → 배열
    Cargo[] arr = list1.toArray(new Cargo[0]);
    
    // List → 다른 List
    List<Cargo> immutable = List.copyOf(list1);  // 불변
    List<Cargo> sorted = list1.stream()
        .sorted(Comparator.comparing(Cargo::getWeight))
        .collect(Collectors.toList());
}

---

예시 8: 동시성 안전 List

public class ThreadSafeListExamples {
    
    // ❌ 일반 ArrayList — 동시 수정 시 데이터 손상
    private List<Cargo> unsafeList = new ArrayList<>();
    
    // ✓ 1. Collections.synchronizedList
    private List<Cargo> synced = Collections.synchronizedList(new ArrayList<>());
    // 모든 메서드 synchronized — 그러나 순회 시 외부 동기화 필요!
    
    synchronized (synced) {
        for (Cargo c : synced) {  // 순회는 명시적 동기화
            // ...
        }
    }
    
    // ✓ 2. CopyOnWriteArrayList
    private List<Cargo> cow = new CopyOnWriteArrayList<>();
    // 쓰기 시 전체 복사 — 읽기 많고 쓰기 적은 경우
    
    // ✓ 3. ConcurrentLinkedQueue (List 아님)
    private Queue<Cargo> queue = new ConcurrentLinkedQueue<>();
    // 진정한 동시성 큐
}

---

⚠️ 7. 주의사항 & 흔한 실수

실수 1: "삽입 많으니까 LinkedList!"

// ❌ 흔한 오해
List<Cargo> cargos = new LinkedList<>();
for (CargoData data : dataList) {
    cargos.add(parse(data));  // 끝에 추가
}

진실:

• "끝에 추가" 는 ArrayList 도 O(1) amortized
• LinkedList 는 Node 객체 생성 비용 + GC 부담
• → ArrayList 가 빠름

해결: ArrayList 가 표준.

---

실수 2: LinkedList 에 인덱스 접근

// ❌ 치명적
LinkedList<Booking> list = ...;
for (int i = 0; i < list.size(); i++) {
    process(list.get(i));  // O(n²)!
}

// 1만 개 → 1억 번 비교 → 분 단위

해결: 향상된 for (Iterator 사용)

for (Booking b : list) {  // O(n)
    process(b);
}

---

실수 3: ArrayList 의 앞에 빈번한 추가

// ❌ 비효율
List<Cargo> cargos = new ArrayList<>();
for (Cargo c : newCargos) {
    cargos.add(0, c);  // O(n) — 모든 요소 이동
}

// 1만 개 → O(n²)

해결 1: 끝에 추가 후 reverse

for (Cargo c : newCargos) {
    cargos.add(c);
}
Collections.reverse(cargos);  // O(n)

해결 2: ArrayDeque

Deque<Cargo> deque = new ArrayDeque<>();
for (Cargo c : newCargos) {
    deque.offerFirst(c);  // O(1)
}

---

실수 4: ConcurrentModificationException

// ❌ 순회 중 수정
for (Cargo c : cargos) {
    if (c.isExpired()) {
        cargos.remove(c);  // 예외!
    }
}

해결: removeIf

cargos.removeIf(Cargo::isExpired);  // 가장 깔끔

---

실수 5: subList 의 함정

List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4, 5));
List<Integer> sub = list.subList(1, 4);  // [2, 3, 4]

// subList 는 view!
sub.add(99);  
// → list 도 변함: [1, 2, 3, 4, 99, 5]

// 원본을 수정하면?
list.add(0, 100);
sub.size();  // ConcurrentModificationException!

해결: 새 List 생성

List<Integer> sub = new ArrayList<>(list.subList(1, 4));  // 복사

---

실수 6: capacity 미설정

// ❌ 큰 데이터인데 기본 capacity (10)
List<Item> items = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) {
    items.add(...);  // 약 30번 확장 발생
}

해결: 미리 설정

List<Item> items = new ArrayList<>(1_000_000);

---

실수 7: List.of() 수정 시도

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

// List.of() 는 불변!

해결: 가변이 필요하면

List<String> list = new ArrayList<>(List.of("A", "B", "C"));
list.add("D");  // ✓

---

실수 8: equals 와 hashCode

List<Cargo> list1 = new ArrayList<>(...);
List<Cargo> list2 = new LinkedList<>(...);

// 두 리스트가 같은 요소면?
list1.equals(list2);  // true (구현 다르지만 내용 같으면)

// HashMap 키로 사용 시?
Map<List<Cargo>, String> map = new HashMap<>();
map.put(list1, "value");

// 그러나 List 를 수정하면?
list1.add(new Cargo(...));
map.get(list1);  // null! (hashCode 변경됨)

원칙: 가변 List 를 HashMap 키로 사용 X.

---

🔗 8. 연관 개념 맵

Phase 6 (데이터 다루기) 에서의 위치

[Unit 6.1: String + Constant Pool] ✓
        ↓
[Unit 6.2: StringBuilder vs StringBuffer] ✓
        ↓
[Unit 6.3: ArrayList vs LinkedList] ← 지금 여기 ★
        ↓
[Unit 6.4: HashMap 내부 구조] ★★★ (다음, 핵심)
        ↓
[Unit 6.5: TreeMap, LinkedHashMap]

---

Phase 4-5 와의 연결

Phase	연결
4.1 (JVM 메모리)	배열은 Heap 에 연속 메모리
5.1 (GC)	LinkedList 의 Node 들이 GC 부담
5.2 (Heap 구조)	큰 List 는 Old Gen 으로 promotion

---

자바 컬렉션 프레임워크 전체

Collection (인터페이스)
├── List
│   ├── ArrayList ⭐
│   ├── LinkedList
│   └── Vector (legacy, synchronized)
│
├── Set
│   ├── HashSet
│   ├── LinkedHashSet
│   └── TreeSet
│
└── Queue / Deque
    ├── ArrayDeque ⭐
    ├── LinkedList (Deque 도 구현)
    └── PriorityQueue

Map (별도 인터페이스)
├── HashMap ⭐ (Unit 6.4)
├── LinkedHashMap (Unit 6.5)
├── TreeMap (Unit 6.5)
└── ConcurrentHashMap

---

시간 복잡도 종합

자료구조	get	add	remove	contains
ArrayList	O(1)	O(1)*	O(n)	O(n)
LinkedList	O(n)	O(1)*	O(n)	O(n)
HashSet	-	O(1)	O(1)	O(1)
TreeSet	-	O(log n)	O(log n)	O(log n)
HashMap	-	O(1)	O(1)	O(1)
TreeMap	-	O(log n)	O(log n)	O(log n)

*amortized

---

다른 언어 비교

언어	동적 배열	연결 리스트
Java	ArrayList	LinkedList
C++	std::vector	std::list
Python	list	(없음, deque)
JavaScript	Array	(없음)
C#	List<T>	LinkedList<T>
Rust	Vec<T>	LinkedList<T>

→ 거의 모든 언어가 동적 배열 표준 + 연결 리스트는 옵션.

---

면접 단골 질문 매핑

질문	이 Unit 에서의 답
ArrayList vs LinkedList?	시간 복잡도 + CPU 캐시
언제 LinkedList?	거의 없음 (ArrayDeque 가 보통 더 좋음)
ArrayList capacity 동작?	1.5배 확장
인덱스 접근 차이?	O(1) vs O(n)
메모리 사용?	LinkedList 가 5배

---

📝 9. 핵심 요약 — 3줄 정리

1️⃣ ArrayList = 동적 배열, LinkedList = 이중 연결 리스트.

ArrayList 는 연속된 메모리 에 배열 보관 — 인덱스 접근 O(1), 중간 삽입 O(n). LinkedList 는 Node 객체들의 양방향 사슬 — 인덱스 접근 O(n), 중간 삽입 O(1) (탐색 후). Big-O 만 보면 LinkedList 가 좋아 보일 수도 있으나...

2️⃣ CPU 캐시 친화도가 모든 것을 바꾼다 — ArrayList 가 거의 항상 빠름.

현대 CPU 의 L1 캐시 (1ns) vs RAM (100ns) 의 100배 차이. ArrayList 는 연속 메모리 → 캐시 라인 활용 → 다음 요소가 이미 캐시에. LinkedList 는 흩어진 Node → 매번 캐시 미스 → 100배 느림. 순차 순회에서 ArrayList 가 5~10배 빠름. 메모리도 5배 적게 사용.

3️⃣ 실무 원칙 — ArrayList 가 표준, LinkedList 는 거의 안 씀.

List 가 필요하면 무조건 ArrayList. 큰 데이터면 new ArrayList<>(예상크기) 로 capacity 미리 설정. 양 끝 큐가 필요하면 ArrayDeque (LinkedList 보다 좋음). 순회 중 수정 은 removeIf 또는 Iterator.remove. HashMap 키로 가변 List 사용 X (hashCode 변경 위험). LinkedList 는 면접 답변 외에는 사용처가 거의 없다고 봐도 무방.

---

🎓 학습 자기 점검

기본 이해

• ArrayList 와 LinkedList 의 내부 구조를 그림으로 그릴 수 있다
• 시간 복잡도 차이를 정확히 안다 (get, add, remove)
• CPU 캐시 친화도가 왜 중요한지 설명할 수 있다
• ArrayList 의 1.5배 확장을 안다

실전 적용

• 거의 모든 경우에 ArrayList 를 선택한다
• 큰 데이터 시 capacity 를 미리 설정한다
• 양 끝 큐는 ArrayDeque 를 사용한다
• ConcurrentModificationException 을 회피한다 (removeIf)

면접 대비 (5분 답변)

• "ArrayList vs LinkedList 차이?" 답변 가능
• "Big-O 만 보면 안 되는 이유?" 답변 가능
• "언제 LinkedList?" 답변 가능 (거의 없음)
• "메모리 차이?" 답변 가능 (5배)

자기 점검 질문 답변

Q1: ArrayList 가 LinkedList 보다 거의 항상 빠른 이유를 메모리 + CPU 관점에서 설명하라.

한 줄 답: 연속 메모리 가 CPU 캐시 라인 을 효율적으로 활용해 L1 캐시 (1ns) 에서 데이터를 가져올 수 있기 때문. LinkedList 는 흩어진 Node 로 매번 RAM (100ns) 접근.

상세 설명:

1. 메모리 배치 차이

ArrayList 의 메모리:

Heap 의 한 영역 (연속):
주소 1000: [Item 0]
주소 1004: [Item 1]
주소 1008: [Item 2]
주소 1012: [Item 3]
...

LinkedList 의 메모리:

Heap 의 흩어진 영역:
주소 1000: [Node 0: prev=null, next=주소 7300, item]
주소 7300: [Node 1: prev=주소 1000, next=주소 4200, item]
주소 4200: [Node 2: prev=주소 7300, next=주소 12000, item]
주소 12000: [Node 3: ...]

왜 흩어지나?:

• LinkedList 의 Node 는 각각 별도 new 로 생성
• JVM 의 메모리 할당자가 그때그때 빈 공간에 배치
• → 인접한 노드가 메모리상 인접 X

---

2. CPU 캐시 계층의 비용

L1 Cache (32 KB):    ~ 1 ns   (CPU 코어 옆)
L2 Cache (256 KB):   ~ 5 ns
L3 Cache (8 MB):     ~ 30 ns  (코어 공유)
RAM (16 GB):         ~ 100 ns

핵심: L1 vs RAM = 100배 차이.

---

3. 캐시 라인 (Cache Line)

CPU 가 메모리를 읽을 때:

• 64 바이트 묶음 으로 가져옴 (캐시 라인 단위)
• 1 바이트만 필요해도 64 바이트 가져옴
• → "근처 데이터" 가 같이 들어옴

ArrayList 의 활용:

배열: [I0][I1][I2][I3][I4][I5][I6][I7]...
       ↑─── 64 바이트 캐시 라인 ────↑

처리:
1. I0 읽기 → 캐시 미스 → 64 바이트 가져옴 (I0~I15)
2. I1 읽기 → ✓ 캐시 히트 (1 ns)
3. I2 읽기 → ✓ 캐시 히트 (1 ns)
...
17. I16 읽기 → 캐시 미스 → 다음 64 바이트 가져옴

평균 비용: 100 ns / 16 요소 = 6 ns per 요소.

---

4. LinkedList 의 캐시 미스 지옥

처리:
1. Node 0 읽기 → 캐시 미스 → 100 ns
2. Node 0.next 따라 Node 1 읽기 → 또 캐시 미스 → 100 ns
3. Node 1.next 따라 Node 2 읽기 → 또 캐시 미스 → 100 ns
...

평균 비용: 100 ns per 요소 (ArrayList 의 16배).

---

5. 실측 결과 — 100만 개 순회

int N = 1_000_000;

// ArrayList
for (Integer i : arrayList) sum += i;  // 약 5 ms

// LinkedList
for (Integer i : linkedList) sum += i;  // 약 50 ms

→ 10배 차이.

---

6. 추가 비용 — Node 객체 오버헤드

LinkedList 의 각 Node:

private static class Node<E> {
    E item;       // 4~8 바이트
    Node<E> next; // 4~8 바이트
    Node<E> prev; // 4~8 바이트
}
// + 객체 헤더 16 바이트
// = 약 32~40 바이트 per 요소

ArrayList:

Object[] elementData;  // 4~8 바이트 per 참조

메모리 차이:

• ArrayList: 8 바이트 / 요소
• LinkedList: 40 바이트 / 요소 (5배)

100만 요소:

• ArrayList: ~8 MB
• LinkedList: ~40 MB

→ GC 부담 증가.

---

7. 종합 비교

측면	ArrayList	LinkedList
메모리 배치	연속	흩어짐
캐시 활용	매우 높음	거의 없음
L1 히트율	~95%	~5%
평균 접근 시간	~6 ns	~100 ns
메모리 사용	1배	5배
GC 부담	적음	큼

---

8. 결론

"알고리즘 복잡도 (Big-O) 는 시작점이지 결정점이 아니다.
현대 CPU 에서 메모리 접근 패턴이 알고리즘 복잡도를 압도 한다.
ArrayList 의 연속 메모리 = CPU 캐시 친화 = 거의 모든 실무 시나리오에서 빠름.
LinkedList 의 흩어진 Node = 캐시 미스 지옥 = 거의 모든 실무에서 느림.
시니어의 깨달음 — 이론과 실무의 괴리를 인식하고 측정으로 검증."

---

Q2: 100만 개 데이터의 중간에 1만 번 삽입한다면 어느 게 좋을까?

한 줄 답: 둘 다 비슷하게 느림 (O(n²)), 그러나 ArrayList 가 약간 더 빠름. 이런 시나리오라면 자료구조 자체를 재고 해야 함.

상세 설명:

1. 표면적 분석

ArrayList 중간 삽입:

• 위치 찾기: O(1) (인덱스 직접)
• 뒤 요소 이동: O(n)
• 합계: O(n) per 삽입

LinkedList 중간 삽입:

• 위치 찾기: O(n) — 처음부터 탐색!
• 노드 연결: O(1)
• 합계: O(n) per 삽입

→ 둘 다 O(n) — Big-O 는 같음.

---

2. 1만 번 반복 시

100만 + 1만 번 삽입 = 약 100억 번의 작업 = O(n²).

List<Integer> list = ...;  // 100만 개
for (int i = 0; i < 10000; i++) {
    list.add(500000, value);  // 중간에 삽입
}

시간:

• ArrayList: 약 수 분~수십 분
• LinkedList: 약 수 분~수십 분 (비슷)

---

3. 그러나 상수 항이 다름

ArrayList 의 중간 삽입:

• System.arraycopy 사용 → 매우 빠른 메모리 복사
• CPU SIMD 활용 가능
• 50만 요소 이동: ~2 ms

LinkedList 의 중간 삽입:

• 50만 번의 node = node.next 탐색
• 각 탐색마다 캐시 미스
• 50만 노드 탐색: ~50 ms

→ ArrayList 가 약 25배 빠름 (상수 항 차이).

---

4. 실측 (대략)

int N = 1_000_000;
int M = 10_000;

// ArrayList
List<Integer> arr = new ArrayList<>(/* N items */);
for (int i = 0; i < M; i++) {
    arr.add(N / 2, i);
}
// 약 30~60초

// LinkedList
List<Integer> lnk = new LinkedList<>(/* N items */);
for (int i = 0; i < M; i++) {
    lnk.add(N / 2, i);
}
// 약 분 단위 (사실상 사용 불가)

---

5. 더 나은 대안 — 자료구조 재고

이런 시나리오에서는 List 자체가 부적합.

대안 1: TreeMap (정렬 키)

TreeMap<Integer, Integer> map = new TreeMap<>();
map.put(50, value);  // O(log n)

대안 2: 일괄 처리 (Batch)

// 1만 개를 모아서 한 번에 정렬/병합
List<Integer> batch = collect();
list.addAll(batch);
Collections.sort(list);  // O(n log n)

대안 3: 다른 자료구조 (Skip List, B-Tree)

// 자바 표준은 없음, 라이브러리 필요

대안 4: 데이터베이스

-- DB 의 인덱스 활용 — 100만 행에서도 O(log n)
INSERT INTO table VALUES (...);

---

6. 면접 답변 패턴

"100만 데이터에 1만 번 중간 삽입" 질문이 나온다면:

1. 표면적 답 (1점): "LinkedList 가 삽입은 O(1) 이라 더 빠름"

2. 중급 답 (3점): "둘 다 O(n) — LinkedList 는 위치 탐색 O(n) 이 추가됨"

3. 시니어 답 (5점):

   • "둘 다 O(n²) 로 부적합"
   • "ArrayList 가 상수 항이 작아 약간 빠름 (System.arraycopy + 캐시)"
   • "진짜 답은 자료구조를 재고하는 것 — TreeMap, 일괄 처리, DB 등"
   • "리얼월드에서 이런 시나리오가 나오면 요구사항 자체를 분석해야 함"

---

7. 결론

"100만 + 1만 중간 삽입은 자료구조 선택 문제가 아닌 설계 문제.
ArrayList 와 LinkedList 모두 O(n²) 로 부적합.
진짜 시니어는 '둘 중 어느 것?' 이 아닌 '왜 이런 패턴이 필요한가?' 를 묻는다.
자주 바뀌는 정렬된 데이터 = TreeMap, 인덱스 = DB, 불변 데이터 = 정렬 후 검색."

---

다음 Unit으로

• HashMap 내부 구조 ★★★ 학습 준비 완료 (Phase 6 의 정점)
• hashCode 와 equals 의 관계가 궁금하다
• 해시 충돌과 트리화 (Java 8+) 를 만날 준비 완료