Scala 的 mutable.ListBuffer 似乎使用 List 的 tail 函数，但它被记录为具有线性复杂性？

Question

截至 Scala 的 2.12.8 current documentation , List 的尾部是常数，ListBuffer 的尾部是线性的。然而，看着source code ，看起来 tail 函数没有覆盖，并且在大多数用例中(例如删除 head 元素)，显式调用 List 的 tail 函数。由于 ListBuffer 似乎只是一个带有长度变量和指向最后一个元素的指针的 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

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

1350
1724

我期望线性复杂度来自构建一个全新的列表来返回，但既然内部结构是一个列表，为什么不返回列表的尾部呢？

Answer 1

ListBuffer不延长 List ，以及它不会覆盖 tail 的事实并不意味着它正在使用 List#tail .如果您查看 tail on ListBuffer 文档的定义类部分，你会看到它来自 TraversableLike ，它的定义如下:

override def tail: Repr = {
  if (isEmpty) throw new UnsupportedOperationException("empty.tail")
  drop(1)
}

如果你看看 drop ，您将看到它使用一个构建器来构造一个包含除第一个元素之外的所有元素的新集合，这解释了为什么它是线性的。

正如 talex 在上面的评论中所暗示的， ListBuffer#tail必须返回一个新集合，因为原始缓冲区可能会被修改，并且标准库设计者已经决定您不希望这些修改反射(reflect)在您从 tail 获得的结果中。 .