将元素添加到 Scala 中的不可变列表

Question

在 Scala 中，将元素添加到不可变列表的方式如下：

    val l = 1 :: 2 :: Nil
    l: List[Int] = List(1, 2)

这意味着您首先创建一个 Nil（空）列表，然后向其添加 2，然后添加 1。即这些操作是右关联的。因此，实际上，它可以以更清晰的方式重写，如下所示：

    val l = (1 :: (2 :: Nil))
    l: List[Int] = List(1, 2)

问题来了，如果List要保留插入顺序，空列表先加2再加1，为什么答案不是l: List[Int] = List(2, 1)？？

Answer 1

这只是惯例。列表基本上是堆栈。访问或修改最近添加的项目是最有效的。您也可以按顺序将列表的头部视为最后一项，在这种情况下，您建议的符号将是合适的。

我推测这种约定的原因是我们通常不太关心列表的构造方式，但我们通常希望将访问的第一个项目视为排序中的初始项目，所以符号反映了这一点。

Answer 2

这是因为元素是前置的：首先是 2 然后是 1。

来自 cons 方法的定义：

  def ::[B >: A] (x: B): List[B] =
    new scala.collection.immutable.::(x, this)

在这里您可以看到每次创建案例 class scala.collection.immutable.:: 的新实例时：

case class ::[B](val head: B, var tail: List[B]) extends List[B]

您只需将新元素用作新列表的 head，并将之前的整个列表用作其 tail。

另外，不可变 List 的前置操作需要常数时间 O(1)，追加是线性 O(n)（来自 Scala docs）。

Adding elements to an immutable list in Scala