none
ObservableCollection Performance

    Question

  • What underlying data structure does ObservableCollection<T> use?  I think it is a Collection<T>, and according to MSDN:
    Add: O(1)
    Insert: O(n)
    RemoveAt: O(n)
    Item (indexer): O(1)

    As far as I know, the above is impossible - The only data structure that has O(1) add, and is dynamically resizable, is a linked list.  But a linked list does not have O(1) lookup.  This looks to me like a List<T> underlying, but that the incorrectly documented the Add.  List<T> add says it is O(1) if count<Capacity, else it is N.

    Does anyone have any more details?
    • Edited by Moby Disk Friday, June 12, 2009 4:24 PM forgot word in the title
    Friday, June 12, 2009 4:22 PM

Answers

  • It derives from Collection<> which uses List<> to store the items.  Whose underlying data structure is an array whose size is List<>.Capacity.  Which is O(1) for add if the array isn't filled yet, O(n) when the array size needs to be doubled to make more room for another item.  The "almost always O(1), sometimes O(n)" behavior makes it amortized O(1).

    Hans Passant.
    • Marked as answer by Moby Disk Friday, June 12, 2009 4:43 PM
    Friday, June 12, 2009 4:36 PM
  • ObservableCollection<T> inherits from Collection<T>. Collection<T> uses an internal List<T> to carry it's values.  The Add method of Collection<T> calls the Insert method of the internal List<T>, which is an O(n) operation, so it does seem that the documentation may be incorrect. 


    David Morton - http://blog.davemorton.net/ - @davidmmorton
    • Marked as answer by Moby Disk Friday, June 12, 2009 4:43 PM
    Friday, June 12, 2009 4:33 PM

All replies

  • ObservableCollection<T> inherits from Collection<T>. Collection<T> uses an internal List<T> to carry it's values.  The Add method of Collection<T> calls the Insert method of the internal List<T>, which is an O(n) operation, so it does seem that the documentation may be incorrect. 


    David Morton - http://blog.davemorton.net/ - @davidmmorton
    • Marked as answer by Moby Disk Friday, June 12, 2009 4:43 PM
    Friday, June 12, 2009 4:33 PM
  • It derives from Collection<> which uses List<> to store the items.  Whose underlying data structure is an array whose size is List<>.Capacity.  Which is O(1) for add if the array isn't filled yet, O(n) when the array size needs to be doubled to make more room for another item.  The "almost always O(1), sometimes O(n)" behavior makes it amortized O(1).

    Hans Passant.
    • Marked as answer by Moby Disk Friday, June 12, 2009 4:43 PM
    Friday, June 12, 2009 4:36 PM
  • It derives from Collection<> which uses List<> to store the items.  Whose underlying data structure is an array whose size is List<>.Capacity.  Which is O(1) for add if the array isn't filled yet, O(n) when the array size needs to be doubled to make more room for another item.  The "almost always O(1), sometimes O(n)" behavior makes it amortized O(1).

    Hans Passant.


    But Hans, the Add method of Collection<T> calls the list's Insert method, not it's Add method.

    The Add method:

    public void Add(T item)
    {
        if (this.items.IsReadOnly)
        {
            ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ReadOnlyCollection);
        }
        int count = this.items.Count;
        this.InsertItem(count, item);
    }

    The InsertItem method:

    protected virtual void InsertItem(int index, T item)
    {
        this.items.Insert(index, item);
    }


    David Morton - http://blog.davemorton.net/ - @davidmmorton - ForumsBrowser, a WPF Forums Client
    Friday, June 12, 2009 4:43 PM
  • List<>.Insert is O(1) if the insertion point is at the end of the list.

    Hans Passant.
    Friday, June 12, 2009 5:26 PM
  • I wish they did some optimization to allow O(1) Insert up until the point that items need to actually be read. Then, they could batch all the inserts into a single O(N) internal bulk insert. Same for Remove().

    I also wish they exposed a BinarySearch<T>(Comparison<T>) type of searcher, as an alternative for IndexOf(...) when you know your collection is already sorted.

    It might be worth trying that yourself by deriving or wrapping ObservableCollection<T> (I'm actually going to try that soon).

    Saturday, March 05, 2011 5:10 AM