Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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; } }
}
share|improve this question

2 Answers 2

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.

share|improve this answer
    
I will add that the insertion isn't as efficient as it could, the insertion point can be found using a binary search as well. –  Carl 7 hours ago
1  
True, but binary search is again efficient only when using an array list which in turn would make insertion inefficient again :-) –  Simon Fischer 7 hours ago
    
You can traverse the list in a binary fashion, which will reduce the amount of comparisons. –  Carl 7 hours ago
    
And as far as not using an array list: codeproject.com/Articles/340797/… –  Carl 7 hours ago
1  
@Carl: How would you perform a binary search on a linked list without introducing extra pointers? –  ChrisWue 6 hours ago

If I'm looking at it right, you could simplify the Add method by dropping the first if condition, like this:

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);
    }
}
share|improve this answer
    
Well this is right! I fixed a bug before in the algorithm and didn't realise this oportunity to simplify the code –  TopinFrassi 4 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.