11
\$\begingroup\$

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; } }
}
\$\endgroup\$
12
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Carl Sep 25 '14 at 19:34
  • 4
    \$\begingroup\$ True, but binary search is again efficient only when using an array list which in turn would make insertion inefficient again :-) \$\endgroup\$ – Simon Fischer Sep 25 '14 at 19:38
  • 1
    \$\begingroup\$ You can traverse the list in a binary fashion, which will reduce the amount of comparisons. \$\endgroup\$ – Carl Sep 25 '14 at 19:56
  • \$\begingroup\$ And as far as not using an array list: codeproject.com/Articles/340797/… \$\endgroup\$ – Carl Sep 25 '14 at 19:57
  • 2
    \$\begingroup\$ @Carl: How would you perform a binary search on a linked list without introducing extra pointers? \$\endgroup\$ – ChrisWue Sep 25 '14 at 20:40
4
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Well this is right! I fixed a bug before in the algorithm and didn't realise this oportunity to simplify the code \$\endgroup\$ – IEatBagels Sep 25 '14 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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