scala - Scala 的 ListBuffer 大小的运行时间是多少？

Question

它是常数还是 O(n)？如果 O(n) 是否存在具有恒定时间大小操作的类似数据结构？

Answer 1

奇怪的是，size和 length在 ListBuffer docs 中有不同的描述.当然，ListBuffer.length是恒定时间。在 Scala 2.8 之前，length确实是 O(n)，但这是 now fixed . implementation of size 在 TraversableOnce表明它是 O(n)，但我可能遗漏了一些东西。

Scala 集合的其他性能特征是 documented here .对于 ListBuffer具体来说，

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

其中 C 是常数，L 是线性时间。

编辑:ListBuffer 的长度和大小现在都是 O(1) - @KiptonBarros 提到的问题已用 Scala 2.9.1 解决，请参阅: https://issues.scala-lang.org/browse/SI-4933