1. List< T >

주로 사용되는 상황

• 동적 크기 조정이 필요할 때: 고정 크기의 배열과 달리 List< T >는 자동으로 크기가 조정되므로 요소를 추가하거나 삭제할 때 용량을 신경 쓸 필요가 없습니다.
• 순차적인 데이터 액세스: 데이터를 순서대로 접근하거나 처리해야 할 때 List< T >가 유용합니다.
• 임의 접근이 필요한 경우: List< T >는 인덱스를 통한 빠른 접근을 지원하여 배열과 유사한 성능을 제공합니다.

장점

• 동적으로 크기 조정: 자동으로 메모리를 재할당하고 요소의 배열을 복사하여 리스트의 용량을 관리합니다.
• 인덱스를 통한 빠른 접근: O(1)의 시간 복잡도로 특정 인덱스의 요소에 접근할 수 있습니다.
• 범용성: 다양한 유형의 데이터에 사용할 수 있으며, 여러 종류의 데이터 처리 작업에 적합합니다.

단점

• 메모리 사용량: 요소가 배열에 저장되기 때문에 크기 조정 시 기존 데이터의 복사가 필요하며, 이는 추가적인 메모리 사용을 초래할 수 있습니다.
• 요소 삽입 및 삭제 비용: 시작이나 중간에 요소를 삽입하거나 삭제할 때, 배열의 요소를 이동해야 하므로 비용이 많이 들 수 있습니다(O(N) 시간 복잡도).

기본적인 메서드

• Add(T item): 리스트의 끝에 요소를 추가합니다.
• Remove(T item): 특정 요소를 제거합니다.
• IndexOf(T item): 특정 요소의 인덱스를 반환합니다.
• Clear(): 리스트의 모든 요소를 제거합니다.
• Count: 리스트에 저장된 요소의 수를 가져옵니다.
• Capacity: 리스트가 저장할 수 있는 요소의 최대 수를 가져오거나 설정합니다.

유용한 메서드

• Find(Predicate< T > match): 조건에 맞는 첫 번째 요소를 찾습니다.
• FindAll(Predicate< T > match): 조건에 맞는 모든 요소를 찾아 새 리스트로 반환합니다.
• Exists(Predicate< T > match): 조건에 맞는 요소가 존재하는지 확인합니다.
• Sort(): 리스트의 요소를 기본 비교자를 사용하여 정렬합니다.
• ForEach(Action< T > action): 리스트의 각 요소에 대해 지정된 작업을 실행합니다.

내부 자료구조

List< T >는 내부적으로 배열을 사용하여 요소를 저장합니다. 초기 용량을 초과하는 요소가 추가되면, 자동으로 크기가 두 배로 증가하는 새 배열에 기존 요소들을 복사합니다.

시간 복잡도

• 인덱스를 통한 접근 (get/set): O(1)
• Add(T item): 평균적으로 O(1), 내부 배열의 확장이 필요할 때는 O(N)
• Insert(int index, T item): O(N) (삽입 위치부터 모든 요소를 이동해야 함)
• Remove(T item), RemoveAt(int index): O(N) (요소를 제거하고 뒤의 요소들을 앞으로 이동해야 함)

2. Dictionary<TKey, TValue>

주로 사용되는 상황

• 고유 식별자를 사용한 데이터 접근: 각 요소에 고유한 키가 할당되어 있을 때, 이 키를 사용하여 빠르게 데이터에 접근할 수 있습니다.
• 데이터 색인: 대량의 데이터를 관리하고, 특정 키를 사용해 빠르게 검색할 필요가 있는 경우에 적합합니다.
• 캐시 구현: 계산 결과나 재사용 가능한 데이터를 저장하는 데 사용하여, 성능을 최적화할 수 있습니다.
• 룩업 테이블: 다양한 값과 설정을 빠르게 조회할 필요가 있을 때 사용됩니다.

장점

• 효율적인 데이터 접근: 평균적으로 O(1) 시간 복잡도로 데이터에 접근할 수 있어 매우 빠릅니다.
• 키-값 쌍 구조: 데이터를 키와 연결된 값으로 관리하므로 의미 있는 관계를 표현하기 쉽습니다.
• 확장성: 요소 수가 많아져도 성능 저하가 적습니다.

단점

• 메모리 사용량: 해시 테이블 구현으로 인해 배열 기반 구조보다 상대적으로 높은 메모리 사용량을 가질 수 있습니다.
• 해시 충돌: 잘못된 해시 함수 설계는 해시 충돌을 빈번하게 발생시켜 성능 저하를 초래할 수 있습니다.

기본적인 메서드

• Add(TKey key, TValue value): 새 키-값 쌍을 딕셔너리에 추가합니다.
• Remove(TKey key): 특정 키를 가진 요소를 딕셔너리에서 제거합니다.
• TryGetValue(TKey key, out TValue value): 주어진 키에 대한 값을 찾고, 찾은 경우 true를 반환합니다.
• Clear(): 딕셔너리의 모든 요소를 제거합니다.
• ContainsKey(TKey key): 특정 키가 딕셔너리에 있는지 확인합니다.

유용한 메서드

• Keys: 딕셔너리의 모든 키를 포함하는 컬렉션을 반환합니다.
• Values: 딕셔너리의 모든 값을 포함하는 컬렉션을 반환합니다.
• Count: 딕셔너리에 있는 키-값 쌍의 수를 반환합니다.

내부 자료구조

Dictionary<TKey, TValue>는 내부적으로 해시 테이블을 사용합니다. 키에 해시 함수를 적용하여 해시 코드를 생성하고, 이 해시 코드를 사용하여 데이터가 저장될 배열의 인덱스를 결정합니다.

시간 복잡도

• 추가, 삭제, 검색: 이상적인 조건 하에서 평균 O(1) 시간 복잡도를 제공합니다. 최악의 경우(모든 키가 같은 버킷에 매핑되는 경우)에는 O(n)이 될 수 있습니다.

3. SortedDictionary<TKey, TValue>

주로 사용되는 상황

• 정렬된 데이터의 관리: 데이터를 자동으로 정렬된 상태로 유지하고 싶을 때 사용합니다.
• 키 기반 검색과 범위 검색: 범위 기반의 검색을 효과적으로 수행할 수 있어야 할 때 유용합니다.
• 데이터 정렬의 유지: 데이터를 추가하거나 제거해도 정렬 상태를 유지해야 할 때 적합합니다.

장점

• 자동 정렬: 키에 의해 자동으로 정렬되며, 이는 데이터의 삽입, 삭제, 검색 시 항상 정렬 상태를 유지합니다.
• 효율적인 범위 검색: 정렬된 키를 기반으로 효율적인 범위 검색을 지원합니다.
• 예측 가능한 반복 성능: 키의 정렬 순서대로 데이터를 반복할 수 있어, 데이터의 순회가 예측 가능합니다.

단점

• 성능 저하 가능성: 일반적인 Dictionary<TKey, TValue>에 비해 삽입, 삭제, 검색 작업에서 시간 복잡도가 더 높아질 수 있습니다.
• 메모리 사용량: 내부적으로 더 복잡한 자료구조를 사용하기 때문에, 메모리 사용량이 더 클 수 있습니다.

기본적인 메서드

• Add(TKey key, TValue value): 새로운 키-값 쌍을 추가합니다.
• Remove(TKey key): 특정 키를 가진 요소를 제거합니다.
• ContainsKey(TKey key): 특정 키가 존재하는지 확인합니다.
• TryGetValue(TKey key, out TValue value): 키에 해당하는 값을 찾고, 있으면 true와 함께 값을 반환합니다.
• Clear(): 모든 키-값 쌍을 제거합니다.

유용한 메서드

• Keys: 딕셔너리의 모든 키를 포함하는 컬렉션을 반환합니다. 이 컬렉션은 정렬된 상태입니다.
• Values: 딕셔너리의 모든 값을 포함하는 컬렉션을 반환합니다. 값은 키의 정렬 순서에 따라 정렬됩니다.
• Count: 딕셔너리에 있는 키-값 쌍의 수를 반환합니다.

내부 자료구조

SortedDictionary<TKey, TValue>는 내부적으로 레드-블랙 트리(Red-Black Tree)라는 유형의 균형 이진 검색 트리를 사용합니다. 이 트리 구조는 데이터의 추가, 삭제, 검색 시 균형을 잘 유지하여 로그 시간 복잡도를 제공합니다.

시간 복잡도

• 추가, 삭제, 검색: 이 모든 연산은 평균적으로 O(log n)의 시간 복잡도를 가집니다.

4. SortedList<TKey, TValue>

주로 사용되는 상황

• 메모리 효율성이 중요한 경우: SortedList<TKey, TValue>는 데이터 양이 적고, 메모리 사용 최적화가 필요할 때 적합합니다.
• 키에 의한 정렬이 필요한 경우: 자동으로 정렬을 유지해야 하며, 삽입 순서가 아닌 키의 순서에 따라 데이터에 접근해야 할 때 사용됩니다.
• 빈번한 조회와 일부 범위 검색: 키로 빠르게 접근할 수 있고, 범위 검색을 수행해야 할 때 유리합니다.

장점

• 자동 정렬: 키에 따라 자동으로 정렬되며, 정렬된 데이터에 빠르게 접근할 수 있습니다.
• 메모리 효율성: 내부적으로 배열을 사용하기 때문에, SortedDictionary<TKey, TValue>와 비교했을 때 메모리 사용이 더 효율적일 수 있습니다.

단점

• 삽입 및 삭제 비용: 중간에 요소를 삽입하거나 삭제할 때, 배열의 요소를 이동해야 하므로 O(N)의 시간이 소요됩니다.
• 데이터 크기 증가 시 성능 저하: 큰 데이터 세트를 관리할 때는 SortedDictionary<TKey, TValue>에 비해 성능이 떨어질 수 있습니다.

기본적인 메서드

• Add(TKey key, TValue value): 새 키-값 쌍을 추가합니다.
• Remove(TKey key): 특정 키를 가진 요소를 제거합니다.
• ContainsKey(TKey key): 특정 키가 존재하는지 확인합니다.
• IndexOfKey(TKey key): 특정 키의 인덱스를 반환합니다.
• Clear(): 모든 키-값 쌍을 제거합니다.

유용한 메서드

• Keys: 컬렉션의 모든 키를 포함하는 컬렉션을 반환합니다.
• Values: 컬렉션의 모든 값을 포함하는 컬렉션을 반환합니다.
• TryGetValue(TKey key, out TValue value): 키에 해당하는 값을 찾고, 있으면 true와 함께 값을 반환합니다.

내부 자료구조

SortedList<TKey, TValue>는 두 개의 배열을 사용합니다: 하나는 키를 저장하고 다른 하나는 해당 키에 연결된 값을 저장합니다. 이 구조는 키와 값이 별도의 배열에서 인덱스로 연결되어 있습니다.

시간 복잡도

• 추가, 삭제: 이러한 연산들은 배열을 재정렬해야 하기 때문에 O(N)의 시간 복잡도를 가집니다.
• 검색: 키 배열이 항상 정렬된 상태이므로, 이진 검색을 사용하여 O(log N)의 시간 복잡도로 검색할 수 있습니다.

5. HashSet< T >

주로 사용되는 상황

• 중복 제거: 데이터에서 중복을 허용하지 않아야 할 때 사용됩니다.
• 빠른 멤버십 검증: 요소가 집합에 존재하는지 빠르게 확인해야 할 때 유용합니다.
• 대규모 데이터의 빠른 처리: 많은 데이터 요소들을 빠르게 처리하고, 중복을 쉽게 제거할 수 있습니다.

장점

• 빠른 성능: 요소의 추가, 삭제, 검색 등의 연산이 평균적으로 O(1) 시간 복잡도로 매우 빠릅니다.
• 자동 중복 제거: 요소를 추가할 때 자동으로 중복을 검사하고 제거합니다.

단점

• 메모리 사용: 내부적으로 해시 테이블을 사용하기 때문에, 비교적 높은 메모리 사용량이 발생할 수 있습니다.
• 요소 정렬 부재: HashSet< T >는 요소를 어떠한 순서로도 저장하지 않으므로, 정렬된 데이터를 필요로 하는 경우에는 적합하지 않습니다.

기본적인 메서드

• Add(T item): 집합에 요소를 추가합니다. 이미 요소가 존재하는 경우에는 추가하지 않습니다.
• Remove(T item): 집합에서 특정 요소를 제거합니다.
• Contains(T item): 특정 요소가 집합에 있는지 확인합니다.
• Clear(): 집합에서 모든 요소를 제거합니다.

유용한 메서드

• UnionWith(IEnumerable< T > other): 다른 컬렉션의 요소를 현재 집합에 추가하여 합집합을 형성합니다.
• IntersectWith(IEnumerable< T > other): 현재 집합과 다른 컬렉션의 공통 요소만을 남기고 나머지 요소는 제거합니다 (교집합).
• ExceptWith(IEnumerable< T > other): 현재 집합에서 다른 컬렉션의 요소를 제거합니다 (차집합).
• IsSubsetOf(IEnumerable< T > other): 현재 집합이 다른 컬렉션의 부분집합인지 확인합니다.
• IsSupersetOf(IEnumerable< T > other): 현재 집합이 다른 컬렉션의 상위집합인지 확인합니다.
• Overlaps(IEnumerable< T > other): 현재 집합과 다른 컬렉션이 최소 하나의 공통 요소를 가지고 있는지 확인합니다.

내부 자료구조

HashSet< T >는 내부적으로 해시 테이블을 사용하여 요소를 저장합니다. 해시 함수를 통해 각 요소의 해시 코드를 계산하고, 이를 기반으로 데이터를 저장하고 검색합니다.

시간 복잡도

• 추가, 삭제, 검색: 모든 기본 연산들은 평균적으로 O(1) 시간 복잡도를 가집니다. 최악의 경우(해시 충돌이 심할 때) 이러한 연산들은 O(n)까지 걸릴 수 있습니다.

6. SortedSet< T >

주로 사용되는 상황

• 정렬된 데이터의 관리: 데이터를 정렬된 상태로 유지해야 할 때 사용됩니다.
• 데이터의 유일성 보장: 중복된 요소를 자동으로 제거해야 하는 경우에 적합합니다.
• 범위 쿼리: 특정 범위 내의 데이터를 효과적으로 쿼리해야 할 때 유용합니다.

장점

• 자동 정렬: 요소를 추가할 때 자동으로 정렬되며, 정렬된 순서로 요소를 순회할 수 있습니다.
• 데이터 유일성: 집합이기 때문에 중복된 요소를 허용하지 않습니다.
• 효율적인 데이터 접근: 이진 검색 트리를 사용하기 때문에 대부분의 연산이 로그 시간 복잡도로 수행됩니다.

단점

• 메모리 사용량: 내부적으로 트리 구조를 사용하기 때문에, 동일한 데이터를 배열이나 리스트로 관리하는 것보다 더 많은 메모리를 사용할 수 있습니다.
• 삽입 및 삭제 비용: 요소의 추가와 제거가 배열이나 리스트에 비해 비교적 느릴 수 있습니다, 특히 트리의 균형을 유지하기 위한 추가 연산이 필요합니다.

기본적인 메서드

• Add(T item): 집합에 요소를 추가합니다. 이미 존재하는 요소는 추가되지 않습니다.
• Remove(T item): 집합에서 특정 요소를 제거합니다.
• Contains(T item): 특정 요소가 집합에 있는지 확인합니다.
• Clear(): 집합에서 모든 요소를 제거합니다.

유용한 메서드

• Min: 집합에서 최소 요소를 반환합니다.
• Max: 집합에서 최대 요소를 반환합니다.
• GetViewBetween(T lowerValue, T upperValue): 지정된 범위 내의 요소를 포함하는 새로운 SortedSet< T > 뷰를 반환합니다.
• UnionWith(IEnumerable< T > other): 다른 컬렉션의 요소를 현재 집합에 추가하여 합집합을 형성합니다.
• IntersectWith(IEnumerable< T > other): 현재 집합과 다른 컬렉션의 공통 요소만을 남기고 나머지 요소는 제거합니다 (교집합).
• ExceptWith(IEnumerable< T > other): 현재 집합에서 다른 컬렉션의 요소를 제거합니다 (차집합).

내부 자료구조

SortedSet< T >는 내부적으로 레드-블랙 트리를 사용하여 요소를 관리합니다. 이는 자가 균형 이진 검색 트리의 한 형태로, 데이터의 추가, 삭제, 검색 작업이 로그 시간 복잡도로 수행됩니다.

시간 복잡도

• 추가, 삭제, 검색: 이러한 기본 연산들은 O(log n)의 시간 복잡도를 가집니다.