Unit 2.3 — List 3형제 (ArrayList / LinkedList / Vector)
F-LAB JAVA · 3주차 · Phase 2 · 컬렉션 프레임워크 전체 지도
📌 학습 목표
이 Unit을 끝내면 다음을 답할 수 있어야 한다.
- List 인터페이스의 본질 과 Set/Queue/Map 과의 차이는?
- ArrayList 의 내부 구조와 1.5배 확장 정책은? (2주차 복습)
- LinkedList 의 노드 사슬과 Queue/Deque 인터페이스 동시 구현?
- Vector 가 왜 Java 1.0 Legacy 인가? 왜 거의 안 쓰는가?
- CopyOnWriteArrayList 의 메커니즘과 사용 시점은?
- ArrayList 의 멀티스레드 안전성 을 어떻게 확보하나? (3가지 방법)
- 시나리오별로 어떤 List 구현체를 선택하나?
- 박승제씨가 ILIC 에서 매일 90% 쓰는 List 는?
🎯 핵심 한 문장
List 는 "순서 있는 가변 컬렉션" 이라는 의미이고, 구현체는 메모리 구조와 동시성 정책으로 갈린다.
ArrayList 는 배열 기반의 표준 — 90% 케이스 정답.
LinkedList 는 노드 사슬 기반 + Queue 역할 — 양 끝 작업 또는 Queue 필요 시.
Vector 는 Java 1.0 legacy — 거의 사용 X.
CopyOnWriteArrayList 는 읽기 많고 쓰기 적은 멀티스레드 환경의 안전한 List.
비유 — 카탈로그 진열대
| 시스템 | 비유 |
|---|---|
| ArrayList | 표준 진열대 — 번호표 매김, 한 페이지에 연속 |
| LinkedList | 메모 노트 — 각 메모가 "다음 메모 위치" 가리킴 |
| Vector | 매번 자물쇠 채우는 진열대 — 안전하지만 답답 |
| CopyOnWriteArrayList | 진열대 변경 시 통째 복사 — 보기는 빠름, 변경은 비쌈 |
→ 의도와 환경에 따라 선택.
🧭 9개 섹션 로드맵
1. List 인터페이스의 본질
2. ArrayList 의 내부 (2주차 복습 + 깊이)
3. LinkedList 의 내부 (2주차 복습 + Queue 역할)
4. Vector 의 정체 (Java 1.0 Legacy)
5. CopyOnWriteArrayList (멀티스레드)
6. 3형제 시간 복잡도 + 메모리 비교
7. ILIC 실무 — List 선택 가이드
8. 흔한 실수 + 안티패턴
9. 면접 + 자기 점검1️⃣ List 인터페이스의 본질
1.1 List 의 정의
List<E> 인터페이스의 정의:
"순서 있는 가변 컬렉션"
규칙:
- 삽입 순서 보존 (Set 과 다름)
- 인덱스 접근 가능 (get(i))
- 중복 허용 (Set 과 다름)
- 가변 크기 (배열과 다름)1.2 List 의 핵심 메서드
public interface List<E> extends Collection<E> {
// 인덱스 기반
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
// 컬렉션 메서드
boolean add(E e); // 끝에 추가
boolean remove(Object o);
boolean contains(Object o);
// 부분 리스트
List<E> subList(int from, int to);
// 순회
Iterator<E> iterator();
ListIterator<E> listIterator(); // ★ 양방향 + 추가/수정 가능
// Java 8+
default void sort(Comparator<? super E> c) { ... }
default void replaceAll(UnaryOperator<E> operator) { ... }
// ...
}핵심:
- 인덱스 접근 (Set 에 없음)
- 순서 보존
- 중복 허용
- ListIterator — 양방향 순회, 수정 가능
1.3 ListIterator 의 추가 능력
List<Shipment> list = new ArrayList<>();
// ... 데이터
ListIterator<Shipment> it = list.listIterator();
while (it.hasNext()) {
int idx = it.nextIndex();
Shipment s = it.next();
if (s.isExpired()) {
it.remove(); // 안전 삭제
}
if (s.needsUpdate()) {
it.set(s.withStatus(UPDATED)); // 현재 위치 교체
}
}
// 역방향
while (it.hasPrevious()) {
Shipment s = it.previous();
// ...
}박승제씨가 2주차 Unit 6.2 (Iterator) 에서 본 패턴.
→ List 는 Iterator + ListIterator 둘 다 제공.
→ Set 은 ListIterator 없음.
1.4 List 와 다른 컬렉션 비교
| 자료구조 | 순서 | 중복 | 인덱스 |
|---|---|---|---|
| List | ✓ | ✓ | ✓ |
| Set | △ (구현체별) | ❌ | ❌ |
| Queue | 처리 순서 | ✓ | ❌ |
| Map | △ | 키 ❌, 값 ✓ | 키로 |
→ 인덱스 + 중복 허용 + 순서 가 List 의 핵심 특성.
1.5 ILIC 에서 List 의 자연스러운 사용
@Service
public class ShipmentService {
// 가장 흔한 패턴 — DB 결과
public List<Shipment> findByStatus(ShipmentStatus status) {
return repository.findByStatus(status);
// JPA 가 ArrayList 반환
// 인터페이스는 List
}
// 도메인 객체의 컬렉션 필드
@Entity
public class Shipment {
@OneToMany
private List<Cargo> cargoes = new ArrayList<>(); // 순서 있는 화물 목록
}
// DTO 변환
public List<ShipmentResponse> getResponses(List<Shipment> shipments) {
return shipments.stream()
.map(ShipmentResponse::from)
.toList(); // Java 16+ 불변 List 반환
}
// 처리 순서가 있는 작업
public List<TaskStep> getProcessingSteps() {
return List.of(
TaskStep.VALIDATE,
TaskStep.CALCULATE_FREIGHT,
TaskStep.NOTIFY_CUSTOMER,
TaskStep.UPDATE_TRACKING
);
}
}→ List 가 가장 흔하게 등장.
1.6 자기 점검 답변
List 를 Set 대신 써야 하는 신호는?
답:
1. 순서가 의미 있을 때 (처리 단계, 화물 순서)
2. 인덱스 접근이 필요할 때
3. 중복이 허용되거나 필요할 때
4. DB 결과 같이 자연스러운 시퀀스
→ 도메인 객체의 컬렉션은 보통 List.
→ 중복 제거 + 빠른 검색이 필요하면 Set.
2️⃣ ArrayList 의 내부 (2주차 복습 + 깊이)
2.1 ArrayList 의 본질
public class ArrayList<E> implements List<E>, RandomAccess, Cloneable, Serializable {
transient Object[] elementData; // 내부 배열
private int size; // 사용 중인 요소 수
private static final int DEFAULT_CAPACITY = 10;
// ...
}박승제씨가 2주차 Unit 5.2 에서 본 것:
- 내부는
Object[]배열 - size 와 capacity 의 구분
- 1.5배 확장 정책 (
oldCapacity + (oldCapacity >> 1)) - amortized O(1) 추가
2.2 ArrayList 의 강점 복습
시간 복잡도:
- get(i): O(1) ★ 랜덤 액세스
- add(e): O(1) amortized
- add(i, e): O(n) 중간 삽입 시 이동
- remove(i): O(n)
- remove(끝): O(1)
- contains: O(n)
- indexOf: O(n)
- size: O(1)2.3 RandomAccess 마커 인터페이스
public class ArrayList<E> implements ..., RandomAccess, ... { ... }RandomAccess:
- 마커 인터페이스 (메서드 없음)
- "이 List 는 인덱스 접근이 빠르다" 표시
Collections.binarySearch등이 이 마커로 분기
// Collections.binarySearch 의 내부
public static <T> int binarySearch(List<T> list, T key, ...) {
if (list instanceof RandomAccess) {
return indexedBinarySearch(list, key); // ArrayList 용
} else {
return iteratorBinarySearch(list, key); // LinkedList 용
}
}→ ArrayList 는 RandomAccess 마커 보유.
→ LinkedList 는 없음.
2.4 메모리 다이어그램 복습
ArrayList<Shipment> list = new ArrayList<>();
list.add(s1);
list.add(s2);
list.add(s3);ArrayList 객체 (Heap):
┌──────────────────────────┐
│ Header │
│ elementData ─────────────┼──┐
│ size = 3 │ │
└──────────────────────────┘ │
│
▼
Object[] (Heap):
┌────┬────┬────┬────┬────┬─...
│ s1 │ s2 │ s3 │null│null│
└────┴────┴────┴────┴────┴
[0] [1] [2] [3] [4]
▲
│
size 가 가리키는 위치 (다음 add 위치)
capacity 는 10 (현재)→ 박승제씨가 2주차 Unit 5.2 에서 본 그림.
2.5 1.5배 확장 정책 복습
// ArrayList 의 grow() 내부
int newCapacity = oldCapacity + (oldCapacity >> 1);
// >> 1 은 비트 우측 시프트 = 2로 나눔
// 결과: 1.5 배확장 시퀀스:
10 → 15 → 22 → 33 → 49 → 73 → 109 → 163 → ...ILIC 에서 큰 List 만들 때:
// ✗ 매번 확장
List<Shipment> list = new ArrayList<>();
for (int i = 0; i < 100_000; i++) {
list.add(...); // 1.5배씩 여러 번 확장
}
// ✓ 초기 크기 지정
List<Shipment> list = new ArrayList<>(100_000);
// 또는 컬렉션 복사
List<Shipment> list = new ArrayList<>(sourceCollection); // sourceCollection.size() 로 초기화2.6 ArrayList 와 amortized O(1)
박승제씨가 2주차 Unit 5.2 에서 본 핵심 개념:
ArrayList.add(e) 가 amortized O(1) 인 이유:
대부분의 추가: O(1) (배열 끝에 단순 대입)
가끔의 확장: O(n) (배열 복사)
n 번 추가 시 총 시간:
- O(1) 작업 × (n - log_1.5(n)) 회
- O(n) 작업 × log_1.5(n) 회
- 총 O(n) → 평균 O(1)2.7 ArrayList vs 배열 vs HashMap
배열:
┌────┬────┬────┬────┐
│ 1 │ 2 │ 3 │ 4 │ 고정 크기
└────┴────┴────┴────┘
ArrayList:
┌────┬────┬────┬────┬─...
│ 1 │ 2 │ 3 │ 4 │ 가변 (1.5배 확장)
└────┴────┴────┴────┴
+ size 추적
HashMap (참고):
table[]:
[0] → null
[1] → Node(...)
[2] → null
+ 해시 기반 분포→ 박승제씨가 이제 차이를 명확히 봄.
2.8 자기 점검 답변
ArrayList 의 add(e) 가 amortized O(1) 인 이유를 한 문장으로?
답:
"1.5배 확장이 가끔 발생하지만, 전체 n번의 add 중 확장은 log_1.5(n) 번뿐이고, 확장 비용 합도 O(n) 으로 평균하면 O(1) 이 됩니다."
→ 면접 단골 질문.
3️⃣ LinkedList 의 내부 (2주차 복습 + Queue 역할)
3.1 LinkedList 의 본질
public class LinkedList<E> implements List<E>, Deque<E>, Cloneable, Serializable {
// ^^^^^^^^^
// ★ Deque 도 구현!
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; // 이전 노드
// 이중 연결 리스트
}
}핵심:
- 이중 연결 리스트 (Doubly Linked List)
- List + Deque 둘 다 구현
- 박승제씨가 2주차 Unit 5.3 에서 본 구조
3.2 LinkedList 가 List + Deque 인 의미
// List 로 사용
List<Shipment> list = new LinkedList<>();
list.add(s); // 끝에 추가
list.get(0); // 인덱스 접근 (O(n))
// Deque (Queue + Stack) 로 사용
Deque<Shipment> deque = new LinkedList<>();
deque.offerFirst(s); // 앞에 추가 O(1)
deque.offerLast(s); // 뒤에 추가 O(1)
deque.pollFirst(); // 앞에서 제거 O(1)
deque.pollLast(); // 뒤에서 제거 O(1)
// Queue 로 사용
Queue<Shipment> queue = new LinkedList<>();
queue.offer(s);
queue.poll();→ 하나의 LinkedList 가 3가지 역할.
→ 이중 연결 덕분에 양 끝 작업이 O(1).
3.3 LinkedList 의 시간 복잡도
박승제씨가 2주차 Unit 5.3 복습:
시간 복잡도:
- get(i): O(n) ★ 인덱스 접근 비싼
- add(e): O(1) 끝에 추가
- addFirst(e): O(1) 앞에 추가
- add(i, e): O(n) 중간 삽입은 인덱스 찾기 비용
- remove(끝): O(1)
- remove(0): O(1)
- remove(i): O(n)
- contains: O(n)
- size: O(1)→ 인덱스 접근은 비쌈, 양 끝 작업은 빠름.
3.4 LinkedList vs ArrayList — 박승제씨의 결론
박승제씨가 2주차 Unit 5.4 에서 본 정점:
교과서적 답:
ArrayList: 조회 빠름, 삽입/삭제 느림
LinkedList: 조회 느림, 삽입/삭제 빠름
실제 정답:
대부분 ArrayList 가 빠름!
- 캐시 효율 (연속 메모리)
- 메모리 효율 (Node 객체 없음)
- 인덱스 빠름
LinkedList 가 진짜 유리한 경우:
- 양 끝 작업 (Deque 로 사용)
- 매우 큰 List 의 앞쪽 삽입/삭제
- ListIterator 로 순회 중 삽입/삭제→ 거의 ArrayList 가 답.
3.5 LinkedList 가 Queue 로 쓰이는 일
Queue<Task> queue = new LinkedList<>();
queue.offer(task1);
queue.offer(task2);
queue.poll(); // task1이게 흔한 패턴이긴 하지만, 더 권장되는 대안:
// ArrayDeque (더 빠름)
Queue<Task> queue = new ArrayDeque<>();ArrayDeque:
- 원형 배열 기반
- 양 끝 작업 O(1)
- 메모리 효율 ↑ (Node 객체 없음)
- 캐시 효율 ↑
→ Queue 용도면 LinkedList 보다 ArrayDeque 권장.
3.6 LinkedList 의 진짜 사용처 — 거의 없음
박승제씨가 ILIC 에서 LinkedList 직접 사용:
- 알고리즘 문제 풀 때
- 매우 특수한 경우 (극단적 앞 삽입/삭제 + 인덱스 안 씀)
- 그 외엔 거의 없음
대신:
- 일반 List: ArrayList
- Queue/Deque: ArrayDeque3.7 자기 점검 답변
LinkedList 와 ArrayList 중 박승제씨가 더 자주 쓰는 것과 그 이유는?
답:
-
ArrayList 가 90% 이상
-
이유:
- DB 결과 (List findAll())
- 일반적 컬렉션
- 인덱스 접근 효율
- 캐시 친화적
- 메모리 효율
-
LinkedList 는:
- 거의 안 씀
- Queue/Deque 필요하면 ArrayDeque
4️⃣ Vector 의 정체 (Java 1.0 Legacy)
4.1 Vector 의 역사
Java 1.0 (1996):
- 컬렉션 프레임워크 (List/Set 등) 없음
- Vector, Hashtable 만 있었음
- 모든 메서드 synchronized (당시 단일 스레드만 보장 가능)
Java 1.2 (1998):
- ArrayList, HashMap 등 등장
- Vector 는 List 인터페이스 구현하도록 retrofit
- 하지만 여전히 synchronized 유지
- → Legacy 가 됨4.2 Vector 의 내부
public class Vector<E> implements List<E>, RandomAccess, ... {
protected Object[] elementData;
protected int elementCount;
protected int capacityIncrement; // ★ 확장 정책 다름
public synchronized boolean add(E e) {
modCount++;
add(e, elementData, elementCount);
return true;
}
public synchronized E get(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index);
}
return elementData(index);
}
// 모든 메서드가 synchronized!
}ArrayList 와의 차이:
- 모든 public 메서드가 synchronized
- 기본 확장 정책: 2배 (ArrayList 는 1.5배)
capacityIncrement로 사용자 정의 가능
4.3 synchronized 의 비용
public synchronized boolean add(E e) { ... }synchronized 메서드 호출 시:
1. 이 객체의 모니터 락 획득 시도
2. 다른 스레드가 락 보유 중이면 대기
3. 메서드 실행
4. 락 해제
비용:
- 락 획득/해제 오버헤드 (수십~수백 ns)
- 단일 스레드도 비용 발생
- 멀티스레드 경합 시 큰 비용 (대기)→ ArrayList 가 Vector 보다 20-30% 빠름 (벤치마크).
4.4 Vector 의 멀티스레드 안전성 — 사실은 불충분
Vector<Integer> v = new Vector<>();
// 스레드 1
if (!v.contains(5)) {
v.add(5);
}
// 스레드 2
if (!v.contains(5)) {
v.add(5);
}문제:
- 각 메서드는 synchronized
- 하지만 contains + add 사이는 비원자적
- 두 스레드 모두 contains 통과 → 둘 다 add → 중복
synchronized 메서드 != 진짜 thread-safe→ Vector 는 단일 메서드만 안전.
→ 복합 작업은 추가 동기화 필요.
4.5 Vector 안 쓰는 7가지 이유
1. Legacy (Java 1.0)
- 1998년 이후 ArrayList 가 권장
- 호환성 위해 남아있을 뿐
2. 단일 스레드도 synchronized 비용
- 90% 케이스가 단일 스레드
- 불필요한 오버헤드
3. 복합 작업 안전성 부족
- 진짜 멀티스레드 안전 보장 X
4. 더 나은 대안 존재
- 단일 스레드: ArrayList
- 멀티스레드 + 락: Collections.synchronizedList
- 멀티스레드 + lock-free: CopyOnWriteArrayList
5. 확장 정책의 메모리 낭비
- 2배 확장 (ArrayList 1.5배)
- 더 많은 메모리
6. API 일관성 부족
- addElement, elementAt 같은 old API
- List 인터페이스에 retrofit
7. Stack 상속의 문제
- Stack 이 Vector 상속 → Stack 도 legacy4.6 Vector 가 그래도 살아있는 이유
하위 호환성:
- Java 1.0~1.1 코드가 아직도 존재 가능
- 일부 라이브러리가 Vector 반환
- 제거하면 깨질 코드 너무 많음
JDK 일부 API:
- JTable 의 데이터 모델
- Swing 의 일부 컴포넌트
- 대부분 GUI 관련 (대안 없음)→ 박승제씨가 ILIC 같은 백엔드에서 만날 일 거의 없음.
4.7 Vector → ArrayList 마이그레이션
// Legacy 코드
Vector<Shipment> v = new Vector<>();
v.add(...);
// 마이그레이션
List<Shipment> list = new ArrayList<>(); // 단일 스레드면 충분
// 또는
List<Shipment> list = Collections.synchronizedList(new ArrayList<>()); // 멀티스레드
// 또는
List<Shipment> list = new CopyOnWriteArrayList<>(); // 읽기 위주4.8 자기 점검 답변
Vector 를 절대 사용하지 말아야 하는 가장 큰 이유는?
답:
1. 불필요한 synchronized 비용 (단일 스레드도)
2. 복합 작업 안전성 부족 (진짜 thread-safe 아님)
3. Legacy (Java 1.0, 더 나은 대안 존재)
4. 더 나은 대안:
- 단일 스레드: ArrayList
- 멀티스레드: ConcurrentHashMap / CopyOnWriteArrayList / Collections.synchronizedList
→ 박승제씨가 ILIC 코드 리뷰 시 Vector 보이면 즉시 ArrayList 로 교체 권장.
5️⃣ CopyOnWriteArrayList (멀티스레드)
5.1 CopyOnWriteArrayList 의 개념
public class CopyOnWriteArrayList<E> implements List<E>, ... {
private transient volatile Object[] array;
public boolean add(E e) {
synchronized (lock) {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1); // ★ 매번 복사!
newElements[len] = e;
setArray(newElements);
return true;
}
}
public E get(int index) {
return elementAt(getArray(), index); // 락 없이 읽기
}
}핵심:
- 쓰기 시마다 전체 배열 복사 (Copy-On-Write)
- 읽기는 락 없이 가능 (lock-free)
- volatile 로 가시성 보장
5.2 동작 메커니즘
시점 T1: 초기 상태
array → [A, B, C]
스레드 1: list.get(0) → A 반환 (락 없음)
스레드 2: list.get(1) → B 반환 (락 없음)
→ 둘 다 동시에 가능
시점 T2: list.add(D) 호출
1. lock 획득
2. 기존 배열 복사
3. 새 배열에 D 추가
4. array 참조 교체 (volatile 보장)
5. lock 해제
새 배열: [A, B, C, D]
→ 다른 스레드는 옛 배열 또는 새 배열 보지만, 일관성 보장
시점 T3: 다음 읽기
스레드 1: list.get(0) → A (새 배열에서)
스레드 2: list.get(3) → D5.3 Copy-On-Write 의 트레이드오프
장점:
- 읽기 매우 빠름 (락 없음, lock-free)
- 쓰기 안전 (락으로 보호)
- Iterator 가 스냅샷 사용 (변경 무관, ConcurrentModificationException 없음)
- 멀티스레드 안전 보장
단점:
- 쓰기 시 전체 복사 (n개 요소면 O(n))
- 메모리 사용 일시 2배
- 잦은 쓰기엔 부적합5.4 사용 시점
적합:
✓ 읽기 >> 쓰기 (90:10 이상)
✓ 작은 List (수십~수백)
✓ Iterator 가 자주 사용됨
✓ Event Listener 패턴
부적합:
✗ 쓰기가 많음
✗ 매우 큰 List
✗ 메모리 민감 환경5.5 ILIC 사용 예 — Event Listener
@Service
public class ShipmentEventBus {
private final List<ShipmentEventListener> listeners = new CopyOnWriteArrayList<>();
public void register(ShipmentEventListener l) {
listeners.add(l); // 가끔 발생 (O(n) 복사)
}
public void fire(ShipmentEvent event) {
// 빈번 발생, 락 없이 안전
for (ShipmentEventListener l : listeners) {
l.onEvent(event);
}
}
}→ Listener 패턴의 표준.
5.6 일반 List 의 멀티스레드 안전 방법 3가지
// 1. CopyOnWriteArrayList — 읽기 위주
List<Shipment> list1 = new CopyOnWriteArrayList<>();
// 2. Collections.synchronizedList — 명시적 락
List<Shipment> list2 = Collections.synchronizedList(new ArrayList<>());
// 단, 순회 시 외부 동기화 필요
synchronized (list2) {
for (Shipment s : list2) { ... }
}
// 3. 직접 ReadWriteLock — 세밀한 제어
private final ReadWriteLock lock = new ReentrantReadWriteLock();
private final List<Shipment> list3 = new ArrayList<>();
public void add(Shipment s) {
lock.writeLock().lock();
try {
list3.add(s);
} finally {
lock.writeLock().unlock();
}
}
public Shipment get(int i) {
lock.readLock().lock();
try {
return list3.get(i);
} finally {
lock.readLock().unlock();
}
}5.7 비교 표
| 방법 | 읽기 | 쓰기 | 메모리 | 적합 |
|---|---|---|---|---|
| Vector | synchronized | synchronized | 기본 | 거의 안 씀 |
| CopyOnWriteArrayList | lock-free | O(n) 복사 | 일시 2배 | 읽기 >> 쓰기 |
| synchronizedList | synchronized | synchronized | 기본 | 균형 |
| ReadWriteLock + ArrayList | shared lock | exclusive lock | 기본 | 세밀 제어 |
5.8 자기 점검 답변
CopyOnWriteArrayList 가 적합한 가장 명확한 시나리오는?
답:
- Event Listener 패턴:
- 빈번한 fire (읽기)
- 가끔의 register/unregister (쓰기)
- 변경 중에도 안전한 순회 필요
다른 적합 사례:
- 설정값 캐시 (드물게 변경, 자주 읽음)
- 권한 정책 목록 (변경 적음)
- DNS 캐시 같은 시간 기반 데이터
6️⃣ 3형제 시간 복잡도 + 메모리 비교
6.1 시간 복잡도 비교표
| 작업 | ArrayList | LinkedList | Vector | CopyOnWriteArrayList |
|---|---|---|---|---|
get(i) | O(1) | O(n) | O(1) | O(1) |
add(e) 끝 | O(1) amortized | O(1) | O(1) synchronized | O(n) 복사 |
add(0, e) 앞 | O(n) | O(1) | O(n) synchronized | O(n) |
add(i, e) 중간 | O(n) | O(n) | O(n) | O(n) |
remove(끝) | O(1) | O(1) | O(1) | O(n) |
remove(0) | O(n) | O(1) | O(n) | O(n) |
contains | O(n) | O(n) | O(n) | O(n) |
size | O(1) | O(1) | O(1) | O(1) |
| 멀티스레드 읽기 | unsafe | unsafe | safe (synchronized) | safe (lock-free) |
| 멀티스레드 쓰기 | unsafe | unsafe | safe (synchronized) | safe (락 + 복사) |
6.2 공간 복잡도
n 개 요소:
ArrayList:
배열: ~ n × 4 bytes (참조)
객체 자체: ~ 40 bytes
capacity 초과분: ~ 25% (LoadFactor 0.75)
대략: n × 5-6 bytes (참조만)
LinkedList:
Node 객체: n × ~ 40 bytes (item + next + prev + Header)
+ 객체 자체
대략: n × ~ 40 bytes (HashMap 의 Node 와 유사)
→ ArrayList 의 ~ 6배 메모리
Vector:
ArrayList 와 비슷 (~ n × 5 bytes)
+ capacity 초과분
CopyOnWriteArrayList:
단일 시점: ArrayList 와 비슷
쓰기 시: 일시 2배 (옛 + 새 배열)6.3 실제 벤치마크 (가상)
1,000,000 개 요소 작업:
add 1백만 회 (끝에):
ArrayList: 30 ms
LinkedList: 80 ms (Node 객체 생성)
Vector: 50 ms (synchronized 오버헤드)
CopyOnWriteArrayList: 매우 느림 (매번 복사)
get 1백만 회 (랜덤 인덱스):
ArrayList: 5 ms
LinkedList: 매우 느림 (O(n) 매번)
Vector: 15 ms (synchronized 오버헤드)
CopyOnWriteArrayList: 5 ms
contains 1백만 회:
ArrayList: 매우 느림 (O(n))
LinkedList: 매우 느림
→ 어차피 Set 으로 변환해야 함
순회 1바퀴:
ArrayList: 매우 빠름 (캐시 친화)
LinkedList: ArrayList 의 약 2배 느림
Vector: synchronized 비용
CopyOnWriteArrayList: ArrayList 와 비슷→ ArrayList 가 거의 모든 경우 최고.
6.4 선택 트리
박승제씨의 List 선택 트리:
1. 멀티스레드 환경?
YES → 2
NO → ArrayList (90% 정답)
2. 읽기 >> 쓰기?
YES → CopyOnWriteArrayList
NO → 3
3. 균형 잡힌 멀티스레드?
→ Collections.synchronizedList(new ArrayList<>())
또는 ReadWriteLock + ArrayList
또는 Concurrent 컬렉션 고려 (List 대신 ConcurrentMap 등)
거의 절대 안 쓰는 것:
- Vector
- Stack
- LinkedList (Queue 필요 시도 ArrayDeque 권장)6.5 90:9:1 법칙
ILIC 에서 List 사용:
90%: ArrayList
- DB 결과
- 도메인 객체 컬렉션
- DTO 변환
- 일반 작업
9%: 다른 List
- CopyOnWriteArrayList (Listener)
- Collections.synchronizedList (멀티스레드)
- List.of (불변 상수)
1%: 특수
- LinkedList (드물게)
- 그 외
0%: Legacy
- Vector
- Stack6.6 자기 점검 답변
박승제씨가 ILIC 에서 List 선택 시 90% 의 답은?
답:
- ArrayList
- 이유:
- 인덱스 접근 빠름 (O(1))
- 캐시 효율 (연속 메모리)
- 메모리 효율 (Node 객체 없음)
- amortized O(1) 추가
- 단일 스레드면 동기화 불필요
- JPA Repository 가 반환하는 표준
→ "List 가 필요한가? → ArrayList" 의 직관.
7️⃣ ILIC 실무 — List 선택 가이드
7.1 시나리오별 선택
시나리오 1 — DB 결과
// JPA Repository
List<Shipment> findByStatus(ShipmentStatus status);
// 반환: ArrayList (JPA 의 표준)
// Service 에서
List<Shipment> shipments = repository.findByStatus(ShipmentStatus.ACTIVE);
// 변수 타입: List<Shipment> (인터페이스)
// 실제 구현: ArrayList→ ArrayList 가 자연스럽게 사용됨.
시나리오 2 — 도메인 객체의 컬렉션 필드
@Entity
public class Shipment {
@Id
private Long id;
@OneToMany(mappedBy = "shipment", cascade = CascadeType.ALL)
private List<Cargo> cargoes = new ArrayList<>();
// ↑ ArrayList — 순서 있는 화물 목록
public void addCargo(Cargo c) {
cargoes.add(c);
c.setShipment(this);
}
}→ JPA + ArrayList.
시나리오 3 — DTO 변환
public List<ShipmentResponse> toResponses(List<Shipment> shipments) {
return shipments.stream()
.map(ShipmentResponse::from)
.toList(); // Java 16+ 불변 List
// 또는 Java 8+
// .collect(Collectors.toList()); // 가변 ArrayList
}→ Stream + List.
시나리오 4 — 불변 상수 목록
public class FreightPolicy {
public static final List<String> SUPPORTED_PORTS = List.of(
"BUSAN", "INCHEON", "GWANGYANG", "ULSAN", "PYEONGTAEK"
);
public static final List<Integer> WEEKEND_DAYS = List.of(
Calendar.SATURDAY, Calendar.SUNDAY
);
}→ List.of (Java 9+) 불변 List.
시나리오 5 — 이벤트 리스너
@Service
public class ShipmentEventBus {
private final List<ShipmentEventListener> listeners = new CopyOnWriteArrayList<>();
public void subscribe(ShipmentEventListener listener) {
listeners.add(listener);
}
@Async
public void publish(ShipmentEvent event) {
listeners.forEach(l -> l.onEvent(event));
}
}→ CopyOnWriteArrayList.
시나리오 6 — 멀티스레드 공유 List
@Service
public class ShipmentTracker {
// ❌ 일반 ArrayList 멀티스레드 위험
private final List<TrackingEntry> entries = new ArrayList<>();
// ✓ Concurrent (Queue 가 더 적합할 수도)
private final BlockingQueue<TrackingEntry> entries =
new LinkedBlockingQueue<>();
// ✓ synchronized List (균형)
private final List<TrackingEntry> entries =
Collections.synchronizedList(new ArrayList<>());
// ✓ CopyOnWriteArrayList (읽기 위주)
private final List<TrackingEntry> entries =
new CopyOnWriteArrayList<>();
}→ 시나리오에 따라 다름.
시나리오 7 — 큰 List 초기 크기
public List<ShipmentReport> generateReports(int expectedCount) {
List<ShipmentReport> reports = new ArrayList<>(expectedCount);
// ↑ 초기 크기 지정으로 확장 회피
for (Shipment s : repository.findAll()) {
reports.add(generateReport(s));
}
return reports;
}→ 큰 List 는 초기 크기 지정.
7.2 List 선택 의사결정 표
| 시나리오 | 선택 | 이유 |
|---|---|---|
| 일반 컬렉션 | ArrayList | 90% 정답 |
| DB 결과 | ArrayList (JPA 자동) | 인덱스 + 캐시 |
| 도메인 컬렉션 | ArrayList | 순서 + 효율 |
| 불변 상수 | List.of | 안전 + 가벼움 |
| Listener 패턴 | CopyOnWriteArrayList | 읽기 lock-free |
| 멀티스레드 균형 | synchronizedList | 락 보장 |
| 작업 큐 (멀티스레드) | BlockingQueue | 큐 의도 명확 |
| 양 끝 작업 | ArrayDeque | LinkedList 보다 빠름 |
7.3 ILIC 코드 리뷰 체크리스트
List 사용 검토:
타입:
- 인터페이스 List<E> 로 선언?
- 구현체 적절?
- Legacy (Vector, Stack) 사용 안 함?
성능:
- 큰 List 에 초기 크기 지정?
- contains 빈번 → Set 으로 변환?
- 인덱스 접근 빈번 → ArrayList?
멀티스레드:
- 공유 List 인데 ArrayList?
- synchronizedList 의 순회 시 외부 동기화?
- CopyOnWriteArrayList 의 쓰기 비용 고려?
함수형:
- subList 의 view 특성 인식?
- Arrays.asList 의 고정 크기?
- List.of 의 불변성?
매개변수:
- 매개변수 List 변경 (side effect)?
- 방어적 복사 필요?7.4 박승제씨의 ILIC 표준 패턴
// 표준 패턴 1: 일반 List 사용
List<Shipment> shipments = new ArrayList<>();
// 표준 패턴 2: 초기 크기 지정
List<Shipment> shipments = new ArrayList<>(expectedSize);
// 표준 패턴 3: 컬렉션 복사
List<Shipment> copy = new ArrayList<>(originalList);
// 표준 패턴 4: 불변 List
List<String> ports = List.of("BUSAN", "INCHEON");
// 표준 패턴 5: Stream 결과
List<ShipmentResponse> responses = shipments.stream()
.map(ShipmentResponse::from)
.toList();
// 표준 패턴 6: 멀티스레드 listener
List<EventListener> listeners = new CopyOnWriteArrayList<>();
// 표준 패턴 7: 방어적 반환
public List<Cargo> getCargoes() {
return List.copyOf(this.cargoes); // 불변 사본
}7.5 자기 점검 답변
ILIC 에서 List 잘못 선택하는 가장 흔한 케이스는?
답:
1. 멀티스레드 환경에 일반 ArrayList → CopyOnWriteArrayList 또는 synchronized
2. Queue 가 필요한데 LinkedList → ArrayDeque
3. 불변이 필요한데 ArrayList → List.of
4. 큰 List 에 초기 크기 미지정 → new ArrayList<>(size)
5. List.contains 빈번 → Set 으로 변환
8️⃣ 흔한 실수 + 안티패턴
8.1 실수 1 — Vector 사용
// ❌ Legacy
Vector<Shipment> v = new Vector<>();해결:
// ✓ ArrayList (단일 스레드)
List<Shipment> list = new ArrayList<>();
// ✓ synchronizedList (멀티스레드 균형)
List<Shipment> list = Collections.synchronizedList(new ArrayList<>());
// ✓ CopyOnWriteArrayList (읽기 위주)
List<Shipment> list = new CopyOnWriteArrayList<>();8.2 실수 2 — LinkedList 로 인덱스 루프
// ❌ LinkedList 인데 인덱스 루프
LinkedList<Shipment> list = ...;
for (int i = 0; i < list.size(); i++) {
Shipment s = list.get(i); // O(n)! × n = O(n²)
}해결:
// ✓ for-each (Iterator 사용)
for (Shipment s : list) {
// ...
}
// ✓ Stream
list.stream().forEach(...);8.3 실수 3 — Arrays.asList 함정
// ❌ 함정
String[] arr = {"A", "B", "C"};
List<String> list = Arrays.asList(arr);
list.add("D"); // UnsupportedOperationException!
list.remove(0); // UnsupportedOperationException!Arrays.asList:
- 고정 크기 List 반환
- 배열의 view (배열 변경 시 List 도 변경)
- set/get 만 가능
해결:
// ✓ 가변 ArrayList
List<String> list = new ArrayList<>(Arrays.asList(arr));
// ✓ Java 9+
List<String> list = List.of(arr); // 불변8.4 실수 4 — subList 의 view 특성
List<Shipment> big = ...;
List<Shipment> sub = big.subList(0, 10);
big.clear(); // 또는 다른 변경
sub.get(0); // ConcurrentModificationException!subList:
- 원본 List 의 view
- 원본 변경 → sub 무효화
- 별도 List 가 아님
해결:
// ✓ 명시적 복사
List<Shipment> independent = new ArrayList<>(big.subList(0, 10));8.5 실수 5 — 순회 중 변경
// ❌ ConcurrentModificationException
List<Shipment> list = new ArrayList<>();
for (Shipment s : list) {
if (s.isExpired()) {
list.remove(s); // CME!
}
}해결:
// ✓ Iterator.remove
Iterator<Shipment> it = list.iterator();
while (it.hasNext()) {
if (it.next().isExpired()) it.remove();
}
// ✓ Java 8+ removeIf
list.removeIf(Shipment::isExpired);박승제씨가 2주차 Unit 6.2 에서 본 패턴.
8.6 실수 6 — List.of 변경 시도
List<String> immutable = List.of("A", "B");
immutable.add("C"); // ❌ UnsupportedOperationExceptionList.of:
- Java 9+ 불변 List
- 변경 메서드 호출 시 예외
해결:
// ✓ 가변 사본
List<String> mutable = new ArrayList<>(List.of("A", "B"));
mutable.add("C"); // OK8.7 실수 7 — synchronizedList 순회 시 락 누락
List<Shipment> list = Collections.synchronizedList(new ArrayList<>());
// ❌ 순회 중 동기화 없음
for (Shipment s : list) {
// 다른 스레드가 변경 가능 → CME
}해결:
// ✓ 외부 동기화
synchronized (list) {
for (Shipment s : list) {
// ...
}
}→ synchronizedList 는 단일 메서드만 동기화.
→ 순회 등 복합 작업은 외부 동기화 필수.
8.8 실수 8 — 큰 List 매번 add
// ❌ 매번 확장
List<Shipment> list = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) {
list.add(...);
}
// ✓ 초기 크기 지정
List<Shipment> list = new ArrayList<>(1_000_000);8.9 ILIC List 안티패턴 체크리스트
박승제씨가 ILIC 에서 피할 것:
레거시:
- Vector → ArrayList 또는 멀티스레드 대안
- Stack → ArrayDeque
구현체 선택:
- LinkedList 인덱스 루프 → ArrayList 또는 for-each
- Queue 에 LinkedList → ArrayDeque
- 불변 필요한데 ArrayList → List.of
멀티스레드:
- 공유 ArrayList → 동기화 또는 Concurrent
- synchronizedList 순회 → 외부 동기화
함정:
- Arrays.asList 후 add → new ArrayList<>()
- List.of 변경 → 가변 사본
- subList 후 원본 변경 → 별도 복사
성능:
- 큰 List 초기 크기 미지정 → 지정
- contains 빈번 → Set 으로 변환9️⃣ 면접 + 자기 점검
9.1 면접 단골 질문 매핑
| Q | 핵심 답변 |
|---|---|
| ArrayList vs LinkedList | 배열 vs 노드 사슬, 인덱스 vs 양 끝 작업 |
| ArrayList 확장 정책 | 1.5배, oldCapacity + (oldCapacity >> 1) |
| Vector 안 쓰는 이유 | Legacy + synchronized 비용 + 더 나은 대안 |
| Stack 안 쓰는 이유 | Vector 상속, ArrayDeque 권장 |
| CopyOnWriteArrayList 메커니즘 | 쓰기 시 전체 복사, 읽기 lock-free |
| CopyOnWriteArrayList 사용처 | Listener 패턴, 읽기 위주 |
| synchronizedList 순회 시? | 외부 동기화 필요 |
| LinkedList 가 Deque? | List + Deque 둘 다 구현 |
| ArrayDeque vs LinkedList | 배열 기반 vs Node, ArrayDeque 권장 |
| RandomAccess 인터페이스? | 인덱스 빠른 List 표시, ArrayList O, LinkedList X |
| Arrays.asList 함정? | 고정 크기, add 불가 |
| subList 함정? | 원본 view, 원본 변경 시 무효화 |
9.2 자기 점검 체크리스트
기본 이해
- List 인터페이스의 본질을 안다
- ArrayList 의 내부 (배열 + 1.5배 확장) 를 안다
- LinkedList 의 내부 (이중 연결 + Deque 구현) 를 안다
- Vector 의 legacy 이유를 안다
- CopyOnWriteArrayList 의 메커니즘을 안다
시간 복잡도
- ArrayList 시간 복잡도를 외운다
- LinkedList 시간 복잡도를 외운다
- amortized O(1) 의 의미를 설명할 수 있다
- CopyOnWriteArrayList 의 O(n) 쓰기를 안다
실전 적용
- 시나리오에 맞는 List 선택 가능
- Vector/Stack 피함
- 멀티스레드 환경의 List 선택
- 큰 List 초기 크기 지정
- Arrays.asList, List.of, subList 함정 회피
면접 대비
- 3형제 + CopyOnWriteArrayList 비교 설명
- Vector 안 쓰는 이유 7가지
- CopyOnWriteArrayList 적합 사례
- ILIC 표준 패턴 7가지
🎯 핵심 요약 — 3줄 정리
1. List 3형제 + CopyOnWriteArrayList 의 본질
- ArrayList = 배열 기반 (90% 정답)
- LinkedList = 이중 연결 노드 사슬 + Deque 구현
- Vector = Java 1.0 Legacy (사용 X)
- CopyOnWriteArrayList = 읽기 lock-free, 쓰기 O(n) 복사
2. 시간 복잡도
- ArrayList: get O(1), add amortized O(1), 중간 작업 O(n)
- LinkedList: get O(n), 양 끝 O(1), 중간 작업 O(n)
- Vector: ArrayList + synchronized 비용
- CopyOnWriteArrayList: 읽기 빠름, 쓰기 매우 느림
3. ILIC 실무 90:9:1
- 90% ArrayList
- 9% CopyOnWriteArrayList, synchronizedList, List.of
- 1% 특수 (LinkedList 등)
- 0% Vector, Stack
📚 다음으로...
Unit 2.4 — Queue (FIFO 자료구조)
이번 Unit에서 List 3형제를 봤다면, 다음은 Queue 자료구조.
- FIFO 의 정확한 의미
- Queue 의 메서드 페어 (offer/add, poll/remove, peek/element)
- ArrayDeque vs LinkedList vs PriorityQueue
- BlockingQueue (멀티스레드)
- ILIC 실무 시나리오 (작업 큐, 이벤트 큐)
Phase 2 진행 상황
🚀 Phase 2 — 컬렉션 프레임워크 전체 지도
✅ Unit 2.1 배열의 한계와 컬렉션의 등장
✅ Unit 2.2 Set 3형제
✅ Unit 2.3 List 3형제 ← 여기
⏭ Unit 2.4 Queue (FIFO 자료구조)
⏭ Unit 2.5 Map 5형제
⏭ Unit 2.6 컬렉션 전체 지도 정리3주차 누적 진행
✅ Phase 1 — Pass by Value (1.1 ~ 1.3 완주)
🚀 Phase 2 — 컬렉션 프레임워크 (3/6 진행)
총: 6/43 Unit 작성 (약 14%)
Software Developer