Recursive collections in Scala such as List

Question

The aim is to use a Scala collection where the size needs not be computed iteratively or recursively.

For instance List proves to be a recursive construction (consider for instance https://stackoverflow.com/a/8197826/3189923), and in order to obtain the size it is necessary to iterate over it; namely an O(N) operation on the number of elements in the list.

Thus to ask for which collections this operation is O(1) ? Many Thanks.

Answer 1

The cost of method size for main immutable collections (according to quick view on code):

Seq:
  LinearSeq:
    List - O(N)
    Stream - O(N)*
    Queue - O(N) // Implemented using List
    Stack - O(N)* // Implemented using List, with additional complexity
  IndexedSeq:
    Vector - O(1)
    NumericRange - O(1)
    Array - O(1) // WrappedArray, ArrayOps
    String - O(1) // WrappedString, StringOps
    Range - O(1)
Set:
  HashSet - O(1) // HashSet.HashTrieSet
  TreeSet - O(N) // RedBlackTree.count - recursive with stack usage 
  BitSet - O(Max)* // fast enough. O(1) for collections of small ints
  ListSet - O(N)
Map:
  HashMap - O(1) // HashMap.HashTrieMap
  TreeMap - O(N) // RedBlackTree.count - recursive with stack usage
  ListMap - O(N)

Stream

From documentation:

In order to compute the length of the Stream, it must first be fully realized, which could cause the complete evaluation of an infinite series, assuming that's what your Stream represents.

Stack

Stack#length complexity is much worse than List#length complexity: it creates N new objects to iterate over Stack.

BitSet

BitSet is for collections of small integers.

Complexity of BitSet#size depends on maximal element, not on count of elements. It's about O(Max/64). See also BitSet#size implementation.

TreeSet/TreeMap

I'm not sure about TreeSet and TreeMap complexity, it looks like recursive with stack usage (not tail recursive). See RedBlackTree.count implementation.

Answer 2

• For the immutable collections, Vector has a constant size operation
• The mutable Array has constant a size operation
• For the mutable collections, both ListBuffer and ArrayBuffer have constant size operations.