Always sorted list

Question

In this list, each newly inserted element is put in its place in order using IComparer<T>. The implementation uses a LinkedList<T> for the increased performance of insertion. Are there any problems with this object?

public class SortedCollection<T> : ICollection<T>
{
    private readonly LinkedList<T> _sortedList;
    private readonly IComparer<T> _comparer;

    public SortedCollection(IComparer<T> comparer)
    {
       if (comparer == null) throw new ArgumentNullException("comparer");

       _comparer = comparer;
       _sortedList = new LinkedList<T>();
    }

    public SortedCollection()
       : this(Comparer<T>.Default)
    { }

    public void Add(T item)
    {
       LinkedListNode<T> node = _sortedList.First;
       if (node == null || _comparer.Compare(node.Value, item) > 0)
       {
          _sortedList.AddFirst(item);
       }
       else
       {
          while (node != null && _comparer.Compare(node.Value, item) < 1)
          {
             node = node.Next;
          }

          if (node == null)
          {
             _sortedList.AddLast(item);
          }
          else
          {
             _sortedList.AddBefore(node, item);
          }
       }
    }

    public bool Remove(T item)
    {
       return _sortedList.Remove(item);
    }

    public IEnumerator<T> GetEnumerator()
    {
       return _sortedList.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
       return _sortedList.GetEnumerator();
    }

    public void Clear()
    {
       _sortedList.Clear();
    }

    public bool Contains(T item)
    {
       return _sortedList.Contains(item);
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
       _sortedList.CopyTo(array, arrayIndex);
    }

    public int Count
    {
       get { return _sortedList.Count; }
    }

    public bool IsReadOnly { get { return false; } }
}

Answer 1

Though insertion itself is efficient, finding the right index is not with this implementation. You are still doing a linear search. For insertion, a sorted tree is more efficient, and that, too, could be iterated over in sort order. I don't know why you chose a list in the first place, but typically the reason for that is accessing elements by index. That is not possible efficiently with a tree, but with a linked list it's not either.

To cut a long story short, you need to know what operations need to be fast to pick the right data structure, but a tree seems more appropriate than your linked list approach when it comes to insertion which is what you mentioned in your question.

Answer 2

You can simplify the Add method by dropping the first if condition, that is:

public void Add(T item)
{
    LinkedListNode<T> node = _sortedList.First;
    while (node != null && _comparer.Compare(node.Value, item) < 1)
    {
        node = node.Next;
    }
    if (node == null)
    {
        _sortedList.AddLast(item);
    }
    else
    {
        _sortedList.AddBefore(node, item);
    }
}