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

Question

从 scala 的 2.12.8 current documentation, List's tail is constant and ListBuffer's tail is linear. However, looking at the source code 开始，tail 函数似乎没有被覆盖，并且在大多数用例中（例如删除 head 元素），List 的 tail 函数被显式调用。由于 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

我预计线性复杂度来自构建一个全新的列表 return，但由于内部结构是一个列表，为什么不 return 列表的尾部？

Answer 1

ListBuffer 不会扩展 List，而且它不会覆盖 tail 的事实并不意味着它正在使用 List#tail。如果您查看 tail on ListBuffer 文档的 Definition 类 部分，您会发现它来自 TraversableLike，它的定义如下这个：

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

如果您查看 drop，您会发现它使用构建器构建一个包含除第一个元素以外的所有元素的新集合，这解释了为什么它是线性的。

正如 talex 在上面的评论中暗示的那样，ListBuffer#tail 必须 return 一个新集合，因为原始缓冲区可能会被修改，而标准库设计者已决定您不希望这些修改反映在您从 tail.

获得的结果中

Answer 2

since the internal structure is a List

如果看the source，内部结构其实是两个列表：

private var start: List[A] = Nil
private var last0: ::[A] = _

last0 具有此类型，因为它使用内部 API ~~进行了变异（并且必须使 ListBuffer 有意义）~~（实际上，只有前后部分的两个列表以相反的顺序排列，应该可以非常有效地支持所有 ListBuffer 操作，包括（分摊）O(1) tail；大概是当前的实现赢得常数因素，或者我可能错过了一些它做得更好的操作）。

所以 tail 不能只是 "return the List's tail"：它至少必须复制 last0 因为你不能在两个缓冲区之间共享相同的可变部分。即使设计者希望对 tail 进行更改以反映对原始 ListBuffer 的更改，反之亦然，共享 last0 也不会产生这种效果（没有更多的努力）。这已经是线性的。

注意如果ListBuffer#tail的return类型是List你还需要复制last0，或者把last0的内容复制到start 在 return 尾巴之前，等等。所以它不会 tail constant-time。但它确实会产生其他问题：ArrayBuffer#tail return Array 吗？如果 tail 的 return 类型在 GenTraversableLike 中仍然可用，你如何声明它？

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

Scala's mutable.ListBuffer seems to use List's tail function yet it is documented as having linear complexity?

scala

scala-collections