java.util 패키지에 collection framework 핵심 인터페이스가 들어있다. 다수의 데이터를 쉽게 처리하는 방법을 제공한다.
| interface | 특징 | 구현 클래스 |
| List | 순서가 있는 데이터의 집합. 순서가 있으니까 데이터의 중복을 허락 ex) 일렬로 줄 서기 |
ArrayList LinkedList |
| Set | 순서를 유지하지 않는 데이터의 집합. 순서가 없어서 같은 데이터를 구별할 수 없다. -> 중복 허락하지 않는다. ex) 알파벳이 한 종류씩 있는 주머니 |
HashSet TreeSet |
| Map | key와 value의 쌍으로 데이터를 관리하는 집합. 순서는 없고 key의 중복 불가, value는 중복 가능 ex) 속성 - 값, 지역번호 - 지역 |
HashMap TreeMap |
1. List 인터페이스
순서가 있는 데이터의 집합으로 데이터의 중복을 허용한다.
- ArrayList : 단방향 포인터 구조로 데이터에 대한 인덱스를 가지고 있어서 조회 기능에 성능이 뛰어나다.
- LinkedList : 양방향 포인터 구조로 데이터의 삽입, 삭제가 빈번할 경우 데이터의 위치 정보만 수정하면 되므로 유용하다.
- List의 시간 복잡도
| add() | remove() | get() | contains() | |
| ArrayList | O(1) | O(n) | O(1) | O(n) |
| LinkedList | O(1) | O(1) | O(n) | O(n) |
2. Set 인터페이스
순서를 유지하지 않는 데이터의 집합으로 데이터의 중복을 허용하지 않는다.
- HashSet : 가장 빠른 임의 접근 속도, 순서를 예측할 수 없다.
- TreeSet : 정렬 방법을 지정할 수 있다.
- LinkedHashSet : HashSet과 동일한 구조를 가지지만 삽입된 순서대로 저장된다. 하지만 중복 값은 허용하지 않는다.
- Set의 시간 복잡도
| add() | contain() | next() | |
| HashSet | O(1) | O(1) | O(h / n) |
| TreeSet | O(log n) | O(log n) | O(log n) |
| LinkedHashSet | O(1) | O(1) | O(1) |
3. Map인터페이스
키(key) - 값(value) 쌍으로 이루어졌다. 순서는 유지되지 않으며 키(key)의 중복을 허용하지 않지만 값(value)의 중복은 허용한다.
- HashMap : 중복과 순서가 허용되지 않으며, null 값 가능
- TreeMap : 정렬된 순서대로 키(key) - 값(value)을 저장하고, 검색이 빠르다.
- LinkedHashMap : HashMap과 동일한 구조를 가지지만 삽입된 순서대로 저장된다.
- Map의 시간 복잡도
| add() | containKey() | next() | |
| HashMap | O(1) | O(1) | O(h/n) |
| TreeMap | O(log n) | O(log n) | O(log n) |
| LinkedHashMap | O(1) | O(1) | O(1) |
※ h: 해쉬 버킷 사이즈, n: 데이터 사이즈
댓글