Collection

Collection Framework이란?

다수의 데이터를 쉽고 효과적으로 처리할 수 있게 표준화된 방법을 제공하는 클래스의 집합

Collection의 종류

List, Set, Map은 인터페이스로 정의되어 있으며 특징에 따라 구분될 수 있음

• List : 순서가 있는 데이터의 집합, 데이터의 중복 허용
• Set : 순서가 없는 데이터의 집합, 데이터의 중복을 허용하지 않음
• Map : 키와 값이 한 쌍으로 이루어지는 데이터의 집합, 키는 중복을 허용하지 않으나, 값은 중복을 허용

LIst, Set은 Collection 인터페이스를 상속받고, Map은 구조적인 차이로 따로 정의되어 있다.

List

• LinkedList : 양방향 포인터 구조로 데이터의 삽입, 삭제가 빈번할 경우insert : O(1) / delete : O(1) / get : O(n) / contains : O(n)
• 데이터의 위치 정보만 변경하면 되기 때문에 유용 > 스택, 큐, 양방향 큐 등을 구현하기 위해 사용
• Stack : 먼저 들어온 데이터가 가장 마지막에 나감.
• insert : O(1) / delete : O(1) / get : O(n)
• ArrayList : 단방향 포인터 구조로 각 데이터에 대한 인덱스를 가지고 있어 탐색 성능이 뛰어남
• insert : O(1) / delete : O(n) / get : O(1) / contains : O(n)
• Vector : 대용량 처리를 위해 사용했던 자료구조로, 동기식이라 성능이 좋지 않아 잘 쓰이지 않음

Queue

• LinkedList : 기본적인 큐를 사용하기 위해 LinkedList로 초기화
• offer : O(1) / peak : O(1) / poll : O(1) / size : O(1)
• PriorityQueue : Heap 구조로 구현하여 우선순위가 높은 순서대로 데이터가 나가는 큐
• offer : O(log n) / peak : O(1) / poll : O(log n) / size : O(1)

Set

• HashSet : 해시 값을 이용해서 저장
• add : O(1) / contains : O(1) / next : O(h/n)
• TreeSet : 이진 트리구조로 값을 정렬하여 저장
• add : O(log n) / contains : O(log n) / next : O(log n)

Map

• Hashtable : 동기화를 지원하여 HashMap보다 느림, 키로 null 값을 허용하지 않음
• HashMap : 중복과 순서를 허용하지 않으며 키로 null 값 허용
• get : O(1) / containsKey : O(1) / next : O(h/n)
• TreeMap : 키를 기준으로 정렬하여 저장하여 검색이 빠름
• get : O(log n) / containsKey : O(log n) / next : O(log n)