Scala：帮助我了解列表性能

Question

List Scaladoc 说：

Time: List has O(1) prepend and head/tail access.

val mainList = List(3, 2, 1)
val with4 =    4 :: mainList  // re-uses mainList, costs one :: instance
val with42 =   42 :: mainList // also re-uses mainList, cost one :: instance
val shorter =  mainList.tail  // costs nothing as it uses the same 2::1::Nil instances as mainList

"costs one :: instance"是什么意思？ （对 O(1) 的引用是为了提供上下文，这不是我要问的。我的问题是关于评论声明）。

Answer 1

我认为 costs one :: instance 是内存消耗的意思。当您执行 4 :: mainList 时，scala 将创建一个新的单个 :: 实例。当您执行 mainList.tail 时，scala 不必创建任何东西。

这很重要，因为对于整个街区

val mainList = List(3, 2, 1)
val with4 =    4 :: mainList  // re-uses mainList, costs one :: instance
val with42 =   42 :: mainList

Scala 仅发布 5 个 :: 个实例，而不是 8 个。

绝对不是性能的问题，因为你不能说mainList.tail在性能上没有成本。