C#에서 제공하는 다양한 컨테이너는 System.Collections 및 System.Collections.Generic 네임스페이스 하에 있습니다.
주요 컨테이너 클래스 및 내부 자료구조
- List<T>
- 내부 자료구조: 동적 배열(Dynamic Array)
- 시간 복잡도:
- 추가, 삭제(마지막 요소): 평균 O(1)
- 인덱스를 통한 접근: O(1)
- 검색: O(n)
- 삽입, 삭제(임의 위치): O(n)
- LinkedList<T>
- 내부 자료구조: 이중 연결 리스트(Doubly Linked List)
- 시간 복잡도:
- 추가, 삭제: O(1) (노드 참조가 주어지면)
- 검색: O(n)
- 삽입, 삭제(노드 찾은 후): O(n) (노드를 찾는 데 O(n), 작업 자체는 O(1))
- Dictionary<TKey, TValue>
- 내부 자료구조: 해시 테이블(Hash Table)
- 시간 복잡도:
- 추가, 검색, 삭제: 평균 O(1), 최악의 경우 O(n) (해시 충돌이 발생할 경우)
- SortedDictionary<TKey, TValue>
- 내부 자료구조: 레드-블랙 트리(Red-Black Tree)
- 시간 복잡도:
- 추가, 검색, 삭제: O(log n)
- HashSet<T>
- 내부 자료구조: 해시 테이블(Hash Table)
- 시간 복잡도:
- 추가, 검색, 삭제: 평균 O(1), 최악의 경우 O(n) (해시 충돌이 심각할 때)
- SortedSet<T>
- 내부 자료구조: 레드-블랙 트리(Red-Black Tree)
- 시간 복잡도:
- 추가, 검색, 삭제: O(log n)
선택 가이드
- 동적 배열이 필요한 경우: List<T>는 간단한 배열 기반의 리스트로서, 인덱스를 통한 빠른 접근이 필요할 때 유리합니다.
- 빈번한 삽입/삭제가 있는 경우: LinkedList<T>는 중간에 삽입하거나 삭제할 때 배열 기반 구조보다 유리할 수 있습니다.
- 키-값 쌍을 빠르게 접근할 필요가 있는 경우: Dictionary<TKey, TValue>는 해시 기반 접근을 통해 매우 빠른 검색 속도를 제공합니다.
- 자동으로 정렬된 키를 유지해야 하는 경우: SortedDictionary<TKey, TValue> 또는 SortedSet<T>는 데이터를 정렬된 상태로 유지하며, 빠른 검색 및 범위 쿼리를 제공합니다.
