Sorting generic linked list

Question

I have everything in a Generic Linked list done except for sorting. And I don't know how to use IComparable or how I would go about doing this because it's generic. I don't know what I would even be comparing or sorting?

public class Node<T> : IComparable<T>
{
    private Node<T> next;
    private T item;

}

So

public int CompareTo( T other )
{
    // TODO: Find out how to do it properly
    throw new NotImplementedException();
}

It is also against the instructions to convert it to an array and then sort it, then convert it back.

Answer 1

Having a linked list Node object implement IComparable makes absolutely no sense for the exact reasons you describe. Instead, the classes that you use in the linked list should implement it. In fact, you can require this with a generic type constraint:

MyClass<T> where T : IComparable<T> {}

With that done, you can use T as if it were an IComparable when performing your sort.

Answer 2

The first thing you ought to do is to read up on sort algorithms and decide which one you're going to use. Once you've done that, you can worry about comparing your generic values.

If you want to follow the framework approach, don't require your T to implement IComparable<T>. Instead, use Comparer<T>.Default. This approach allows you to write your class to support user-defined comparisons:

public class LinkedList<T>
{
    public void Sort() { this.Sort(Comparer<T>.Default); }
    public void Sort(IComparer<T> comparer)
    {
        //todo: implement
        throw new NotImplementedException();
    }
}

My initial version of this answer had the comparer as a property of the class, but that's really incorrect, because a linked list is not an inherently sorted type. You might want to sort the list one way once, and then 2 seconds later sort it a different way. The comparer should therefore be a parameter of the sort method.