Array
- 탐색 및 삽입, 삭제의 시간복잡도 = O(1)
- Arrays.sort()의 시간복잡도 = 평균 O(NlogN) 최악 O(N^2)
ArrayList
- 데이터 공간의 초기 크기는 10이며, 10개 이상의 값이 오는 경우, 데이터 공간이 자동 추가 생된다.
- 데이터 추가시 해당 인덱스를 기준으로 뒤쪽 모든 데이터를 한 칸씩 이동시키고 빈 공간에 추가한다. 때문에 맨 뒤에 추가하는 경우, 시간복잡도는 O(1)
- 시간복잡도
- 탐색의 시간복잡도 = O(1)
- 앞, 중간 삽입의 시간복잡도 = O(N)
- 맨 마지막 삽입의 시간복잡도
- 배열의 크기를 늘려야하는 경우 = O(N)
- 추가만 하는 경우 = O(1)
- 삭제의 시간복잡도 = O(N)
- Collections.sort()의 시간복잡도 = 평균, 최악 O(NlogN)
LinkedList
- 탐색의 시간복잡도 = O(N)
- 삽입 및 삭제의 시간복잡도 = O(1)
이중 연결리스트(클래스를 통해 직접 구현)
- 시간복잡도
- 탐색의 시간복잡도 = O(N)
- 삽입 및 삭제의 시간복잡도 = O(1)
- 자기 자신인 data와 함께, 이전 노드와 다음 노드의 위치를 가르키는 prev, next를 가지고 있다.
- prev = 이전
data = 현재
next = 다음
head = 이중연결리스트의 첫 번째 노드
tail = 이중연결리스트의 마지막 노드
(단일 연결리스트에 비해 이전과 다음 노드를 기억하기에 메모리를 많이 차지하지만, 상황에 따라 탐색 방향이 변한는 경우 사용이 좋다.)
HashMap
- 탐색 및 삽입, 삭제의 시간복잡도 = O(1)
- 순서가 없다.
TreeMap
- 탐색 및 삽입, 삭제의 시간복잡도 = O(logN)
- iterator를 이용하여 순회하게 되면, 자동으로 key 기준 오름차순으로 순회가 된다.
HashSet
- 탐색 및 삽입, 삭제의 시간복잡도 = O(1)
- 순서가 없다.
TreeSet
- 탐색 및 삽입, 삭제의 시간복잡도 = O(logN)
- ceiling, floor, higher, lower, first, last 등을 통해 탐색이 쉽다.
Priority Queue
- 삽입 및 삭제의 시간복잡도 = O(logN)