Java Collections 시간 복잡도 정리

Yuri JI·2023년 4월 23일
0

TIL

목록 보기
8/11

List

ListAddRemoveGetContainsNextData Structure
ArrayListO(1)O(n)O(1)O(n)O(1)Array
LinkedListO(1)O(1)O(n)O(n)O(1)Linked List
CopyOnWriteArrayListO(n)O(n)O(1)O(n)O(1)Array
  • ArrayList
    • 데이터의 인덱스를 가지고 있어 데이터 검색시 빠름
  • LinkedList

Set

SetAddRemoveContainsNextSizeData Structure
HashSetO(1)O(1)O(1)O(h/n)O(1)Hash Table
LinkedHashSetO(1)O(1)O(1)O(1)O(1)Hash Table + Linked List
EnumSetO(1)O(1)O(1)O(1)O(1)Bit Vector
TreeSetO(log n)O(log n)O(log n)O(log n)O(1)Red-black tree
CopyOnWriteArraySetO(n)O(n)O(n)O(1)O(1)Array
ConcurrentSkipListSetO(log n)O(log n)O(log n)O(1)O(n)Skip List
  • HashSet
    • 객체 저장 시 순서가 없고, 중복을 허용하지 않음
  • LinkedHashSet
    • 등록한 순으로 정렬
  • TreeSet
    • 객체기준으로 정렬
    • Null 허용 X

Queue

QueueOfferPeakPollRemoveSizeData Structure
PriorityQueueO(log n)O(1)O(log n)O(n)O(1)Priority Heap
LinkedListO(1)O(1)O(1)O(1)O(1)Array
ArrayDequeueO(1)O(1)O(1)O(n)O(1)Linked List
ConcurrentLinkedQueueO(1)O(1)O(1)O(n)O(n)Linked List
ArrayBlockingQueueO(1)O(1)O(1)O(n)O(1)Array
PriorirityBlockingQueueO(log n)O(1)O(log n)O(n)O(1)Priority Heap
SynchronousQueueO(1)O(1)O(1)O(n)O(1)None!
DelayQueueO(log n)O(1)O(log n)O(n)O(1)Priority Heap
LinkedBlockingQueueO(1)O(1)O(1)O(n)O(1)Linked List

Map

MapGetContainsKeyNextData Structure
HashMapO(1)O(1)O(h / n)Hash Table
LinkedHashMapO(1)O(1)O(1)Hash Table + Linked List
IdentityHashMapO(1)O(1)O(h / n)Array
WeakHashMapO(1)O(1)O(h / n)Hash Table
EnumMapO(1)O(1)O(1)Array
TreeMapO(log n)O(log n)O(log n)Red-black tree
ConcurrentHashMapO(1)O(1)O(h / n)Hash Tables
ConcurrentSkipListMapO(log n)O(log n)O(1)Skip List
  • HashMap
    - 순서 존재 X
  • LinkedHashMap
    • 순서 존재
  • TreeMap
    • 객체를 추가하면서 저장
    • Null 허용 X
profile
안녕하세요 😄

1개의 댓글

comment-user-thumbnail
2023년 4월 24일

시간복잡도를 산정하면 hashMap보다 linkedHashMap을 쓰는게 더 유리하겠네요.
앞으로 참고하겠습니다.

답글 달기