Coffeehouse Post

Single Post Permalink

View Thread: Immutable collections for .NET arrive
  • User profile image
    Sven Groot

    @evildictaitor: Your implementation means that both Count and getting an item are no longer O(1), and that the items are not stored in contiguous memory (which is what is usually expected from a List<T>).

    In the worst case, with a list constructed by adding items one by one, these operations now have a worst case complexity of O(n).

    EDIT: It sounds like the immutable collections actually have a lookup time of O(log n), and don't use contiguous storage anyway.