1. List
- 설명:
순서가 있는 데이터의 모음으로, 중복된 요소를 허용합니다. - 주요 구현 클래스:
ArrayList, LinkedList, Vector - 특징:
- ArrayList: 동적 배열로, 인덱스를 통한 빠른 접근이 가능하지만, 삽입/삭제가 비효율적일 수 있습니다.
- LinkedList: 이중 연결 리스트로, 삽입/삭제가 빠르지만, 인덱스 접근이 느립니다.
- Vector: ArrayList와 유사하지만, 동기화된 버전입니다.(성능 이슈: 대안책으로 ConcurrentHashMap)
- Stack: List 구현체로 포함되어 있지만, Stack이 LIFO(Last In, First Out) 구조를 가지며 Vector를 기반으로 동작합니다.
- 장점:
데이터의 순서가 유지됨
중복된 데이터를 허용 - 단점:
특정 상황에서 성능이 비효율적일 수 있음 (예: ArrayList의 삽입/삭제)
2. Set
- 설명:
중복되지 않는 요소의 모음으로, 순서가 없는 컬렉션입니다. - 주요 구현 클래스:
HashSet, LinkedHashSet, TreeSet - 특징:
- HashSet: 해시 테이블을 사용하여 빠른 검색과 삽입을 지원합니다.
- LinkedHashSet: 입력된 순서를 유지하는 HashSet입니다.
- TreeSet: 정렬된 상태로 데이터를 유지하는 이진 검색 트리 기반의 Set입니다.
- 장점:
중복 요소를 허용하지 않음
TreeSet을 사용하면 자동으로 정렬된 상태 유지 - 단점:
HashSet은 순서를 보장하지 않음
TreeSet은 삽입/삭제/검색이 상대적으로 느림
3. Queue
- 설명:
FIFO(First In, First Out) 원칙에 따라 동작하는 컬렉션입니다. - 주요 구현 클래스:
LinkedList, PriorityQueue, ArrayDeque - 특징:
- LinkedList: 큐의 양쪽에서 삽입/삭제가 가능한 이중 연결 리스트 기반의 큐입니다.
- PriorityQueue: 요소의 우선순위에 따라 처리되는 큐입니다.
- ArrayDeque: 큐의 양쪽에서 삽입/삭제가 가능한 배열 기반의 덱입니다.
- 장점:
다양한 큐 구조를 지원 (예: 우선순위 큐)
큐의 양쪽에서 삽입/삭제가 가능한 구조 지원 - 단점:
PriorityQueue는 동등한 우선순위의 요소가 있을 때 예측하기 어려움
4. Map
- 설명:
키와 값의 쌍으로 이루어진 데이터 구조입니다. 키는 중복될 수 없으며, 값은 중복될 수 있습니다. - 주요 구현 클래스:
HashMap, LinkedHashMap, TreeMap, Hashtable - 특징:
- HashMap: 해시 테이블을 기반으로 하여 키-값 쌍을 빠르게 저장하고 검색할 수 있습니다.
- LinkedHashMap: 입력된 순서를 유지하는 HashMap입니다.
- TreeMap: 키를 정렬된 상태로 유지하는 이진 검색 트리 기반의 맵입니다.
- Hashtable: HashMap과 유사하지만 동기화된 버전입니다.(성능 이슈: 대안책으로 ConcurrentHashMap)
- 장점:
키-값 쌍으로 데이터를 저장하여 빠른 검색 가능
TreeMap을 사용하면 키가 자동으로 정렬됨 - 단점:
HashMap과 Hashtable은 순서를 보장하지 않음
TreeMap은 삽입/삭제/검색이 상대적으로 느림
5. 시간 및 공간복잡도
- 접근 시간 (Access Time)
- ArrayList: 인덱스를 통한 요소 접근은 O(1)의 시간 복잡도를 가지며 매우 빠릅니다. 그러나 리스트의 크기가 매우 커질 경우 메모리 관리 측면에서 성능 저하가 발생할 수 있습니다.
- LinkedList: 인덱스 접근이 O(n)의 시간 복잡도를 가지므로, 리스트의 길이가 길어질수록 접근 시간이 선형적으로 증가합니다.
- 검색 시간 (Search Time)
- HashSet/HashMap: 해시 테이블 기반으로, 일반적으로 O(1)의 검색 시간을 가집니다. 하지만 해시 충돌이 발생할 경우 성능이 저하될 수 있습니다.
- TreeSet/TreeMap: 정렬된 트리 구조로 O(log n)의 검색 시간을 가지며, 대규모 데이터에서 일정한 성능을 유지할 수 있습니다.
- 삽입 및 삭제 시간 (Insertion/Deletion Time)
- ArrayList: 요소 삽입/삭제 시, 특히 리스트 중간에서의 작업은 O(n)의 시간 복잡도를 가지며, 리스트의 크기가 클수록 더 많은 요소를 이동해야 하므로 성능이 저하됩니다.
- LinkedList: 요소 삽입/삭제는 리스트의 양 끝에서 O(1)의 시간 복잡도를 가지지만, 중간에서의 삽입/삭제는 O(n) 시간이 걸릴 수 있습니다.
- TreeSet/TreeMap: 삽입/삭제 시 트리를 재구성해야 하므로 O(log n)의 시간이 걸리며, 크기가 커질수록 성능이 영향을 받을 수 있습니다.
- 공간 복잡도 (Space Complexity)
- 모든 컬렉션 클래스는 O(n)의 공간 복잡도를 가지며, 저장되는 요소의 수에 비례하여 메모리를 사용합니다. 그러나 동적 배열 기반 컬렉션(ArrayList, Vector)은 추가적인 메모리를 할당하여 크기를 조정할 수 있기 때문에 잠재적인 메모리 오버헤드가 발생할 수 있습니다.
| Collection Type | Time Complexity (Access) | Time Complexity (Search) | Time Complexity (Insertion) | Time Complexity (Deletion) | Space Complexity |
|---|---|---|---|---|---|
| ArrayList | O(1) | O(n) | O(1) | O(n) | O(n) |
| LinkedList | O(n) | O(n) | O(1) | O(1) | O(n) |
| Vector | O(1) | O(n) | O(1) | O(n) | O(n) |
| Stack | O(1) | O(n) | O(1) | O(1) | O(n) |
| HashSet | N/A | O(1) | O(1) | O(1) | O(n) |
| LinkedHashSet | N/A | O(1) | O(1) | O(1) | O(n) |
| TreeSet | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| PriorityQueue | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| HashMap | N/A | O(1) | O(1) | O(1) | O(n) |
| LinkedHashMap | N/A | O(1) | O(1) | O(1) | O(n) |
| TreeMap | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
Reference
https://docs.oracle.com/javase/8/docs/technotes/guides/collections/reference.html
안녕하세요. 블로그를 시작하게 되었습니다! 앞으로 유용한 정보와 좋은 내용을 많이 공유할게요:)