SortedList in C#

A SortedList in C# is a collection of key-value pairs that must be sorted at any given point in time based on its keys. This data structure guarantees that whenever we add or remove elements from any point in the list, the order of the list will remain the same. In this article, we will discuss how to create and use this data structure in our C# applications.

Let’s start.

What Is a SortedList in C#?

As we stated in our introduction, a sorted list is made up of key-value pairs that must always be sorted based on its keys. In C#, we get this using the SortedList class. Essentially, this class behaves just like a regular List<T>, but has two primary differences;

• It gets sorted once we add or remove elements to or from it
• It stores a list of KeyValuePair<TKey, TValue> instead of a single type T

In fact, we can argue that the SortedList is a hybrid between a Dictionary<TKey, TValue> and a List<T>. This has some operational advantages, as well as disadvantages.

Let’s compare adding new elements into a List object, to adding elements into a SortedList:

 

When we add a new element to a List, our list class will simply append the element to the end of the collection in the order in which we added them. For the SortedList however, our class will always sort the contents of the list to decide the appropriate position to insert our new element.

How to Create a SortedList in C#

There are two versions of this class available in C#; the generic and non-generic versions. They differ in how we create them, and some nuances in how we access them.

Generic SortedList

The generic SortedList is available under the System.Collections.Generic namespace. As with all generics, when creating a new object, we have to define the types of the key and value that is, TKey and TValue respectively.

Let’s create a generic SortedList that takes int keys and string values:

var myList = new SortedList<int,string>();

This gives us a strongly typed collection, which means that every pair of elements we add to it must be of int key type and string value type. This structure is so similar to a Dictionary that we can even initialize a new sorted list by feeding a dictionary into its constructor:

var myDictionary = new Dictionary<int, string> { {1, "first things first"}, { 2, "second things second" } };
var myListFromDictionary = new SortedList<int, string>(myDictionary);

The initialized list will simply sort itself using the keys, and retain the contents of the supplied dictionary. There are four other constructor overloads available when creating a SortedList.

Let’s describe all the available overloads:

SortedList<TKey,TValue>(IComparer<TKey>)

SortedList<TKey,TValue>(IDictionary<TKey,TValue>, IComparer<TKey>)

SortedList<TKey,TValue>(Int32)

SortedList<TKey,TValue>(Int32, IComparer<TKey>)

In whichever overload we use, we can add elements to our list, and expect the list to expand to accommodate the new addition. However, we can’t add values of any other types to the keys or values. In fact, attempting to do this will give us a syntax error.

Now, let’s add some elements to our first generic SortedList:

myList.Add(1, "This is my first string element");
myList.Add(2, "This is my second string element");

myList.Add("three", "This is my third string element"); // CS1503: Argument 1: cannot convert from 'string' to 'int'
myList.Add(null, "There is nothing to see here"); // CS1503: Argument 1: cannot convert from '<null>' to 'int'
myList.Add(5, 5); // CS1503: Argument 2: cannot convert from 'int' to 'string'

The last three lines of our code will give us syntax errors because we are trying to insert the wrong types either as a key, or a value. The situation is quite different for a non-generic SortedList.

Non-Generic SortedList

The non-generic SortedList is available under the System.Collections namespace. Here, we don’t have to declare the types that we will be adding to our collection. Instead, C# uses variable boxing to implicitly determine the acceptable key type once we add our first element to the collection. The value is always boxed and treated as an object.

Let’s create a non-generic SortedList:

var myNonGenericList = new SortedList();

Once we create an empty SortedList, we can use the Add() method to insert new elements into the list. Unlike the generic SortedList, since the key and value types are evaluated at runtime, we do not get any syntax errors even when we try to add unwanted types to our collection. We will however get runtime exceptions.

Let’s add the same elements from our generic collection, into this non-generic one:

myNonGenericList.Add(1, "This is my first string element");
myNonGenericList.Add(2, "This is my second string element");

myNonGenericList.Add("three", "This is my third string element"); // System.ArgumentException: ...
myNonGenericList.Add(null, "There is nothing to see here"); // System.ArgumentNullException: ...

// This line does not give us any errors!
myNonGenericList.Add(5, 5);

Did you notice that the myNonGenericList.Add(5, 5) line did not return any errors? Since the value is a basic object type, our program does not need to control what kind of values we input into our collection. We will have to take responsibility for handling the different types when accessing the SortedList within our code.

How to Access a SortedList in C#

There are many methods and properties through which we can access a SortedList. First, let’s look at the properties of our SortedList:

 

The Capacity property gives us the maximum number of elements that our SortedList can contain at any moment. The Count gives us the number of elements currently within our collection. The Keys property gives us a list of all the Keys currently within the collection, while the Values property gives us a list of the Values. Under the hood, the SortedList actually makes use of two parallel lists for storing keys and values. The IComparer<T> which provides the logic for sorting our collection is also exposed using the Comparer property.

There are many methods that we can use to access the SortedList in C#. We have already demonstrated the Add() method which adds a new element into the collection with the specified key and value. Once we have elements in the collection, we want to be able to perform actions on the collection. To check if a key is part of a collection, we can use the ContainsKey(TKey) method. The IndexOfKey(TKey) method will give us the zero-based index of our key if it exists in the list.

Let’s modify myList to add in the 3 and 4 key-value pairs:

if(!myList.ContainsKey(3))
{
    myList.Add(3, "This is my third value");
}

if(!myList.ContainsValue("This is my fourth value"))
{
    myList.Add(4, "This is my fourth value");
}

For the fourth item, instead of using ContainsKey(TKey), we use ContainsValue(TValue).

When we have the values but not the keys, we can perform the reverse search by using ContainsValue(TValue) and IndexOfValue(TValue) respectively.

How to Remove Elements From a SortedList

While working with our list, we may want to remove some elements from it. Using the RemoveAt(Int32) method, we can remove a single element at a zero-based index. If we have the key for this element, we could instead remove it using the Remove(TKey) function:

myList.RemoveAt(3) // removes (2, "") which is the item at position 3
myList.Remove(4) // removes (4, "")

myList.Clear() // removes all the elements and returns an empty collection

We should remember that in adding or removing elements from a SortedList, it must complete a sort operation to make sure the right order is in place.

When to Use SortedLists

While SortedList can be a powerful tool for performing quick manipulation of paired data in an orderly manner, there are certain cases where this class may not be suitable.

By its nature, a SortedList must always be sorted. Therefore, whenever we add a new element to the list or remove an element from it, it must sort itself to ensure that all elements are in the right order. This becomes more expensive as we increase the number of elements in our list.

We should only use SortedList when we want to handle smaller collections that need to be sorted at all times. When dealing with larger collections, it is more efficient to use a dictionary, HashSet, or even a regular list which we can then sort once at the point where we need it.

Conclusion

The SortedList is a very useful and memory-efficient way to store sorted data. It gives us the flexibility of being able to index data, and also select data using keys. Once we have a mastery of the SortedList object, we can apply it in so many parts of our daily programming syntax.