在Scala中向列表末尾添加一个元素

Question

我无法将类型为T的元素添加到列表List[T]中。 我尝试使用myList ::= myElement，但它似乎创建了一个奇怪的对象，并且访问myList.last总是返回放入列表中的第一个元素。我该如何解决这个问题？

- Masiar

Answer 1

List(1,2,3) :+ 4

Results in List[Int] = List(1, 2, 3, 4)

请注意，此操作的时间复杂度为O(n)。如果您需要频繁执行此操作或者处理长列表，请考虑使用另一种数据类型（例如ListBuffer）。

- Landei

---

在渐进复杂度中，常数因子被忽略，因此没有O(2*n)。我认为这个"List"被转换成了"ListBuffer"，元素被添加，然后再将"ListBuffer"转回来（就像Java中的"String"和"StringBuilder"一样），但这只是一个猜测。 - Landei

它是O(n)的，因为你必须完全遍历列表才能到达最后一个元素指针，并能够附加元素使最后一个元素指针指向它。 - Pikachu

如果是这种情况，可以维护一个指向链表头和尾的指针。然而，Scala中的列表是不可变的，意味着要“修改”列表的最后一个元素，需要首先复制一份。复制过程的时间复杂度是O(n)，而不是遍历链表本身的时间复杂度。 - user289086

我认为它是O(n)，因为它创建了一个全新的列表。 - Raffaele Rossi

cons 运算符的时间复杂度为 O(1)，因为它操作的是列表的“期望”一侧。 - Landei

Answer 2

这是因为你不应该这样做（至少对于一个不可变的列表而言）。 如果你真的非常需要在一个数据结构的末尾添加元素，而且这个数据结构真的需要是一个列表，并且这个列表一定要是不可变的，那么你可以采用以下方法：

(4 :: List(1,2,3).reverse).reverse

或者是这样的：

List(1,2,3) ::: List(4)

- agilesteel

---

非常感谢！那正是我正在寻找的。不过从你的回答中我猜我不应该这样做...我会修改我的结构并看看能做些什么。再次感谢。 - Masiar

如果你想要不可变性和高效的追加操作，建议使用 Vector。请参考 http://www.scala-lang.org/docu/files/collections-api/collections.html 中的“性能特征”部分。 - Arjan Blokzijl

“在列表前面添加元素并翻转整个列表”模式非常适合添加许多元素，但我认为将它应用于向现有列表添加单个元素不是一个好主意。 "双重翻转"技巧需要重建列表两次，而即使效率低下，使用 :+ 只需要重建一次。 - Nicolas Payette

Answer 3

Scala中的列表不是设计用来修改的。实际上，您无法向Scala List 添加元素；它是一个不可变数据结构，就像Java字符串一样。

当您在Scala中“向列表添加元素”时，实际上是从现有列表创建一个新列表。(来源)

建议在这种情况下使用ArrayBuffer或ListBuffer而不是使用列表。这些数据结构被设计为可以添加新元素。

最后，在完成所有操作后，缓冲区可以转换为列表。请参阅以下REPL示例：

scala> import scala.collection.mutable.ListBuffer
import scala.collection.mutable.ListBuffer

scala> var fruits = new ListBuffer[String]()
fruits: scala.collection.mutable.ListBuffer[String] = ListBuffer()

scala> fruits += "Apple"
res0: scala.collection.mutable.ListBuffer[String] = ListBuffer(Apple)

scala> fruits += "Banana"
res1: scala.collection.mutable.ListBuffer[String] = ListBuffer(Apple, Banana)

scala> fruits += "Orange"
res2: scala.collection.mutable.ListBuffer[String] = ListBuffer(Apple, Banana, Orange)

scala> val fruitsList = fruits.toList
fruitsList: List[String] = List(Apple, Banana, Orange)

- Markus Weninger

Answer 4

这与其中一个答案相似，但是方式不同：

scala> val x = List(1,2,3)
x: List[Int] = List(1, 2, 3)

scala> val y = x ::: 4 :: Nil
y: List[Int] = List(1, 2, 3, 4)

- Venkat

Answer 5

我们可以将两个列表或列表和数组进行追加或前置操作。
追加：

var l = List(1,2,3)    
l = l :+ 4 
Result : 1 2 3 4  
var ar = Array(4, 5, 6)    
for(x <- ar)    
{ l = l :+ x }  
  l.foreach(println)

Result:1 2 3 4 5 6

插入：

var l = List[Int]()  
   for(x <- ar)  
    { l= x :: l } //prepending    
     l.foreach(println)   

Result:6 5 4 1 2 3

- Ramesh Muthavarapu

---

是的，我们可以这样做，但出于其他答案提到的所有原因，这将是一个不好的主意。 - jwvh

Answer 6

在Scala中List是不可变的

你可以使用MutableList

var l = scala.collection.mutable.MutableList(1,2,3)
l += 4 

- Matul Jain