list - 将元素添加到 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)？

score 1 · Accepted Answer

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

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

score 1 · Accepted Answer

这是因为元素是前置的： first 2then 1。

根据 cons 方法的定义：

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

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

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

您只需将新元素用作headfor 新列表，将整个先前列表用作其tail.

不可变的前置操作也List需要恒定时间 O(1)，附加是线性 O(n)（来自 Scala文档）。

2 回答 2