시간 복잡도 비교
| 자료 구조 | 참조 | 탐색 | 삽입 | 삭제 | 특이 사항 |
|---|---|---|---|---|---|
| 배열(Vector) | O(1) | O(n) | O(1) (맨 끝) | O(1) (맨 끝) | 중간 삽입/삭제: O(n) |
| 연결리스트 | O(n) | O(n) | O(1) | O(1) | Doubly linked list 기준 |
| 스택(Stack) | O(n) | O(n) | O(1) | O(1) | Top 참조: O(1) |
| 큐(Queue) | O(n) | O(n) | O(1) | O(1) | Front 참조: O(1) |
| 맵(Map) | O(logn) | O(logn) | O(logn) | O(logn) | Balanced tree 기반 (예: TreeMap) |
| 셋(Set) | O(logn) | O(logn) | O(logn) | O(logn) | Balanced tree 기반 |
| 해시 테이블 | O(1) | O(1) | O(1) | O(1) | 최악: O(n) (해시 충돌) |
| 힙(Heap) | O(1) | O(n) | O(logn) | O(logn) | 최대/최소 참조: O(1) |
배열 vs 연결리스트
| 비교 기준 | 배열 | 연결 리스트 |
|---|---|---|
| 메모리 공간 | 연속 O | 연속 X |
| 삽입/삭제 (맨 끝/맨 앞 제외) | O(n) | O(1) |
| n번째 요소 참조 | O(1) | O(n) |
| 탐색 | O(n) | O(n) |
결론 데이터의 추가와 삭제가 많을 경우 연결 리스트 사용이 유리, 참조가 많을 경우 배열 사용이 유리
의견 나누는 것을 좋아합니다 ლ(・ヮ・ლ)