기타 기술
Java Collection의 시간 복잡도
곰돌이볼
2023. 6. 10. 10:46
List의 시간복잡도
| add() | get() | contains() | remove() | |
| ArrayList | O(1) | O(1) | O(N) | O(N) |
| LinkedList | O(1) | O(N) | O(N) | O(1) |
| CopyonWriteArrayList | O(N) | O(1) | O(N) | O(N) |
Set
| add() | contains() | next | |
| HashSet | O(1) | O(1) | O(h/N) (h : 테이블 용량) |
| LinkedHashSet | O(1) | O(1) | O(1) |
| TreeSet | O(log N) | O(log N) | O(log N) |
Map
| get() | containsKey() | next | |
| HashMap | O(1) | O(1) | O(h/N) (h : 테이블 용량) |
| LinkedHashMap | O(1) | O(1) | O(1) |
| TreeMap | O(log N) | O(log N) | O(log N) |
Stack
| push() | pop() | peek() | search() | |
| stack | O(1) | O(1) | O(1) | O(N) |
Queue
| Offer | Peak | Poll | Size | |
| Priority Queue | O(log N) | O(1) | O(log N) | O(1) |
| LinkedList | O(1) | O(1) | O(1) | O(1) |
| ArrayDequeue | O(1) | O(1) | O(1) | O(1) |
| DelayQueue | O(log N) | O(1) | O(log N) | O(1) |