ความแตกต่างระหว่าง SortedList และ SortedDictionary ใน C#

ความแตกต่างหลัก

คุณสมบัติ	SortedList<TKey, TValue>	SortedDictionary<TKey, TValue>
Implementation	Array-based (2 Arrays: Keys, Values)	Red-Black Tree (BST)
Memory	Compact, Less Overhead	More Overhead (Node Objects)
Insert/Delete (Unsorted)	O(n) - Shift Elements	O(log n) - Tree Rotation
Insert/Delete (Sorted)	O(n) - Binary Search + Shift	O(log n)
Lookup by Key	O(log n) - Binary Search	O(log n) - Tree Traversal
Lookup by Index	O(1) - Direct Array Access	O(n) - ต้อง Iterate
Memory Fragmentation	Low (Contiguous)	Higher (Scattered Nodes)
Iteration Order	Sorted by Key	Sorted by Key
Duplicate Keys	ไม่ได้ (Throw)	ไม่ได้ (Throw)

เมื่อไหร่ควรใช้ SortedList

✅ Data เล็ก-ปานกลาง (< 1000 items)
✅ Insert/Delete นادرة (Mostly Read)
✅ ต้องการ Access by Index (list[index], Keys[index], Values[index])
✅ Memory Critical (Embedded, Mobile)
✅ Pre-loaded Data แล้วแค่ Read

เมื่อไหร่ควรใช้ SortedDictionary

✅ Data ใหญ่ หรือ Frequent Insert/Delete
✅ Real-time Updates (Add/Remove บ่อย)
✅ ไม่ต้องการ Index Access
✅ Thread-Safe Version: ConcurrentDictionary (แต่ไม่ Sorted)

ตัวอย่างโค้ด


using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // SortedList
        var sortedList = new SortedList<int, string>();
        sortedList.Add(3, "Three");
        sortedList.Add(1, "One");
        sortedList.Add(2, "Two");
        
        Console.WriteLine("SortedList (by Index):");
        for (int i = 0; i < sortedList.Count; i++)
        {
            Console.WriteLine($"Index {i}: Key={sortedList.Keys[i]}, Value={sortedList.Values[i]}");
        }
        
        // SortedDictionary
        var sortedDict = new SortedDictionary<int, string>();
        sortedDict.Add(3, "Three");
        sortedDict.Add(1, "One");
        sortedDict.Add(2, "Two");
        
        Console.WriteLine("\nSortedDictionary (no Index Access):");
        foreach (var kvp in sortedDict)
        {
            Console.WriteLine($"Key={kvp.Key}, Value={kvp.Value}");
        }
        
        Console.ReadKey();
    }
}

Output

SortedList (by Index):
Index 0: Key=1, Value=One
Index 1: Key=2, Value=Two
Index 2: Key=3, Value=Three

SortedDictionary (no Index Access):
Key=1, Value=One
Key=2, Value=Two
Key=3, Value=Three

Generic vs Non-Generic

SortedList (Non-Generic) - Legacy, System.Collections
SortedList<TKey, TValue> - Generic, System.Collections.Generic
SortedDictionary<TKey, TValue> - Generic Only

Performance Summary

Operation              | SortedList    | SortedDictionary
-----------------------|---------------|------------------
Add (Random Order)     | O(n)          | O(log n)
Add (Pre-sorted)       | O(n) *        | O(log n)
Remove                 | O(n)          | O(log n)
Index Access           | O(1)          | O(n)
Key Lookup             | O(log n)      | O(log n)
Memory/Item            | ~16 bytes     | ~40+ bytes
Iteration              | Fast (Cache)  | Slower (Pointer)

* SortedList Add แบบ Pre-sorted เร็วกว่า (Append Only) แต่ยัง O(n) ทฤษฎี

Alternative: Immutable Collections


// System.Collections.Immutable (NuGet)
var immutable = ImmutableSortedDictionary.CreateRange(new[] 
{
    new KeyValuePair<int, string>(3, "Three"),
    new KeyValuePair<int, string>(1, "One"),
});
// Thread-Safe, Persistent Data Structure