小编H4u*_*4uZ的帖子

从scala的2.12.8 当前文档开始,List的尾部是常量,ListBuffer的尾部是线性的.但是,查看源代码,看起来尾部函数没有覆盖,并且在大多数用例中(例如删除head元素),显式调用了List的尾部函数.由于ListBuffer似乎只是一个带有长度var和指向最后一个元素的指针的List包装器,为什么它是线性的？

我对两种方法进行了计时,看起来List的尾部是常量,而ListBuffer的尾部确实是线性的:

import scala.collection.mutable
import scala.collection.immutable

val immutableList: immutable.List[Int] = (1 to 10000).toList
val mutableListBuffer: mutable.ListBuffer[Int] = mutable.ListBuffer.empty[Int] ++= (1 to 10000).toList

// Warm-up
(1 to 100000).foreach(_ => immutableList.tail)
(1 to 100000).foreach(_ => mutableListBuffer.tail)

// Measure
val start = System.nanoTime()
(1 to 1000).foreach(_ => immutableList.tail)
val middle = System.nanoTime()
(1 to 1000).foreach(_ => mutableListBuffer.tail)
val stop = System.nanoTime()

println((middle - start) / 1000)
println((stop - middle) / 1000)

结果如:

1076
86010

但是,如果使用诸如remove(0)之类的函数使用List的尾部,则它是常量,具有以下结果:

1350
1724

我希望线性复杂性来自构建一个全新的列表返回,但由于内部结构是一个List,为什么不返回List的尾部呢？