✅ ArrayList 주요 연산 시간 복잡도
| 메서드 | 시간 복잡도 (Best / Avg / Worst) | 설명 |
|---|---|---|
add(E e) | O(1) / O(1) / O(n) | 끝에 추가할 때 평균적으로 O(1), 하지만 용량 초과 시 배열 확장 발생 |
add(int index, E e) | O(1) / O(n) / O(n) | 중간 삽입 → 이후 요소들 뒤로 밀기 필요 |
get(int index) | O(1) | 배열 인덱스 접근 |
set(int index, E e) | O(1) | 인덱스 위치에 값 덮어쓰기 |
remove(int index) | O(1) / O(n) / O(n) | 중간 제거 시 이후 요소 앞으로 당기기 필요 |
remove(Object o) | O(n) | 선형 탐색 후 remove(index) |
contains(Object o) | O(n) | 앞에서부터 순차 탐색 |
indexOf(Object o) | O(n) | 앞에서부터 순차 탐색 |
lastIndexOf(Object o) | O(n) | 뒤에서부터 순차 탐색 |
size() | O(1) | 저장된 요소 수 반환 |
isEmpty() | O(1) | 비어 있는지 확인 |
clear() | O(n) | 배열의 참조를 null로 초기화 |
toArray() | O(n) | 배열 복사 |
ensureCapacity(int min) | O(n) | 명시적으로 용량 확보 (배열 복사 발생 가능) |
trimToSize() | O(n) | 실제 크기로 배열 줄임 (메모리 절약 목적) |
iterator() / listIterator() | O(1) | 반복자 객체 생성 |
✅ LinkedList 주요 메서드와 시간 복잡도
| 메서드 | 시간 복잡도 (Best / Avg / Worst) | 설명 |
|---|---|---|
add(E e) | O(1) / O(1) / O(1) | 뒤에 추가 (addLast) — 꼬리 참조로 빠름 |
addFirst(E e) / addLast(E e) | O(1) / O(1) / O(1) | 양 끝 삽입 — Deque 특성 |
add(int index, E e) | O(1) / O(n) / O(n) | 중간 삽입 — index까지 순회 필요 |
get(int index) | O(1) / O(n) / O(n) | 양쪽 끝은 빠르지만 중간은 느림 |
set(int index, E e) | O(1) / O(n) / O(n) | get(index) 후 덮어쓰기 |
remove(int index) | O(1) / O(n) / O(n) | index까지 순회 + 연결 재조정 |
remove(Object o) | O(n) | 처음부터 탐색 |
removeFirst() / removeLast() | O(1) | 머리/꼬리 제거 |
contains(Object o) | O(n) | 처음부터 탐색 |
indexOf(Object o) / lastIndexOf(Object o) | O(n) | 앞/뒤에서 탐색 |
size() | O(1) | 내부 변수로 관리 |
clear() | O(n) | 모든 노드 연결 해제 |
peekFirst() / peekLast() | O(1) | 양 끝 조회 |
pollFirst() / pollLast() | O(1) | 양 끝 제거 |
push(E e) | O(1) | addFirst(e)와 동일 |
pop() | O(1) | removeFirst()와 동일 |
iterator() / listIterator() | O(1) (생성) | 단, 순회는 O(n) |
✅ HashMap 주요 메서드와 시간 복잡도
| 메서드 | 시간 복잡도 (평균 / 최악) | 설명 |
|---|---|---|
put(K key, V value) | O(1) / O(n) | 키-값 쌍 추가 (동일 키 존재 시 덮어씀) |
get(Object key) | O(1) / O(n) | 키에 해당하는 값 반환 |
remove(Object key) | O(1) / O(n) | 키-값 쌍 제거 |
containsKey(Object key) | O(1) / O(n) | 키 존재 여부 확인 |
containsValue(Object value) | O(n) | 값 존재 여부 확인 (선형 탐색) |
size() | O(1) | 저장된 엔트리 수 반환 |
isEmpty() | O(1) | 맵이 비었는지 확인 |
clear() | O(1) | 모든 엔트리 제거 |
keySet() | O(1) (생성) / 순회는 O(n) | 키 집합 반환 |
values() | O(1) (생성) / 순회는 O(n) | 값 컬렉션 반환 |
entrySet() | O(1) (생성) / 순회는 O(n) | 키-값 쌍 집합 반환 |
getOrDefault(K key, V default) | O(1) / O(n) | 키가 없으면 기본값 반환 |
putIfAbsent(K key, V value) | O(1) / O(n) | 키가 없을 때만 추가 |
✅ 내부 구조 (간단 설명)
- 내부적으로 배열 + 연결 리스트 또는 배열 + 트리(Node) 구성
- Java 8부터는 해시 충돌이 일정 이상 발생 시 해당 버킷을 LinkedList → Tree로 변환하여 최악 시간 복잡도를 O(log n)으로 개선합니다.
- key의 hashCode() → 인덱스로 변환 → equals() 비교로 중복 여부 확인
✅ HashSet 주요 메서드와 시간 복잡도
| 메서드 | 시간 복잡도 (평균 / 최악) | 설명 |
|---|---|---|
add(E e) | O(1) / O(n) | 요소 추가 (중복이면 무시) |
remove(Object o) | O(1) / O(n) | 요소 제거 |
contains(Object o) | O(1) / O(n) | 요소 존재 여부 확인 |
size() | O(1) | 요소 개수 반환 |
isEmpty() | O(1) | 비어 있는지 여부 |
clear() | O(1) | 모든 요소 제거 |
iterator() | O(1) (생성), 순회는 O(n) | 요소 반복자 반환 |
toArray() | O(n) | 배열로 변환 |
✅ 내부 구조 (간단 설명)
HashSet은 내부에서HashMap<E, Object>을 사용- 값은 key로 저장되고,
value는 더미 객체 (PRESENT = new Object())
✅ ArrayDeque 주요 메서드와 시간 복잡도
| 메서드 | 시간 복잡도 (평균 / 최악) | 설명 |
|---|---|---|
addFirst(E e) | O(1) / O(n) | 앞에 삽입, 용량 초과 시 확장 발생 |
addLast(E e) | O(1) / O(n) | 뒤에 삽입 |
offerFirst(E e) | O(1) / O(n) | 앞에 삽입 (실패 시 false 반환) |
offerLast(E e) | O(1) / O(n) | 뒤에 삽입 |
removeFirst() / remove() | O(1) | 앞 요소 제거 (예외 발생 가능) |
removeLast() | O(1) | 뒤 요소 제거 |
pollFirst() | O(1) | 앞 요소 제거 (null 반환) |
pollLast() | O(1) | 뒤 요소 제거 |
getFirst() / element() | O(1) | 앞 요소 반환 (제거 X, 예외 가능) |
getLast() | O(1) | 뒤 요소 반환 |
peekFirst() | O(1) | 앞 요소 조회 (null 반환) |
peekLast() | O(1) | 뒤 요소 조회 |
push(E e) | O(1) / O(n) | = addFirst() (스택용) |
pop() | O(1) | = removeFirst() (스택용) |
contains(Object o) | O(n) | 선형 탐색 |
size() | O(1) | 요소 개수 반환 |
clear() | O(n) | 내부 배열 null 처리 |
✅ TreeSet 주요 메서드와 시간 복잡도
| 메서드 | 시간 복잡도 (평균 / 최악) | 설명 |
|---|---|---|
add(E e) | O(log n) | 요소 추가 (자동 정렬됨) |
remove(Object o) | O(log n) | 요소 제거 |
contains(Object o) | O(log n) | 포함 여부 검사 |
first() / last() | O(log n) | 최소 / 최대 요소 반환 |
ceiling(E e) / floor(E e) | O(log n) | e 이상 / 이하인 가장 가까운 값 |
higher(E e) / lower(E e) | O(log n) | e보다 큰 / 작은 값 중 가장 가까운 값 |
pollFirst() / pollLast() | O(log n) | 첫/마지막 요소 반환 및 제거 |
isEmpty() / size() | O(1) | 비었는지, 크기 |
clear() | O(n) | 전체 비우기 |
iterator() | O(1) 생성, 순회 O(n) | 오름차순 반복자 반환 |
descendingIterator() | O(1) 생성, 순회 O(n) | 내림차순 반복자 반환 |
subSet(from, to) | O(log n) | 범위 부분 집합 |
headSet(to) / tailSet(from) | O(log n) | 하위/상위 집합 |
- 자동 정렬이 필요한 경우
Backend engineer