SortedList vs SortedDictionary in C

Both SortedList<TKey, TValue> and SortedDictionary<TKey, TValue> are generic collection classes in C# that maintain elements in sorted order based on their keys. While their public interfaces and functional outcomes appear almost identical, their internal implementations are fundamentally different. SortedList<TKey, TValue> relies on contiguous arrays, whereas SortedDictionary<TKey, TValue> is implemented as a self-balancing binary search tree. These architectural differences create distinct trade-offs in memory consumption, insertion speed, lookup performance, and indexed access.

Underlying Data Structure

• SortedList<TKey, TValue> maintains two internal arrays: one for keys and one for values. The elements are kept sorted by performing a binary search to find the correct index for any operation.
• SortedDictionary<TKey, TValue> uses a Red-Black Tree, which is a self-balancing binary search tree. Each element is stored in an independent tree node that links to its parent and child nodes.

Performance Characteristics

The difference in data structures dictates the time complexity of common operations:

While both collections offer \(O(\log n)\) key retrieval, SortedList<TKey, TValue> is typically faster in practice for lookups because arrays provide better CPU cache locality than node-based trees.

Conversely, inserting or removing elements in a SortedList<TKey, TValue> requires shifting all subsequent elements in the array, making these modifications \(O(n)\). SortedDictionary<TKey, TValue> performs insertions and deletions in \(O(\log n)\) time because it only needs to update node pointers and rebalance the tree.

Memory Overhead

• SortedList<TKey, TValue> has minimal memory overhead. Because it stores data in flat arrays, memory is allocated contiguously without the need for node pointers or object wrapper metadata.
• SortedDictionary<TKey, TValue> has significantly higher memory overhead. Each entry requires a separate node object that stores references to the key, value, left child, right child, parent, and node color. This design also increases pressure on the garbage collector due to frequent allocations and deallocations.

Indexing Capabilities

SortedList<TKey, TValue> exposes indexed access to keys and values through its Keys and Values properties (e.g., myList.Keys[i]). This allows developers to retrieve the \(i\)-th smallest element in \(O(1)\) time.

SortedDictionary<TKey, TValue> does not support efficient indexed access. Accessing an element by index requires iterating through the tree using an enumerator, which takes \(O(n)\) time.

When to Use Each Collection

Use SortedList<TKey, TValue> when:

• The collection is populated once or modified infrequently, but queried often.
• Memory usage is a critical constraint.
• You need fast, direct access to keys and values by numeric index.
• Data is inserted in sequential, sorted order (which eliminates the need to shift array elements).

Use SortedDictionary<TKey, TValue> when:

• The application performs frequent insertions, updates, and deletions of unsorted data.
• Fast insertion speed takes priority over memory efficiency and lookup caching.
• Indexed access to elements is unnecessary.