Unit 5.4 — 삽입/삭제 효율의 진짜 이유 (코드 검증)
F-LAB JAVA · 2주차 · Phase 5 · 컬렉션 프레임워크 내부 구조
🏁 Phase 5 마지막 Unit
📌 학습 목표
이 Unit을 끝내면 다음을 답할 수 있어야 한다.
- "LinkedList가 삽입/삭제에 유리하다"는 말은 언제 진실이고 언제 거짓인가?
- 위치 찾기 비용과 실제 작업 비용 의 차이는?
- 같은 빅 O(n) 작업이 ArrayList와 LinkedList에서 왜 실제 성능이 다른가?
- 시나리오별 의사결정 — 진짜 자료구조 선택 기준은?
- 자바 표준 라이브러리 코드로 위 내용을 직접 검증할 수 있는가?
- Phase 5 졸업 — 자료구조 선택 마스터가 됐는가?
🎯 핵심 한 문장
"LinkedList가 삽입/삭제에 유리"는 절반의 진실이다.
정확히는 "이미 위치를 안다면 LinkedList의 실제 삽입/삭제는 O(1)".
그러나 위치를 모른다면 찾는 데 O(n) → 결국 ArrayList와 같거나 더 느림.
두 비용을 분리해서 이해하는 것이 자료구조 선택의 진짜 기준이다.
비유 — 책장에 책 끼우기 vs 메모 끼우기
| 시스템 | 비유 |
|---|---|
| ArrayList 중간 삽입 | 책장 7번 자리 책을 8번으로, 8번 책을 9번으로... 모두 한 칸씩 이동 후 7번에 새 책 |
| LinkedList 중간 삽입 | 7번 자리 메모를 일단 찾기 → 그 메모 직전에 새 메모 끼우기 (이전·다음 화살표만 다시 그림) |
| 둘 다 7번 찾기 비용 | 책장: 즉시 (인덱스). 메모: 처음부터 6번 거쳐서 |
| 둘 다 실제 끼우기 비용 | 책장: 7번부터 모두 이동 (느림). 메모: 화살표 두 개 변경 (빠름) |
→ "찾기"와 "끼우기"는 다른 비용.
🧭 9개 섹션 로드맵
1. 흔한 오해 분해
2. 위치 찾기 vs 실제 작업 분리
3. ArrayList의 비용 정밀
4. LinkedList의 비용 정밀
5. 자바 표준 라이브러리 코드로 검증
6. 시나리오별 의사결정
7. ILIC 실무 — 진짜 자료구조 선택 가이드
8. 흔한 실수 + 디버깅
9. 면접 + Phase 5 졸업 시험1️⃣ 흔한 오해 분해
1.1 학교/책의 일반적인 설명
교과서:
"ArrayList는 조회가 빠르고 삽입/삭제가 느림"
"LinkedList는 조회가 느리고 삽입/삭제가 빠름"→ 반쯤 맞고 반쯤 틀림.
1.2 실제 측정 결과
시나리오 A: "맨 앞에 100만 번 추가"
ArrayList.add(0, e): 약 30초 (매번 O(n) 이동)
LinkedList.add(0, e): 약 50ms (매번 O(1))
→ LinkedList가 600배 빠름. 교과서가 맞는 듯.
시나리오 B: "중간에 100번 삽입 (인덱스로)"
ArrayList.add(size/2, e): 약 1ms
LinkedList.add(size/2, e): 약 100ms (매번 size/2 탐색)
→ ArrayList가 100배 빠름! 교과서와 반대?1.3 진실
"LinkedList가 삽입/삭제에 유리"는 다음 조건일 때만:
1. 양 끝(앞/뒤) 에서 작업
2. 또는 이미 Iterator로 순회 중인 위치에서
위치를 인덱스로 찾아야 한다면:
→ LinkedList의 O(n) 탐색 비용 발생
→ ArrayList와 비교해도 별다른 이점 없음→ 상황에 따라 다르다.
1.4 자기 점검 답변
다음 두 명제 중 어느 쪽이 옳은가?
"LinkedList는 삽입/삭제가 빠르다"
"LinkedList는 삽입/삭제가 빠를 수도 있고 느릴 수도 있다"
답: 후자.
- 양 끝/Iterator 위치: 빠름
- 인덱스로 찾은 위치: 더 느림 (탐색 O(n))
2️⃣ 위치 찾기 vs 실제 작업 분리
2.1 두 비용의 분리
삽입/삭제 작업 = 위치 찾기 비용 + 실제 작업 비용
ArrayList:
위치 찾기 (인덱스로): O(1)
실제 삽입/삭제: O(n) ← 메모리 복사
LinkedList:
위치 찾기 (인덱스로): O(n) ← 사슬 따라가기
실제 삽입/삭제: O(1) ← 참조 변경만2.2 핵심 통찰
ArrayList의 비용은 "끝쪽" 에 따라 다름:
맨 뒤 작업: 찾기 0 + 작업 0 = O(1)
맨 앞 작업: 찾기 0 + 작업 n = O(n)
중간 작업: 찾기 0 + 작업 n/2 = O(n)
LinkedList의 비용은 "접근 방식" 에 따라 다름:
Iterator로 위치 알면: 찾기 0 + 작업 0 = O(1)
앞/뒤 (head/tail): 찾기 0 + 작업 0 = O(1)
인덱스로: 찾기 n/2 + 작업 0 = O(n)2.3 두 자료구조의 진짜 성능 비교
시나리오: 100만 항목 List에서 작업
| 작업 | ArrayList | LinkedList |
|---|---|---|
| add(끝) | O(1) 빠름 | O(1) but Node 객체 생성 |
| add(0) | O(n) 느림 | O(1) 빠름 ★ |
| add(중간, 인덱스로) | O(n) | O(n) (탐색 비용) |
| Iterator로 중간 add | O(n) (탐색 후 add)* | O(1) ★ |
| get(i) | O(1) ★ | O(n) 느림 |
| contains | O(n) | O(n) (캐시 효율로 ArrayList 빠름) |
| remove(끝) | O(1) | O(1) |
| remove(0) | O(n) | O(1) ★ |
| 전체 순회 | O(n) ★ (캐시 효율) | O(n) (느림) |
* ArrayList도 Iterator 사용 가능하지만, 결국 add 시 메모리 복사 발생2.4 자기 점검 답변
"두 자료구조 모두 빅 O가 O(n)인데, 왜 실제 성능이 다른가?"
답:
1. 상수 차이가 큼 — 메모리 복사 vs 참조 변경
2. 캐시 효율 — 연속 메모리 vs 흩어진 메모리
3. 객체 생성 — LinkedList는 Node 객체마다 생성
4. GC 부담 — LinkedList의 Node들이 추가 부담
→ 빅 O는 같아도 실제 성능 큰 차이.
3️⃣ ArrayList의 비용 정밀
3.1 ArrayList.add(int index, E element) 소스
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index, // ← 핵심: 복사
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}핵심 라인:
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);→ index 이후의 s - index 개 요소를 한 칸씩 뒤로 복사.
3.2 비용 분석
arraycopy의 비용:
복사할 요소 수에 비례
add(0, e): size 개 복사
add(size/2, e): size/2 개 복사
add(size-1, e): 1 개 복사
add(size, e): 0 개 복사 (또는 끝 추가 = O(1))
→ 평균 size/2 → O(n)3.3 arraycopy의 실제 동작
System.arraycopy 는 네이티브 메서드:
- C로 구현됨
- 매우 빠른 메모리 복사 (memcpy)
- 캐시 라인 활용
- CPU의 SIMD 명령어 사용 가능
하지만 요소 수에 비례.
100만 요소 add(0, e):
arraycopy 1번 호출
100만 참조 (4 bytes × 1M = 4MB) 복사
→ 약 1-2ms→ "한 번의 작업이지만 1-2ms"
3.4 ArrayList.remove(int index) 소스
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked")
E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}→ 삭제도 arraycopy로 모든 뒷 요소를 앞으로 이동.
3.5 끝 작업은 정말 빠른가?
list.add(e); // 끝 추가- arraycopy 호출 안 됨 (i + 1 = size, 복사할 게 없음)
- 단순히
elementData[size++] = e - 진짜 O(1) (확장 발생 안 한다면)
list.remove(list.size() - 1); // 끝 제거- arraycopy의
newSize - i = 0→ 호출 안 됨 - 단순히
es[size-1] = null; size--; - 진짜 O(1).
→ ArrayList의 양 끝 중 끝 작업은 매우 빠름.
4️⃣ LinkedList의 비용 정밀
4.1 LinkedList.add(int index, E element) 소스
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index)); // ← 핵심: node(index)
}핵심: node(index) 가 위치를 찾는 부분.
4.2 node(int index) — 위치 찾기
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}→ O(n/2) 최악, 평균 O(n/4), 빅 O는 O(n).
4.3 linkBefore — 실제 삽입
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
}→ Node 1개 생성 + 참조 3-4개 변경.
→ O(1).
4.4 비용 종합
linkedList.add(index, e):
node(index): O(n) ← 탐색
linkBefore(): O(1) ← 실제 삽입
총: O(n)→ 인덱스 기반 삽입은 ArrayList와 같은 O(n).
4.5 Iterator를 통한 add — 진짜 O(1)
LinkedList<Shipment> list = ...;
ListIterator<Shipment> it = list.listIterator(50); // 50번 위치까지 이동 (O(n))
while (조건) {
it.add(newShipment); // ← 이 add는 O(1) ★
}ListIterator.add():
- 현재 Iterator 위치 알고 있음
- node(index) 호출 안 함
- linkBefore 만 수행 → O(1)
→ Iterator 위치가 정해진 후 반복 작업은 LinkedList의 진짜 강점.
4.6 양 끝 작업 — head/tail 직접 접근
linkedList.add(0, e); // 또는 addFirst(e)public void addFirst(E e) {
linkFirst(e);
}
void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
}→ node(index) 안 호출. 진짜 O(1).
4.7 자기 점검 — 진짜 비용
LinkedList의 add(index, e) 진짜 비용:
| 인덱스 | 비용 |
|---|---|
| 0 (= addFirst) | O(1) |
| size (= addLast = add) | O(1) |
| 다른 인덱스 (인덱스로) | O(n) |
| Iterator 위치 | O(1) |
→ "LinkedList 삽입 빠름"은 양 끝 또는 Iterator일 때만5️⃣ 자바 표준 라이브러리 코드로 검증
5.1 OpenJDK 17 소스 직접 보기
# OpenJDK 다운로드 후
src/java.base/share/classes/java/util/ArrayList.java
src/java.base/share/classes/java/util/LinkedList.java또는 IntelliJ IDEA에서 Ctrl+클릭으로 표준 라이브러리 소스 탐색.
5.2 RandomAccess 인터페이스
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, ...ArrayList는 RandomAccess 구현.
LinkedList는 안 함.
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, ...→ "인덱스 접근이 효율적인 List" 마커 인터페이스.
표준 라이브러리에서 사용:
// Collections.binarySearch
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size() < BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key); // 인덱스 사용
else
return Collections.iteratorBinarySearch(list, key); // Iterator 사용
}→ 표준 라이브러리도 LinkedList엔 Iterator 사용.
5.3 직접 벤치마크 코드
// 100만 항목 List에서 작업
List<Integer> arrayList = new ArrayList<>(1_000_000);
List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < 1_000_000; i++) {
arrayList.add(i);
linkedList.add(i);
}
// 시나리오 A: 끝에 추가
long start = System.nanoTime();
for (int i = 0; i < 10_000; i++) {
arrayList.add(i);
}
long arrayEndTime = System.nanoTime() - start;
start = System.nanoTime();
for (int i = 0; i < 10_000; i++) {
linkedList.add(i);
}
long linkedEndTime = System.nanoTime() - start;
System.out.println("끝 추가:");
System.out.println(" ArrayList: " + arrayEndTime / 1_000_000 + "ms");
System.out.println(" LinkedList: " + linkedEndTime / 1_000_000 + "ms");예상 결과:
끝 추가:
ArrayList: 1ms (확장 없음)
LinkedList: 5ms (Node 객체 생성 1만번)
→ ArrayList가 빠름5.4 시나리오 B: 맨 앞 추가
start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
arrayList.add(0, i); // O(n) × 1000
}
start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
linkedList.addFirst(i); // O(1) × 1000
}예상 결과:
맨 앞 추가:
ArrayList: 약 1000ms (1조 작업)
LinkedList: 약 5ms (간단한 참조 변경)
→ LinkedList가 200배 빠름 ★5.5 시나리오 C: 중간 인덱스 삽입
start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int idx = arrayList.size() / 2;
arrayList.add(idx, i);
}
start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
int idx = linkedList.size() / 2;
linkedList.add(idx, i); // ← node(idx)가 O(n)
}예상 결과:
중간 삽입 (인덱스로):
ArrayList: 약 500ms (메모리 복사)
LinkedList: 약 30,000ms (탐색 + 작업)
→ ArrayList가 60배 빠름! 의외놀라운 결과: 중간 삽입에서 LinkedList가 ArrayList보다 느림.
이유:
- LinkedList: 매번 O(n) 탐색 + O(1) 삽입 = O(n)
- ArrayList: O(1) 인덱스 + O(n) 복사 = O(n)
- 둘 다 빅 O는 같지만, 메모리 복사가 사슬 탐색보다 빠름 (캐시 효율)
5.6 진짜 LinkedList가 빛나는 경우 — ListIterator
// LinkedList의 진짜 강점
LinkedList<Integer> linkedList = ...;
ListIterator<Integer> it = linkedList.listIterator();
// 한 번 위치 설정 후 반복
for (int i = 0; i < linkedList.size() / 2; i++) {
it.next(); // 위치 이동
}
start = System.nanoTime();
for (int i = 0; i < 1000; i++) {
it.add(i); // O(1)
}예상 결과:
Iterator 위치 삽입:
ArrayList Iterator add: 약 500ms (여전히 메모리 복사)
LinkedList Iterator add: 약 5ms ★
→ 100배 빠름→ LinkedList의 진짜 가치는 Iterator 패턴.
6️⃣ 시나리오별 의사결정
6.1 의사결정 트리
어떤 작업이 주요?
├─ 인덱스 접근 빈번 (get(i))
│ → ArrayList
│
├─ 끝 추가만
│ → ArrayList (캐시 효율 + 가벼움)
│
├─ 양 끝 작업 (앞+뒤)
│ → ArrayDeque (LinkedList보다 빠름)
│
├─ Iterator 순회 + 중간 작업
│ → LinkedList (Iterator add/remove 빠름)
│
├─ 매우 큰 컬렉션 + 가끔 삽입
│ → ArrayList (메모리 효율)
│
└─ 일반적인 경우
→ ArrayList ★ (대부분)6.2 실제 90% 케이스
// 대부분 ArrayList
List<Shipment> shipments = new ArrayList<>();
// Queue/Deque 필요 시
Deque<Task> queue = new ArrayDeque<>();
// LinkedList는 거의 안 씀→ 박승제씨가 매일 쓰는 패턴.
6.3 자료구조 선택 매트릭스
| 시나리오 | 추천 | 이유 |
|---|---|---|
| 인덱스 접근 | ArrayList | get(i) O(1) |
| 끝 추가만 | ArrayList | O(1) + 캐시 효율 |
| 앞 추가 빈번 | LinkedList 또는 ArrayDeque | O(1) |
| 양 끝 작업 | ArrayDeque | 캐시 효율 |
| 중간 삽입 (Iterator) | LinkedList | Iterator add O(1) |
| 중간 삽입 (인덱스) | ArrayList | 캐시 효율로 더 빠름 |
| 큰 컬렉션 + 메모리 중요 | ArrayList | 8배 적은 메모리 |
| 알고리즘 학습 | LinkedList | 자료구조 이해 |
6.4 함정 — 흔한 잘못된 선택
잘못된 선택 1:
"삽입/삭제 많아서 LinkedList"
→ 인덱스 접근이면 ArrayList가 더 빠름
잘못된 선택 2:
"조회만 하니까 LinkedList 써도 됨"
→ 조회만 해도 ArrayList가 캐시 효율로 빠름
잘못된 선택 3:
"Queue 필요해서 LinkedList"
→ ArrayDeque가 더 빠름
잘못된 선택 4:
"Stack 필요해서 Stack 클래스"
→ Stack은 Legacy. ArrayDeque 사용7️⃣ ILIC 실무 — 진짜 자료구조 선택 가이드
7.1 ILIC 코드 리뷰 체크리스트
List 사용 확인:
☐ ArrayList인가? (대부분의 경우 OK)
☐ LinkedList면 왜? (보통 잘못된 선택)
☐ Vector 사용? (즉시 제거)
☐ 초기 크기 지정? (큰 List는 권장)
사용 패턴 확인:
☐ List.contains 빈번? → Set으로 변환
☐ list.get(i) for 루프? → for-each
☐ list.add(0, e)? → ArrayDeque 검토
☐ list.remove(0)? → ArrayDeque 검토7.2 ILIC 표준 패턴
패턴 1 — 도메인 객체 보관
// ✓ 가장 흔한 케이스
List<Shipment> shipments = repository.findAll();
List<Cargo> cargoes = shipment.getCargoes();→ ArrayList. 인덱스 접근, 순회 모두 효율적.
패턴 2 — DTO 변환
// ✓ Stream + List
List<ShipmentResponse> responses = shipments.stream()
.map(ShipmentResponse::from)
.toList(); // Java 16+→ 내부적으로 ArrayList.
패턴 3 — 작업 큐
// ✓ ArrayDeque
Deque<Task> taskQueue = new ArrayDeque<>();
taskQueue.offer(task);
Task t = taskQueue.poll();→ LinkedList 대신 ArrayDeque.
패턴 4 — 작업 스택
// ✓ ArrayDeque
Deque<Frame> callStack = new ArrayDeque<>();
callStack.push(frame);
Frame f = callStack.pop();→ Stack 클래스 절대 사용 X.
패턴 5 — 빈번한 양쪽 작업
// 슬라이딩 윈도우
Deque<Integer> window = new ArrayDeque<>();
window.offerFirst(value);
window.pollLast();→ ArrayDeque.
7.3 멀티스레드 시 고려
// ❌ 멀티스레드에서 ArrayList
private List<Shipment> shared = new ArrayList<>(); // 데이터 깨짐
// ✓ Synchronized List (낡은 방식)
private List<Shipment> shared = Collections.synchronizedList(new ArrayList<>());
// ✓ CopyOnWriteArrayList (읽기 위주)
private List<Shipment> shared = new CopyOnWriteArrayList<>();CopyOnWriteArrayList:
- 쓰기 시 전체 복사 (비쌈)
- 읽기는 lock-free (빠름)
- 읽기 >> 쓰기 패턴에 적합
7.4 ILIC 권장 패턴 — 명시적 선언
// 인터페이스로 선언 (구현체 교체 가능)
List<Shipment> list = new ArrayList<>();
Deque<Task> queue = new ArrayDeque<>();
Set<Long> ids = new HashSet<>();
Map<Long, Shipment> cache = new HashMap<>();
// 멀티스레드라면
ConcurrentMap<Long, Shipment> sharedCache = new ConcurrentHashMap<>();7.5 자료구조 변경 시 체크리스트
ArrayList → ArrayDeque로 마이그레이션 시:
☐ 인덱스 접근 코드 있나?
☐ get(i), set(i) 사용?
☐ Sublist 사용?
☐ null 요소 허용? (ArrayDeque는 null 거부)
LinkedList → ArrayDeque:
☐ Iterator로 중간 작업? (ArrayDeque는 다름)
☐ null 요소? (LinkedList는 허용, ArrayDeque는 안 함)7.6 1주차 자료와의 통합 (HashMap PPT)
박승제씨가 1주차에서 만든 HashMap PPT 자료와 통합:
Phase 5 종합:
- List: ArrayList (배열 기반)
- Set: HashSet (HashMap 기반)
- Map: HashMap (해시 테이블)
- Queue: ArrayDeque (원형 배열)
모두 배열 기반 → 캐시 효율 + 메모리 효율 ↑
LinkedList는 노드 기반 → 메모리 부담 ↑8️⃣ 흔한 실수 + 디버깅
실수 1 — "삽입/삭제 빠르다고 들었는데" 신화
// ❌ 잘못된 추론
List<Item> list = new LinkedList<>(); // 삽입/삭제 많으니까
// 그런데 코드:
for (int i = 0; i < list.size(); i++) { // O(n²)!
if (list.get(i).needsUpdate()) {
list.remove(i);
}
}해결:
list.removeIf(Item::needsUpdate); // 안전 + 효율실수 2 — Stack 사용
// ❌ Legacy
Stack<Frame> stack = new Stack<>();
stack.push(...);
stack.pop();// ✓ ArrayDeque
Deque<Frame> stack = new ArrayDeque<>();
stack.push(...);
stack.pop();Stack 클래스는 Vector 상속 → synchronized 무거움.
실수 3 — Queue 인터페이스에 LinkedList
// △ 동작하지만 ArrayDeque보다 느림
Queue<Task> queue = new LinkedList<>();// ✓ ArrayDeque
Queue<Task> queue = new ArrayDeque<>();실수 4 — 멀티스레드 ArrayList
// ❌
List<Shipment> shared = new ArrayList<>();
@Async
public void process(Shipment s) {
shared.add(s); // 동시 호출 시 깨짐
}// ✓
List<Shipment> shared = Collections.synchronizedList(new ArrayList<>());
// 또는
List<Shipment> shared = new CopyOnWriteArrayList<>(); // 읽기 위주실수 5 — 빈도 측정 안 함
// 어떤 자료구조가 적합? 모른 채로 선택해결:
- JMH 벤치마크
- 실제 사용 패턴 측정
- 그 후 자료구조 선택
실수 6 — Iterator 사용 안 함
// LinkedList인데 인덱스 루프
LinkedList<Shipment> list = ...;
for (int i = 0; i < list.size(); i++) {
process(list.get(i)); // O(n²)
}→ for-each 또는 Iterator. 반드시.
실수 7 — 잘못된 capacity
// 작은 List에 큰 capacity
List<String> small = new ArrayList<>(10000);
small.add("A"); // 1개만 들어감
// 9999 슬롯 메모리 낭비→ 진짜 클 것 같을 때만 큰 capacity.
디버깅 도구
# 실시간 자료구조 분석
jmap -histo:live <PID> | grep -E "(ArrayList|LinkedList|HashMap)"
# Heap dump 분석 — MAT
# - List/Map의 size 분포
# - 의외로 큰 컬렉션 찾기
# JFR
jcmd <PID> JFR.start filename=collections.jfr9️⃣ 면접 + Phase 5 졸업 시험
9.1 면접 단골 질문 매핑
| Q | 핵심 답변 |
|---|---|
| ArrayList vs LinkedList 차이? | 배열 vs 노드 사슬. 메모리/캐시/시간 |
| "삽입/삭제 빠르다"의 함정? | 위치 알 때만. 인덱스로 찾으면 동일 |
| 진짜 LinkedList 사용처? | 거의 없음. ArrayDeque 권장 |
| ArrayDeque 장점? | 배열 기반 + 양 끝 O(1) + null 거부 |
| Stack 클래스 사용? | Legacy. ArrayDeque 사용 |
| Queue 인터페이스 구현? | ArrayDeque 권장 |
| 멀티스레드 List? | CopyOnWriteArrayList 또는 synchronizedList |
| RandomAccess 인터페이스? | 인덱스 접근 효율적인 List 표시 |
| ListIterator의 의미? | LinkedList의 진짜 강점 (O(1) 삽입) |
| Phase 5 종합 결론? | 90% ArrayList, 9% ArrayDeque, 1% LinkedList |
9.2 자기 점검 체크리스트
기본 이해
- 위치 찾기와 실제 작업의 분리를 안다
- ArrayList의 진짜 비용을 안다 (arraycopy)
- LinkedList의 진짜 비용을 안다 (node 탐색)
- Iterator의 진짜 의미를 안다
- RandomAccess 인터페이스를 안다
실전 적용
- 시나리오별 자료구조 선택 가능
- ArrayList vs ArrayDeque 결정 가능
- 멀티스레드 컬렉션 선택 가능
- 코드 리뷰 시 자료구조 검토
- JMH 벤치마크로 검증 가능
면접 대비 — 5분 답변
- 자료구조 선택의 진짜 기준
- LinkedList "삽입 빠르다" 함정
- ArrayDeque의 우월성
- 멀티스레드 컬렉션 선택
- 실무 자료구조 선택 가이드
9.3 🏆 Phase 5 졸업 시험
다음 질문에 즉답할 수 있다면 Phase 5 졸업:
- List/Set/Map 각각의 본질적 의미와 시간 복잡도는?
- ArrayList의 1.5배 확장 정책의 메모리 효과는?
- LinkedList의 인덱스 접근이 O(n)인 이유와 최적화는?
- ArrayList vs LinkedList의 진짜 성능 차이 5가지는?
- ILIC에서 List/Queue/Stack 각각 어떤 구현체를 선택하나?
모두 답할 수 있다면 Phase 5 완주. 자료구조 선택 마스터.
🎯 핵심 요약 — 3줄 정리
1. 비용은 두 부분으로 나뉜다
- 위치 찾기 비용 + 실제 작업 비용
- ArrayList: O(1) + O(n) = O(n)
- LinkedList (인덱스): O(n) + O(1) = O(n)
- LinkedList (Iterator/끝): 0 + O(1) = O(1)
2. 같은 빅 O여도 실제 성능 큰 차이
- 메모리 복사 (arraycopy) vs 사슬 탐색
- 캐시 효율: ArrayList ★
- 메모리 효율: ArrayList ★ (8배 적음)
3. ILIC 실무 — 90:9:1 법칙
- 90%: ArrayList
- 9%: ArrayDeque (Queue/Stack/Deque)
- 1%: LinkedList (특수 케이스)
- 0%: Vector, Stack (legacy)
🏆 Phase 5 완주 — 자료구조 선택 마스터
🚀 Phase 5 — 컬렉션 내부 구조
✅ Unit 5.1 List/Set/Map의 본질적 차이
✅ Unit 5.2 ArrayList 내부
✅ Unit 5.3 LinkedList 내부
✅ Unit 5.4 삽입/삭제 효율의 진짜 이유 ← 여기, Phase 5 완주
→ 박승제씨는 이제 자료구조 선택 마스터Phase 5 후 박승제씨가 가진 능력
- ✓ 시나리오별 정확한 자료구조 선택
- ✓ 메모리/시간 복잡도 정확히 판단
- ✓ 코드 리뷰 시 자료구조 검토
- ✓ Legacy 클래스(Vector, Stack) 즉시 식별
- ✓ 멀티스레드 환경 안전 선택
- ✓ JMH로 검증
- ✓ 면접에서 자료구조 질문 자신감
📚 다음으로...
Phase 6 — Reflection & Iterator
이번 Phase에서 자료구조의 정수를 봤다면, 다음은 자료구조와 메서드를 동적으로 다루는 메커니즘.
- Reflection이 무엇이고 왜 필요한가
- Iterator 패턴의 본질
- Spring DI, JPA, Jackson 등이 Reflection을 어떻게 활용
- 성능 함정과 최적화
- ILIC 코드에서의 활용
→ Phase 5가 컬렉션의 정수였다면, Phase 6은 그 컬렉션을 동적으로 다루기.
2주차 진행 상황
✅ Phase 1 — 자바 변수 ↔ 메모리 매핑 (1.1 ~ 1.6 완주)
✅ Phase 2 — JVM 메서드 실행 메커니즘 (2.1 ~ 2.4 완주)
✅ Phase 3 — 바이트코드와 상수 풀 (3.1 ~ 3.4 완주, 정점)
✅ Phase 4 — G1 GC 심화 (4.1 ~ 4.5 완주, 운영 마스터)
✅ Phase 5 — 컬렉션 내부 구조 (5.1 ~ 5.4 완주, 자료구조 마스터) ← 여기
🚀 Phase 6 — Reflection & Iterator (다음)
⏭ Phase 7 — Buffer작성한 2주차 학습자료
Phase 1: 6개 Unit (1.1 ~ 1.6)
Phase 2: 4개 Unit (2.1 ~ 2.4)
Phase 3: 4개 Unit (3.1 ~ 3.4) ★ 정점
Phase 4: 5개 Unit (4.1 ~ 4.5) — 운영 마스터
Phase 5: 4개 Unit (5.1 ~ 5.4) — 자료구조 마스터
─────────────────────────────
누적: 23개 Unit
2주차의 약 85% 완주이제 2주차의 본격적 학습이 거의 마무리.
남은 Phase 6, 7은 보너스 + 응용.
Software Developer