Anhängen eines Elements an das Ende einer Liste in Scala

223

Es klingt wie eine dumme Frage, aber alles, was ich im Internet gefunden habe, war Müll. Ich kann einfach kein typisches Element Tzu einer Liste hinzufügen List[T]. Ich habe es mit versucht, myList ::= myElementaber es scheint, dass es ein seltsames Objekt erstellt und beim Zugriff auf myList.lastimmer das erste Element zurückgegeben wird, das in die Liste aufgenommen wurde.

Masiar
quelle

Antworten:

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

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

Beachten Sie, dass diese Operation eine Komplexität von O (n) hat. Wenn Sie diesen Vorgang häufig oder für lange Listen benötigen, sollten Sie einen anderen Datentyp verwenden (z. B. einen ListBuffer).

Landei
quelle
7
Es gibt kein O (2 * n), konstante Faktoren werden für asymptotische Komplexitäten ignoriert. Ich denke , die Listzu einem umgewandelt wird ListBuffer, wird das Element angefügt, und das ListBufferkonvertierte zurück ( so ziemlich wie Stringund StringBuilderin Java), aber das ist nur eine Vermutung.
Landei
2
Es ist O (n), weil Sie die Liste vollständig durchlaufen müssen, um den letzten Elementzeiger zu erreichen und das Element anhängen zu können, sodass der letzte Elementzeiger darauf zeigt.
Pisaruk
39
@pisaruk wenn das der Fall wäre, könnte man einfach einen Zeiger auf den Kopf und den Schwanz halten. Die Liste in Scala ist jedoch unveränderlich, was bedeutet, dass man zuerst eine Kopie davon erstellen muss, um das letzte Element der Liste zu "modifizieren". Es ist die Kopie, die O (n) ist - nicht das Durchlaufen der Liste selbst.
2
Ich glaube, es ist O (n), einfach weil eine brandneue Liste erstellt wird
Raffaele Rossi
3
Der Nachteile-Operator hat die Komplexität O (1), da er auf der "beabsichtigten" Seite der Liste arbeitet.
Landei
67

Das liegt daran, dass Sie es nicht tun sollten (zumindest mit einer unveränderlichen Liste). Wenn Sie wirklich wirklich ein Element an das Ende einer Datenstruktur anhängen müssen und diese Datenstruktur wirklich wirklich eine Liste sein muss und diese Liste wirklich wirklich unveränderlich sein muss, dann tun Sie Folgendes:

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

oder das:

List(1,2,3) ::: List(4)
agilesteel
quelle
Vielen Dank! Genau das habe ich gesucht. Ich denke aus Ihrer Antwort sollte ich das aber nicht tun ... Ich werde meine Struktur überarbeiten und sehen, was ich tun kann. Danke noch einmal.
Masiar
6
@Masiar Verwenden Sie einen Vektor, wenn Sie Unveränderlichkeit und effizientes Anhängen wünschen. Siehe den Abschnitt Leistungsmerkmale in scala-lang.org/docu/files/collections-api/collections.html
Arjan Blokzijl
29
Das "Erstellen der Liste durch Voranstellen und anschließendes Umkehren" ist ein nützliches Muster, wenn Sie viele Elemente hinzufügen müssen, aber ich denke nicht, dass es eine gute Idee ist, es so anzuwenden, wie Sie es tun, wenn Sie einem Element ein einzelnes Element hinzufügen vorhandene Liste. Der Trick "Double Reverse" erstellt die Liste zweimal neu, während sie :+, so ineffizient sie auch sein mag, nur einmal neu erstellt wird.
Nicolas Payette
25

Listen in Scala können nicht geändert werden. Tatsächlich können Sie einer Scala keine Elemente hinzufügen List. Es ist eine unveränderliche Datenstruktur wie ein Java-String. Was Sie tatsächlich tun, wenn Sie in Scala "ein Element zu einer Liste hinzufügen", ist, eine neue Liste aus einer vorhandenen Liste zu erstellen . (Quelle)

Anstatt Listen für solche Anwendungsfälle zu verwenden, schlage ich vor, entweder a ArrayBufferoder a zu verwenden ListBuffer. Diese Datenstrukturen sollen neue Elemente hinzufügen.

Nachdem alle Vorgänge ausgeführt wurden, kann der Puffer schließlich in eine Liste konvertiert werden. Siehe folgendes REPL-Beispiel:

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
quelle
3

Dies ähnelt einer der Antworten, ist jedoch unterschiedlich:

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
quelle
2

Wir können zwei Listen oder List & Array anhängen oder voranstellen. Anhängen
:

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

Vorab:

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

Result:6 5 4 1 2 3
Ramesh Muthavarapu
quelle
1
Ja, wir können, aber es wäre aus all den in den anderen Antworten genannten Gründen eine schlechte Idee.
Jwvh