[C#][자료구조] SortedList와 SortedDictionary

✅ SortedList & SortedDictionary

📌 SortedList / SortedDictionary란?

SortedList<TKey,TValue>와 SortedDictionary<TKey,TValue>는 키(Key)를 기준으로 자동 정렬되는 컬렉션입니다. 즉, 데이터를 넣을 때마다 키 값의 오름차순으로 정렬된 상태가 유지됩니다.

둘 다 "정렬된 Key-Value 쌍"을 관리하지만, 내부 구조가 달라 성능 특성이 다릅니다.

📌 언제 사용할까?

• Key 기준 정렬된 데이터가 항상 필요할 때
• 범위 검색 (예: 일정 구간의 Key만 조회)
• 정렬된 순서대로 순회해야 할 때

📊 내부 구조와 성능 비교

구분	SortedList<TKey,TValue>	SortedDictionary<TKey,TValue>
내부 구조	배열(Array) 기반	이진 탐색 트리(Red-Black Tree)
삽입/삭제	O(N) (요소 이동 필요)	O(log N)
조회 (인덱스 접근)	O(1)	❌ 지원하지 않음
조회 (Key)	O(log N)	O(log N)
메모리 사용	더 적음	더 많음 (트리 노드 오버헤드)
적합한 경우	조회가 많고 데이터 크기가 작을 때	삽입/삭제가 많고 데이터 크기가 클 때

✅ C#에서의 SortedList

📌 기본 사용법

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var sortedList = new SortedList();

        sortedList.Add(3, "Banana");
        sortedList.Add(1, "Apple");
        sortedList.Add(2, "Cherry");

        foreach (var kvp in sortedList)
            Console.WriteLine($"{kvp.Key} => {kvp.Value}");
        // 출력: 1 => Apple, 2 => Cherry, 3 => Banana

        Console.WriteLine(sortedList[2]); // 인덱스 접근
    }
}

✅ C#에서의 SortedDictionary

📌 기본 사용법

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var sortedDict = new SortedDictionary();

        sortedDict[3] = "Banana";
        sortedDict[1] = "Apple";
        sortedDict[2] = "Cherry";

        foreach (var kvp in sortedDict)
            Console.WriteLine($"{kvp.Key} => {kvp.Value}");
        // 출력: 1 => Apple, 2 => Cherry, 3 => Banana

        Console.WriteLine(sortedDict.ContainsKey(2)); // True
    }
}

📝 정리

• SortedList<TKey,TValue>: 배열 기반, 조회가 빠르지만 삽입/삭제는 느림
• SortedDictionary<TKey,TValue>: 트리 기반, 삽입/삭제가 빠르지만 메모리 소모 많음
• 데이터 크기, 삽입/삭제 빈도, 조회 패턴에 따라 적절히 선택