Ajout d'un élément à la fin d'une liste dans Scala

223

Cela ressemble à une question stupide, mais tout ce que j'ai trouvé sur Internet était une poubelle. Je ne peux tout simplement pas ajouter un élément de type Tdans une liste List[T]. J'ai essayé avec myList ::= myElementmais il semble que cela crée un objet étrange et y accéder myList.lastrenvoie toujours le premier élément qui a été mis dans la liste.

Masiar
la source

Réponses:

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

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

Notez que cette opération a une complexité de O (n). Si vous avez besoin de cette opération fréquemment ou pour de longues listes, envisagez d'utiliser un autre type de données (par exemple, un ListBuffer).

Landei
la source
7
Il n'y a pas d'O (2 * n), les facteurs constants sont ignorés pour les complexités asymptotiques. Je pense que le Listest converti en un ListBuffer, l'élément est ajouté et le ListBufferconverti en arrière (à peu près comme Stringet StringBuilderen Java), mais ce n'est qu'une supposition.
Landei
2
Il s'agit de O (n) car vous devez parcourir entièrement la liste pour atteindre le dernier pointeur d'élément et pouvoir y ajouter l'élément en faisant pointer le dernier pointeur d'élément.
pisaruk
39
@pisaruk si tel était le cas, on pourrait simplement maintenir un pointeur vers la tête et la queue. Cependant, la liste dans scala est immuable, ce qui signifie que pour "modifier" le dernier élément de la liste, il faut d'abord en faire une copie. C'est la copie qui est O (n) - pas la traversée de la liste elle-même.
2
Je crois que c'est O (n) simplement parce que crée une toute nouvelle liste
Raffaele Rossi
3
L'opérateur contre a la complexité O (1), car il fonctionne du côté "prévu" de la liste.
Landei
67

C'est parce que vous ne devriez pas le faire (au moins avec une liste immuable). Si vous avez vraiment besoin d'ajouter un élément à la fin d'une structure de données et que cette structure de données doit vraiment être une liste et que cette liste doit vraiment être immuable, alors faites ceci:

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

ou ça:

List(1,2,3) ::: List(4)
agilesteel
la source
Merci beaucoup! C'est exactement ce que je cherchais. Je suppose que d'après votre réponse, je ne devrais pas faire cela cependant ... Je vais réviser ma structure et voir ce que je peux faire. Merci encore.
Masiar
6
@Masiar utilise un vecteur si vous voulez une immuabilité et un ajout efficace. Voir la section des caractéristiques de performance dans scala-lang.org/docu/files/collections-api/collections.html
Arjan Blokzijl
29
Le "construire la liste en ajoutant et en inversant" est un modèle utile si vous avez de nombreux éléments à ajouter, mais je ne pense pas que ce soit une bonne idée de l'appliquer comme vous le faites dans le cas de l'ajout d'un seul élément à un liste existante. L'astuce «double reverse» reconstruit la liste deux fois, tandis que :+, aussi inefficace qu'elle soit, elle ne la reconstruit qu'une seule fois.
Nicolas Payette
25

Les listes de Scala ne sont pas conçues pour être modifiées. En fait, vous ne pouvez pas ajouter d'éléments à un Scala List; c'est une structure de données immuable , comme une chaîne Java. Ce que vous faites réellement lorsque vous "ajoutez un élément à une liste" dans Scala, c'est de créer une nouvelle liste à partir d'une liste existante . (La source)

Au lieu d'utiliser des listes pour de tels cas d'utilisation, je suggère d'utiliser soit un, ArrayBuffersoit un ListBuffer. Ces infrastructures de données sont conçues pour ajouter de nouveaux éléments.

Enfin, une fois toutes vos opérations terminées, le tampon peut alors être converti en liste. Voir l'exemple REPL suivant:

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
la source
3

Ceci est similaire à l'une des réponses mais de manière différente:

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
la source
2

Nous pouvons ajouter ou pré-ajouter deux listes ou list & array
Append:

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

Prepending:

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

Result:6 5 4 1 2 3
Ramesh Muthavarapu
la source
1
Oui, nous le pouvons, mais ce serait une mauvaise idée pour toutes les raisons mentionnées dans les autres réponses.
jwvh