Java Collections 시간 복잡도 정리
List
List | Add | Remove | Get | Contains | Next | Data Structure |
---|
ArrayList | O(1) | O(n) | O(1) | O(n) | O(1) | Array |
LinkedList | O(1) | O(1) | O(n) | O(n) | O(1) | Linked List |
CopyOnWriteArrayList | O(n) | O(n) | O(1) | O(n) | O(1) | Array |
- ArrayList
- 데이터의 인덱스를 가지고 있어 데이터 검색시 빠름
- LinkedList
Set
Set | Add | Remove | Contains | Next | Size | Data Structure |
---|
HashSet | O(1) | O(1) | O(1) | O(h/n) | O(1) | Hash Table |
LinkedHashSet | O(1) | O(1) | O(1) | O(1) | O(1) | Hash Table + Linked List |
EnumSet | O(1) | O(1) | O(1) | O(1) | O(1) | Bit Vector |
TreeSet | O(log n) | O(log n) | O(log n) | O(log n) | O(1) | Red-black tree |
CopyOnWriteArraySet | O(n) | O(n) | O(n) | O(1) | O(1) | Array |
ConcurrentSkipListSet | O(log n) | O(log n) | O(log n) | O(1) | O(n) | Skip List |
- HashSet
- 객체 저장 시 순서가 없고, 중복을 허용하지 않음
- LinkedHashSet
- TreeSet
Queue
Queue | Offer | Peak | Poll | Remove | Size | Data Structure |
---|
PriorityQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap |
LinkedList | O(1) | O(1) | O(1) | O(1) | O(1) | Array |
ArrayDequeue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List |
ConcurrentLinkedQueue | O(1) | O(1) | O(1) | O(n) | O(n) | Linked List |
ArrayBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Array |
PriorirityBlockingQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap |
SynchronousQueue | O(1) | O(1) | O(1) | O(n) | O(1) | None! |
DelayQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap |
LinkedBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List |
Map
Map | Get | ContainsKey | Next | Data Structure |
---|
HashMap | O(1) | O(1) | O(h / n) | Hash Table |
LinkedHashMap | O(1) | O(1) | O(1) | Hash Table + Linked List |
IdentityHashMap | O(1) | O(1) | O(h / n) | Array |
WeakHashMap | O(1) | O(1) | O(h / n) | Hash Table |
EnumMap | O(1) | O(1) | O(1) | Array |
TreeMap | O(log n) | O(log n) | O(log n) | Red-black tree |
ConcurrentHashMap | O(1) | O(1) | O(h / n) | Hash Tables |
ConcurrentSkipListMap | O(log n) | O(log n) | O(1) | Skip List |
- HashMap
- 순서 존재 X
- LinkedHashMap
- TreeMap
시간복잡도를 산정하면 hashMap보다 linkedHashMap을 쓰는게 더 유리하겠네요.
앞으로 참고하겠습니다.