CODEWITHSUNDEEP
scala
deltanovember
deltanovember

Reputation: 44051

What is the running time for size on Scala's ListBuffer?

Is it constant or O(n)? If O(n) are there similar data structures with constant time size operations?

Upvotes: 4

Views: 889

Answers (1)

Kipton Barros
Kipton Barros

Reputation: 21112

Strangely, size and length have different descriptions in the ListBuffer docs. For sure, ListBuffer.length is constant time. Prior to Scala 2.8, length was indeed O(n), but this is now fixed. The implementation of size in TraversableOnce suggests that it is O(n), but I may be missing something.

Other performance characteristics of Scala collections are documented here. For ListBuffer specifically,

             head     tail     apply   update   prepend  append  insert
 ListBuffer  C        L        L       L        C        C       L

where C is constant and L is linear time.

Edit : Both ListBuffer length and size are now O(1) - The issue mentioned by @KiptonBarros was closed with Scala 2.9.1 see: https://issues.scala-lang.org/browse/SI-4933

Upvotes: 3

Related Questions