Collection 시간 복잡도/ 특징

List

• ArrayList

  • add() : O(1)

  • remove() : O(N)

  • get() : O(1)

  • Contains() : O(N)

  • 특징 : 대량의 데이터 삽입/삭제 시 성능 저하, 검색에는 용이

• LinkedList

  • add() : O(1)

  • remove() : O(1)

  • get() : O(N)

  • Contains() : O(N)

  • 특징 : 데이터 삽입/삭제 빠름, 검색은 느리다.

Queue

• PriorityQueue

  • offer() : O(log N)

  • peek() : O(1)

  • poll() : O(log N)

  • size() : O(1)

  • 특징 : 일반적인 Queue는 FIFO 구조를 갖지만, natural Order에 따라 정렬한다.

• ArrayBlockingQueue

  • offer() : O(1)

  • peek() : O(1)

  • poll() : O(1)

  • size() : O(1)

  • 특징 : FIFO, 고정된 사이즈로 생성 후 변경이 불가능하다.

• ArrayDeque

  • offer() : O(1)

  • peek() : O(1)

  • poll() : O(1)

  • size() : O(1)

  • 특징 : 양쪽에서 element를 삽입/삭제 가능한 확장 가능한 배열

Set

• HashSet

  • add() : O(1)

  • remove() : O(1), 해시 충돌 발생 시 최악의 경우 O(N)

  • contains() : O(1)

  • next() : O(h/n)

  • 특징 : 객체를 순서없이 저장하고 중복을 허용하지 않음, null을 허용한다.

• LinkedHashSet

  • add() : O(1)

  • remove() : O(1)

  • contains() : O(1)

  • next() : O(1)

  • 특징 : 순서대로 저장하지만 HashSet에 비해 느리고 성능은 좋다.

• TreeSet

  • add() : O(log N)

  • remove() : O(log N)

  • contains() : O(log N)

  • next() : O(log N)

  • 특징 : Object 기준으로 정렬, null을 허용하지 않는다.

Map

• HashMap

  • put() : O(1), Collisions 발생 시 O(N)일 경우도 있다.

  • get() : O(1)

  • containsKey : O(1)

• TreeMap

  • put() : O(log N)

  • remove() : O(log N)

  • get() : O(log N)