C#에서 SortedList와 SortedDictionary는 모두 키-값 쌍을 정렬된 상태로 유지하며 데이터를 저장하는 대표적인 컬렉션입니다. 이름과 용도가 비슷해 혼동하기 쉽지만, 내부 구조와 메모리 사용 방식, 성능 특성에서 뚜렷한 차이를 보입니다.
아래 표에서 두 컬렉션의 핵심적인 차이점을 확인해 보세요.
SortedList와 SortedDictionary의 주요 차이점
| 번호 | 구분 항목 | SortedList | SortedDictionary |
|---|---|---|---|
| 1 | 메모리 사용량 | 내부적으로 배열을 사용하므로 메모리 사용량이 적고 오버헤드가 낮습니다. | 각 요소를 별도의 노드 객체로 관리하므로 상대적으로 더 많은 메모리를 소비합니다. |
| 2 | 내부 설계 | 요소들이 메모리상의 연속된 블록(배열)에 저장됩니다. | 이진 탐색 트리 기반으로, 노드들이 힙 전체에 흩어져 저장됩니다. |
| 3 | 메모리 단편화 | 연속된 배열 구조 덕분에 메모리가 압축적으로 유지되어 단편화 부담이 적습니다. | 개별 노드가 힙 곳곳에 할당되므로 장기적으로 단편화가 발생하기 쉽습니다. |
| 4 | 요소 접근 방식 | 인덱스와 키 모두로 접근할 수 있어, 원하는 인덱스를 지정해 해당 위치의 값을 바로 가져올 수 있습니다. | 키를 통해서만 접근할 수 있으며, 인덱스 기반 접근은 지원하지 않습니다. |
| 5 | 데이터 정렬 | 이름 그대로 요소가 항상 키 기준으로 정렬된 상태로 저장되며, 배열 재배치를 통해 정렬 순서를 유지합니다. | 마찬가지로 키 기준 정렬 순서를 유지하지만, 트리 구조 자체가 정렬 상태를 관리하는 방식입니다. |
성능 측면의 차이
삽입 및 삭제
SortedList는 중간에 요소를 삽입하거나 삭제할 때 기존 요소들을 밀어내거나 당겨야 하므로 최악의 경우 O(n)의 시간이 소요됩니다. 반면 SortedDictionary는 균형 트리(레드-블랙 트리) 구조 덕분에 삽입과 삭제가 항상 O(log n)으로 안정적으로 처리됩니다.
조회 속도
키를 이용한 조회는 두 컬렉션 모두 O(log n)으로 비슷한 성능을 보입니다. 다만 SortedList는 인덱스 기반 접근을 추가로 지원하므로, 위치를 알고 있는 경우 더 빠르게 값을 읽을 수 있다는 장점이 있습니다.
어떤 상황에서 무엇을 선택해야 할까?
데이터를 한 번 채워 넣은 후 조회 위주로 사용하는 경우라면 메모리 효율이 좋은 SortedList가 적합합니다. 반면, 실행 중 잦은 삽입과 삭제가 발생하는 동적인 환경이라면 성능이 안정적인 SortedDictionary가 더 나은 선택입니다. 프로젝트의 데이터 변경 빈도와 메모리 제약 조건을 고려해 적절한 컬렉션을 선택하는 것이 중요합니다.