자바 Collection 정리

jj J·2022년 10월 27일
0

JAVA

목록 보기
3/15

LIST

ArrayList

add : O(1)
remove : O(n)
get : O(1)
contain : O(n)

  • Thread Safe X
  • 데이터 추가, 삭제를 위해 임시 배열을 생성해 데이터를 복사
  • 대량의 자료를 추가/삭제 시 복사가 일어나게 되어 성능 저하를 일으킴
  • 데이터의 인덱스를 가지고 있어 데이터 검색 시 빠름

LinkedList

add : O(1)
remove : O(1)
get : O(n)
contain : O(n)

  • Thread Safe X
  • 데이터를 저장하는 각 노드가 이전 노드와 다음 노드의 상태만 알고 있다
  • 데이터 추가/삭제 시 빠름
  • 데이터 검색 시 처음부터 노드를 순회해야하기 때문에 느림

SET

HashSet

add : O(1)
remove : O(1)
next : O(h/n)

  • Thread Safe X
  • 객체들을 순서없이 저장하고, 동일한 객체를 중복 저장하지 않는다.
  • 중복되지 않는 값을 등록할때 용이
  • null을 허용
  • next의 시간복잡도에서 h는 해시 버킷의 사이즈를 의미하고, n은 HashSet에 저장되는 데이터의 사이즈를 의미한다. h/n이라는 값이 나오는 이유는 엘리먼트에 비해 해시 버킷의 수가 늘어나면 해시 버킷으로 사용되는 배열의 대부분은 비게 되고, 엘리먼트가 담겨있는 해시버킷을 찾기 위해 매번 비어있는 해시 버킷을 방문해야 하기 때문에 h가 들어간다.
    또한, 엘리먼트의 숫자가 늘어나면 해시 버킷이 비어있을 가능성이 줄어들게 되고, O(1)에 근접하게 된다. 이런 의미에서 h/n이라는 시간 복잡도가 나온 것으로 보인다.

TreeSet

add : O(log n)
remove : O(log n)
next : O(log n)

  • Thread Safe X
  • 객체 기준으로 정렬을 한다. 느리다.
  • null을 허용하지 않는다.
profile
매일 발전

0개의 댓글