STUDY NOTE · 개념 정리
자바 컬렉션 프레임워크 정리: List, Set, Map 구현체 비교와 선택 기준
Java
자바 컬렉션 프레임워크는 데이터 묶음을 다루는 인터페이스와 구현체의 모음이다. 순서와 중복이 필요하면List, 중복을 없애려면Set, 키로 찾으려면Map을 고르고, 그다음 순서·정렬·성능 요구에 따라 구현체를 고른다. 기본 구현체들은 스레드 안전하지 않다.
1. 구조
Iterable
└─ Collection
├─ List : ArrayList, LinkedList, (Vector)
├─ Set : HashSet, LinkedHashSet, TreeSet
└─ Queue : ArrayDeque, PriorityQueue, LinkedList
└─ Deque : ArrayDeque, LinkedList
Map (Collection을 상속하지 않음) : HashMap, LinkedHashMap, TreeMap, (Hashtable)
| 인터페이스 | 순서 | 중복 | 핵심 용도 |
| List | 인덱스 순서 유지 | 허용 | 순서 있는 목록 |
| Set | 구현체에 따라 다름 | 불허 | 중복 제거, 포함 여부 확인 |
| Queue / Deque | 넣은 순서 또는 우선순위 | 허용 | 대기열, 스택 |
| Map | 구현체에 따라 다름 | 키 불허, 값 허용 | 키로 값 조회 |
2. List 구현체
| 구현체 | 내부 구조 | get(i) | 끝에 추가 | 중간 삽입·삭제 | 비고 |
| ArrayList | 동적 배열 | O(1) | 분할 상환 O(1) | O(n) | 대부분의 경우 기본 선택 |
| LinkedList | 이중 연결 리스트 | O(n) | O(1) | 위치를 찾는 데 O(n) | Deque로도 쓸 수 있음 |
"LinkedList는 중간 삽입이 O(1)"이라는 말은 삽입할 노드를 이미 알고 있을 때만 맞다. 인덱스로 위치를 찾는 데 O(n)이 들고, 노드가 메모리에 흩어져 있어 CPU 캐시 효율도 나쁘다. 그래서 실무에서는 거의 항상 ArrayList가 빠르다.
3. Set 구현체
| 구현체 | 내부 구조 | 순서 | add / contains | null |
| HashSet | HashMap | 보장 안 함 | 평균 O(1) | 1개 허용 |
| LinkedHashSet | LinkedHashMap | 삽입 순서 | 평균 O(1) | 1개 허용 |
| TreeSet | 레드-블랙 트리 (TreeMap) | 정렬 순서 | O(log n) | 자연 순서 비교 시 불가 |
HashSet은 내부적으로 HashMap의 키만 쓰는 구조다. 그래서 중복 판단은 hashCode()와 equals()로 하고, TreeSet은 compareTo()(또는 Comparator) 결과가 0이면 같은 원소로 본다.
4. Map 구현체
| 구현체 | 순서 | get / put | null 키 | 용도 |
| HashMap | 보장 안 함 | 평균 O(1) | 1개 허용 | 기본 선택 |
| LinkedHashMap | 삽입 순서 (옵션: 접근 순서) | 평균 O(1) | 1개 허용 | 순서 유지, LRU 캐시 |
| TreeMap | 키 정렬 순서 | O(log n) | 자연 순서 비교 시 불가 | 범위 검색 (floorKey, subMap) |
| Hashtable | 보장 안 함 | O(1) + 락 | 불가 | 레거시 |
| ConcurrentHashMap | 보장 안 함 | 평균 O(1) | 불가 (키·값 모두) | 멀티스레드 환경 |
5. Queue와 Deque
| 구현체 | 특징 | 용도 |
| ArrayDeque | 원형 배열, 양끝 삽입·삭제 O(1) | 스택과 큐 모두 이걸로 |
| PriorityQueue | 이진 힙, 삽입·꺼내기 O(log n) | 우선순위 큐, 다익스트라 |
| Stack | Vector 상속, synchronized | 레거시, ArrayDeque로 대체 |
6. 불변 컬렉션과 고정 크기 리스트
| 생성 방법 | add/remove | set | null | 원본과의 관계 |
| List.of(...) | 불가 | 불가 | 불가 (NPE) | 독립된 불변 리스트 |
| Arrays.asList(...) | 불가 (크기 고정) | 가능 | 가능 | 원본 배열과 연결됨 |
| Collections.unmodifiableList(list) | 불가 | 불가 | 원본 따름 | 원본의 읽기 전용 뷰 (원본이 바뀌면 같이 바뀜) |
수정 불가 메서드를 호출하면 UnsupportedOperationException이 난다. 메서드에서 내부 리스트를 반환할 때 불변 복사본(List.copyOf)이나 읽기 전용 뷰로 넘기면 바깥에서 내부 상태를 바꾸지 못한다.
7. 순회 중 삭제: ConcurrentModificationException
ArrayList, HashMap 등의 반복자는 fail-fast다. 향상된 for문으로 순회하면서 컬렉션 자체의 remove를 호출하면 구조 변경을 감지해 예외를 던진다.
for (String s : list) {
if (s.isEmpty()) list.remove(s); // ConcurrentModificationException 가능
}
list.removeIf(String::isEmpty); // 권장
Iterator<String> it = list.iterator(); // 또는 반복자의 remove 사용
while (it.hasNext()) {
if (it.next().isEmpty()) it.remove();
}
8. 실제로 어떻게 적용되나
- 조회용 맵 만들기: 주문 목록과 상품 목록을 따로 조회한 뒤 주문마다 상품을 찾을 때, 상품 리스트를
Map<Long, Product>로 바꿔 두면 이중 반복문(O(n·m))이 O(n + m)이 된다. - 순서가 있는 중복 제거: 화면에 보여 줄 카테고리 목록에서 중복을 없애되 원래 순서를 지키려면
HashSet이 아니라LinkedHashSet을 쓴다. - 간단한 LRU 캐시:
LinkedHashMap을 접근 순서 모드로 만들고removeEldestEntry를 오버라이드하면 가장 오래 안 쓴 항목이 자동으로 빠진다.
class LruCache<K, V> extends LinkedHashMap<K, V> {
private final int max;
LruCache(int max) {
super(16, 0.75f, true); // true: 접근 순서
this.max = max;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > max;
}
}
9. 면접 질문으로 정리
- Q. ArrayList와 LinkedList의 차이는? ArrayList는 동적 배열이라 인덱스 접근이 O(1)이고 중간 삽입·삭제가 O(n)이다. LinkedList는 이중 연결 리스트라 인덱스 접근이 O(n)이고, 위치를 알면 삽입·삭제가 O(1)이다. 캐시 효율 때문에 대부분 ArrayList가 빠르다.
- Q. HashMap, LinkedHashMap, TreeMap의 차이는? HashMap은 순서를 보장하지 않고 평균 O(1), LinkedHashMap은 삽입(또는 접근) 순서를 유지하며 평균 O(1), TreeMap은 키 정렬 순서를 유지하며 O(log n)이다.
- Q. List.of와 Arrays.asList의 차이는? List.of는 완전히 불변이고 null을 허용하지 않는다. Arrays.asList는 크기만 고정이라 set은 되고 add·remove는 안 되며, 원본 배열과 연결돼 있다.
- Q. 순회 중 삭제하면 왜 예외가 나나? 반복자가 생성 이후의 구조 변경을 감지하면 ConcurrentModificationException을 던지는 fail-fast 방식이기 때문이다. Iterator.remove나 removeIf를 쓴다.
- Q. 멀티스레드에서 HashMap 대신 무엇을 쓰나? ConcurrentHashMap을 쓴다. Hashtable이나 synchronizedMap보다 락 범위가 좁아 동시 처리 성능이 좋다.