C# SortedList

Introduction

The SortedList is a powerful collection type in C# that automatically maintains its elements in a sorted order. It combines features of both arrays and hash tables, storing key-value pairs that are sorted by the keys. This makes it especially useful when you need a collection that maintains its order while allowing fast lookups.

In this tutorial, we'll explore the SortedList collection in depth, learning how to create, manipulate, and use it effectively in your C# applications.

What is a SortedList?

A SortedList in C# is a collection that:

• Stores key-value pairs (similar to a dictionary)
• Automatically keeps the pairs sorted by keys
• Allows fast lookups by key (similar to a dictionary)
• Allows access by index (similar to an array)
• Does not allow duplicate keys

Think of it as a combination of a dictionary and an array, with the added benefit of automatic sorting.

Creating a SortedList

Let's start by creating a simple SortedList:

csharp

// Create a new SortedList
SortedList<string, int> studentScores = new SortedList<string, int>();

// Add key-value pairs
studentScores.Add("Alice", 95);
studentScores.Add("Charlie", 85);
studentScores.Add("Bob", 90);
studentScores.Add("David", 80);

// Display all the student scores
Console.WriteLine("Student scores (automatically sorted by name):");
foreach (var student in studentScores)
{
    Console.WriteLine($"{student.Key}: {student.Value}");
}

Output:

Student scores (automatically sorted by name):
Alice: 95
Bob: 90
Charlie: 85
David: 80

Notice how even though we added "Charlie" before "Bob", the SortedList automatically sorted the entries alphabetically by the key (student name).

Basic Operations with SortedList

1. Adding Elements

csharp

SortedList<int, string> rankedPlayers = new SortedList<int, string>();

// Add items using the Add method
rankedPlayers.Add(3, "Charlie");
rankedPlayers.Add(1, "Alice");
rankedPlayers.Add(2, "Bob");

// Alternative way to add or update items
rankedPlayers[4] = "David";  // Add a new item
rankedPlayers[1] = "Alicia"; // Update an existing item

// Display the players by rank
foreach (var player in rankedPlayers)
{
    Console.WriteLine($"Rank {player.Key}: {player.Value}");
}

Output:

Rank 1: Alicia
Rank 2: Bob
Rank 3: Charlie
Rank 4: David

2. Accessing Elements

You can access elements in a SortedList either by key or by index:

csharp

SortedList<string, string> capitals = new SortedList<string, string>
{
    { "France", "Paris" },
    { "Japan", "Tokyo" },
    { "Italy", "Rome" },
    { "Canada", "Ottawa" }
};

// Access by key
Console.WriteLine($"The capital of Japan is {capitals["Japan"]}");

// Access by index
Console.WriteLine($"The second country in the list is {capitals.Keys[1]} with capital {capitals.Values[1]}");

// Check if a key exists before accessing
if (capitals.ContainsKey("Germany"))
{
    Console.WriteLine($"The capital of Germany is {capitals["Germany"]}");
}
else
{
    Console.WriteLine("Information about Germany is not available");
}

Output:

The capital of Japan is Tokyo
The second country in the list is France with capital Paris
Information about Germany is not available

3. Removing Elements

csharp

SortedList<string, decimal> productPrices = new SortedList<string, decimal>
{
    { "Laptop", 999.99m },
    { "Mouse", 25.50m },
    { "Keyboard", 45.75m },
    { "Monitor", 249.99m }
};

// Remove an item by key
productPrices.Remove("Mouse");

// Clear all items
// productPrices.Clear();

Console.WriteLine("Products after removing Mouse:");
foreach (var product in productPrices)
{
    Console.WriteLine($"{product.Key}: ${product.Value}");
}

Output:

Products after removing Mouse:
Keyboard: $45.75
Laptop: $999.99
Monitor: $249.99

Common Properties and Methods

The SortedList<TKey, TValue> class provides several useful properties and methods:

Properties

• Count: Gets the number of key-value pairs in the SortedList.
• Keys: Gets the collection of keys in the SortedList.
• Values: Gets the collection of values in the SortedList.
• Capacity: Gets or sets the capacity of the SortedList.

Methods

• Add(TKey, TValue): Adds an element with the specified key and value.
• Remove(TKey): Removes the element with the specified key.
• ContainsKey(TKey): Determines whether the SortedList contains the specified key.
• ContainsValue(TValue): Determines whether the SortedList contains the specified value.
• GetKey(int): Gets the key at the specified index.
• GetKeyList(): Gets a read-only list of the keys in the SortedList.
• GetValueList(): Gets a read-only list of the values in the SortedList.
• IndexOfKey(TKey): Searches for the specified key and returns its index.
• IndexOfValue(TValue): Searches for the specified value and returns the index of its first occurrence.
• TryGetValue(TKey, out TValue): Gets the value associated with the specified key.

Custom Key Sorting

By default, SortedList uses the default comparer for the key type. However, you can provide a custom comparer to control how keys are sorted:

csharp

// Custom comparer for descending order
class DescendingComparer<T> : IComparer<T> where T : IComparable<T>
{
    public int Compare(T x, T y)
    {
        // Reverse the comparison for descending order
        return y.CompareTo(x);
    }
}

// Using the custom comparer
SortedList<int, string> descendingScores = new SortedList<int, string>(new DescendingComparer<int>());
descendingScores.Add(85, "Charlie");
descendingScores.Add(95, "Alice");
descendingScores.Add(90, "Bob");
descendingScores.Add(80, "David");

Console.WriteLine("\nScores in descending order:");
foreach (var score in descendingScores)
{
    Console.WriteLine($"{score.Key}: {score.Value}");
}

Output:

Scores in descending order:
95: Alice
90: Bob
85: Charlie
80: David

Practical Examples

Example 1: Student Grade Tracker

csharp

using System;
using System.Collections.Generic;

public class GradeTracker
{
    private SortedList<string, List<int>> studentGrades = new SortedList<string, List<int>>();
    
    public void AddGrade(string student, int grade)
    {
        if (!studentGrades.ContainsKey(student))
        {
            studentGrades[student] = new List<int>();
        }
        
        studentGrades[student].Add(grade);
    }
    
    public double GetAverageGrade(string student)
    {
        if (!studentGrades.ContainsKey(student))
        {
            throw new ArgumentException($"No grades found for student: {student}");
        }
        
        List<int> grades = studentGrades[student];
        int sum = 0;
        foreach (int grade in grades)
        {
            sum += grade;
        }
        
        return (double)sum / grades.Count;
    }
    
    public void DisplayAllStudentAverages()
    {
        Console.WriteLine("Student Grade Averages (Alphabetical Order):");
        foreach (var student in studentGrades)
        {
            double average = GetAverageGrade(student.Key);
            Console.WriteLine($"{student.Key}: {average:F1}");
        }
    }
}

// Usage example
public static void Main()
{
    GradeTracker tracker = new GradeTracker();
    
    tracker.AddGrade("John", 85);
    tracker.AddGrade("John", 90);
    tracker.AddGrade("John", 88);
    
    tracker.AddGrade("Alice", 92);
    tracker.AddGrade("Alice", 95);
    tracker.AddGrade("Alice", 90);
    
    tracker.AddGrade("Bob", 78);
    tracker.AddGrade("Bob", 82);
    tracker.AddGrade("Bob", 85);
    
    tracker.DisplayAllStudentAverages();
}

Output:

Student Grade Averages (Alphabetical Order):
Alice: 92.3
Bob: 81.7
John: 87.7

Example 2: Word Frequency Counter

csharp

using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;

public class WordFrequencyCounter
{
    public static SortedList<string, int> CountWordFrequency(string text)
    {
        SortedList<string, int> wordFrequency = new SortedList<string, int>();
        
        // Remove punctuation and convert to lowercase
        string cleanText = Regex.Replace(text.ToLower(), @"[^\w\s]", "");
        
        // Split the text into words
        string[] words = cleanText.Split(new[] { ' ', '\t', '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries);
        
        // Count frequency of each word
        foreach (string word in words)
        {
            if (wordFrequency.ContainsKey(word))
            {
                wordFrequency[word]++;
            }
            else
            {
                wordFrequency[word] = 1;
            }
        }
        
        return wordFrequency;
    }
}

// Usage example
public static void Main()
{
    string text = "This is a sample text. This text is used to demonstrate the word frequency counter. The counter counts each word in the text.";
    
    SortedList<string, int> frequency = WordFrequencyCounter.CountWordFrequency(text);
    
    Console.WriteLine("Word Frequencies (Alphabetically):");
    foreach (var word in frequency)
    {
        Console.WriteLine($"{word.Key}: {word.Value}");
    }
}

Output:

Word Frequencies (Alphabetically):
a: 1
counter: 2
counts: 1
demonstrate: 1
each: 1
frequency: 1
in: 1
is: 2
sample: 1
text: 3
the: 3
this: 2
to: 1
used: 1
word: 2

Performance Considerations

When deciding whether to use a SortedList in your application, consider the following performance characteristics:

1. Insertion: O(n) - Less efficient than Dictionary since elements need to be kept sorted
2. Lookup by key: O(log n) - Binary search is used for fast lookups
3. Lookup by index: O(1) - Direct indexing is very fast
4. Memory usage: More efficient than SortedDictionary when the collection is mostly stable (not many insertions/deletions)

Use a SortedList when:

• You need a sorted collection of key-value pairs
• You often access elements by index
• The collection is relatively stable (not many insertions and deletions)
• Memory efficiency is important

SortedList vs. SortedDictionary

Both SortedList and SortedDictionary store sorted key-value pairs, but they have important differences:

Feature	SortedList	SortedDictionary
Implementation	Array of key-value pairs	Binary search tree
Memory usage	Lower	Higher
Insertion performance	Slower (O(n))	Faster (O(log n))
Retrieval by key	O(log n)	O(log n)
Retrieval by index	O(1)	Not supported
Best used when	Collection is stable, memory is a concern	Frequent insertions and removals

Summary

The SortedList collection in C# provides a powerful way to store key-value pairs in a sorted manner. It combines the benefits of arrays and dictionaries, offering both indexed access and key-based lookups. It's particularly useful when you need to maintain items in a specific order while still having fast access to values by their keys.

Key points to remember:

• SortedList automatically keeps items sorted by key
• It doesn't allow duplicate keys
• It's more memory-efficient than SortedDictionary
• It offers both dictionary-like and array-like access
• It's best for relatively stable collections where you don't insert/remove items frequently

Exercises

1. Create a program that uses a SortedList to maintain a list of countries and their populations, sorted by country name.

2. Implement a simple contact book using a SortedList where names are keys and phone numbers are values.

3. Extend the word frequency counter example to display the words sorted by frequency (highest to lowest) instead of alphabetically. Hint: You'll need to create a new SortedList with frequencies as keys.

4. Create a program that reads a CSV file containing student names and scores, stores them in a SortedList, and allows users to query information about specific students or display all students sorted by name.

5. Implement a simple inventory management system using a SortedList where product IDs are keys and product details (as a custom class) are values.

Additional Resources

• Microsoft Documentation on SortedList<TKey,TValue>
• C# SortedList vs SortedDictionary Performance Comparison
• .NET Collections and Data Structures

Happy coding with C# SortedList collections!