How do I implement IComparable<T>?

Question

I've created my own generic Java data structure library, now I'm creating it in C#, but I'm stuck trying to implement the CompareTo method to sort a singly linked list. Here's my code:

class SortedSinglyLinkedList<T> : IComparable // my class
// [irrelevant stuff...]
// Sorts the list, from the least to the greatest element
    public void sort()
    {
        for (int i = 0; i < count; i++)
        {
            for (int j = 0; j < count; j++)
            {
                if (get(i).CompareTo(get(j)) < 0) // ERROR -> 'T' does not contain a definition for 'CompareTo' and no extension method 'CompareTo' accepting a first argument of type'T' could be found (are you missing a using directive or an assembly reference?)
                {
                    move(i, j); // this method simply moves a node from i to j
                }
            }
        }
    }

    // Compares 2 elements
    int IComparable<T>.CompareTo(T other)
    {
        // what should I put here to make it work?
    }

Answer 1

One way of achieving this, is to require the elements of your list to be comparable, i.e. have them implement the IComparable interface. You would express this using a generic type constraint on T, as in:

public class SortedSinglyLinkedList<T> : where T : IComparable 

A more general way of doing this, that also allows your list to contain elements that do not implement this IComparable interface, is to follow the strategy used in many of the c# BCL generic collection classes (e.g. SortedDictionary or SortedList): use an IComparer instance to perform the comparisons.

public class SortedSinglyLinkedList<T>
{
    private readonly IComparer<T> _comparer;

    // ...

    public SortedSinglyLinkedList()
    {
        _comparer = Comparer<T>.Default; // use the default.
        // ...
    }

    public SortedSinglyLinkedList(IComparer<T> comparer)
    {
        _comparer = comparer ?? Comparer<T>.Default;
        // ...
    }
}

And in your Sort method, use this comparer instance to perform the comparisons:

_comparer.Compare(get(i), get(j));