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 |
|
CopyonWriteArrayList |
O(n) |
O(n) |
O(1) |
O(n) |
Array |
|
Stack |
O(1) |
O(1) |
O(1) |
O(n) |
Vector 기반 |
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 |
|
CopyonWriteArraySet |
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 |
|
ConcurrentLinkedQueue |
O(1) |
O(1) |
O(1) |
O(n) |
Linked List |
|
ArrayBlockingQueue |
O(1) |
O(1) |
O(1) |
O(1) |
Array |
|
PriorirityBlockingQueue |
O(log n) |
O(1) |
O(log n) |
O(1) |
Priority Heap |
|
SynchronousQueue |
O(1) |
O(1) |
O(1) |
O(1) |
None! |
|
DelayQueue |
O(log n) |
O(1) |
O(log n) |
O(1) |
Priority Heap |
|
LinkedBlockingQueue |
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 |
|
ConcurrentHashMap |
O(1) |
O(1) |
O(h / n) |
Hash Tables |
|
ConcurrentSkipListMap |
O(log n) |
O(log n) |
O(1) |
Skip List |
정렬 알고리즘 비교
| 정렬 이름 | 공간복잡도 | 시간복잡도 | ||
| 최악 | 최선 | 평균 | 최악 | |
| Bubble Sort | O(1) | O(n) | O(n2) | O(n2) |
| Heapsort | O(1) | O(n log n) | O(n log n) | O(n log n) |
| Insertion Sort | O(1) | O(n) | O(n2) | O(n2) |
| Mergesort | O(n) | O(n log n) | O(n log n) | O(n log n) |
| Quicksort | O(log n) | O(n log n) | O(n log n) | O(n2) |
| Selection Sort | O(1) | O(n2) | O(n2) | O(n2) |
| Shell Sort | O(1) | O(n) | O(n log n2) | O(n log n2) |
| Smooth Sort | O(1) | O(n) | O(n log n) | O(n log n) |
자료구조별 비교
| 자료구조이름 | 평균 경우 | 최악의경우 | ||||
| Search | Insert | Delete | Search | Insert | Delete | |
| Array | O(n) | N/A | N/A | O(n) | N/A | N/A |
| ArrayList | O(log n) | O(n) | O(n) | O(log n) | O(n) | O(n) |
| Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Doubly Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Stack | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |
| Hash table | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) |
| Binary Search Tree | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) |
| B-Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
| Red-Black tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
참고 Big O 그래프
'To be Developer > JAVA' 카테고리의 다른 글
| Comparator 객체 정리 (Lambda, Stream, 2중비교 포함) (0) | 2020.04.08 |
|---|---|
| 가비지 컬렉터란 무엇일까? (0) | 2019.11.21 |
| [펌글] POJO란 무엇인가??? (0) | 2018.03.05 |
| [JAVA]Scanner 사용시 가끔 입력을 안받고 넘기는 이유 (0) | 2017.01.18 |
| 자바스크립트 달력소스 (0) | 2017.01.16 |