개발/자바
자바 컬렉션 정리 (Collection)
Walon_
2021. 11. 9. 15:35
1. Set
- 중복을 허용하지 않는다.
- 순서를 보장하지 않는다.
- index접근이 불가하고 iterator를 사용해야 한다.
2. Map
- key와 value의 쌍으로 이루어짐.
- key의 중복은 허용하지 않지만 value의 중복은 허용한다.
3. List
- 중복을 허용한다.
- 순서를 보장한다.
Stack - https://walon-h.tistory.com/17?category=971067
4. Queue
- 먼저 들어간 값이 먼저 나오는 구조
- 삽입과 삭제 연산만 한다.
Queue / Deque - https://walon-h.tistory.com/16
Prioirty Queue - https://walon-h.tistory.com/20
=== 시간복잡도 ===
더보기
※ List
| Add | Remove | Get | Contains | Data Structure | |
| ArrayList | O(1) | O(n) | O(1) | O(n) | Array |
| LinkedList | O(1) | O(1) | O(n) | O(n) | Linked List |
| CopyonWrite ArrayList |
O(n) | O(n) | O(1) | O(n) | Array |
※ Set
| Add | Contains | Next | Data Structure | |
| HashSet | O(1) | O(1) | O(h/n) | Hash Table |
| LinkedHashSet | O(1) | O(1) | O(1) | Hash Table + Linked List |
| EnumSet | O(1) | O(1) | O(1) | Bit Vector |
| TreeSet | O(log n) | O(log n) | O(log n) | Red-black tree |
| CopyonWrite ArraySet |
O(n) | O(n) | O(1) | Array |
| ConcurrentSkipList | O(log n) | O(log n) | O(1) | Skip List |
※ Queue
| Offer | Peak | Poll | Size | Data Structure | |
| PriorityQueue | O(log n) | O(1) | O(log n) | O(1) | Priority Heap |
| LinkedList | O(1) | O(1) | O(1) | O(1) | Array |
| ArrayDequeue | O(1) | O(1) | O(1) | O(1) | Linked List |
| Concurrent LinkedQueue |
O(1) | O(1) | O(1) | O(1) | Linked List |
| ArrayBlocking Queue |
O(1) | O(1) | O(1) | O(n) | Array |
| Prioririty BlockingQueue |
O(log n) | O(1) | O(log n) | O(1) | Priority Heap |
| Synchronous Queue |
O(1) | O(1) | O(1) | O(1) | None! |
| DelayQueue | O(log n) | O(1) | O(log n) | O(1) | Priority Heap |
| Linked BlockingQueue |
O(1) | O(1) | O(1) | O(1) | Linked List |
※ 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 |
| Concurrent HashMap |
O(1) | O(1) | O(h / n) | Hash Tables |
| ConcurrentSkip ListMap |
O(log n) | O(log n) | O(1) | Skip List |
출처 : http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html