Pourquoi l'ajout à une liste dans Scala a-t-il une complexité temporelle O (n)?

Je viens de lire que le temps d'exécution de l'opération d'ajout pour un List(: +) croît linéairement avec la taille du List.

L'ajout à un Listsemble être une opération assez courante. Pourquoi la manière idiomatique de procéder consiste-t-elle à ajouter les composants et à inverser la liste? Cela ne peut pas non plus être un échec de conception car l'implémentation peut être modifiée à tout moment.

De mon point de vue, le préfixe et l'ajout doivent être O (1).

Y a-t-il une raison légitime à cela?

Je vais développer un peu mon commentaire. La List[T]structure des données scala.collection.immutableest optimisée pour fonctionner comme une liste immuable dans un langage de programmation plus purement fonctionnel. Il a des temps de préparation très rapides et il est supposé que vous travaillerez sur la tête pour presque tout votre accès.

Les listes immuables ont des temps de préparation très rapides car elles modélisent leurs listes liées comme une série de "contre-cellules". La cellule définit une valeur unique et un pointeur sur la cellule suivante (style classique de liste à liaison unique):

Cell [Value| -> Nil]

Lorsque vous ajoutez à une liste, vous créez vraiment une seule nouvelle cellule, le reste de la liste existante étant pointé vers:

Cell [NewValue| -> [Cell[Value| -> Nil]]

Parce que la liste est immuable, vous pouvez le faire sans aucune copie réelle . Il n'y a aucun danger que l'ancienne liste change et que toutes les valeurs de votre nouvelle liste deviennent invalides. Cependant, vous perdez la possibilité d'avoir un pointeur modifiable à la fin de votre liste comme compromis.

Cela se prête très bien à un travail récursif sur des listes. Disons que vous avez défini votre propre version de filter:

def deleteIf[T](list : List[T])(f : T => Boolean): List[T] = list match {
  case Nil => Nil
  case (x::xs) => f(x) match {
    case true => deleteIf(xs)(f)
    case false => x :: deleteIf(xs)(f)
  }
}

C'est une fonction récursive qui fonctionne exclusivement depuis le début de la liste, et tire parti de la correspondance de motifs via l'extracteur ::. C'est quelque chose que vous voyez beaucoup dans des langues comme Haskell.

Si vous voulez vraiment des ajouts rapides, Scala propose de nombreuses structures de données mutables et immuables. Du côté mutable, vous pourriez vous pencher sur ListBuffer. Alternativement, à Vectorpartir de scala.collection.immutablea un temps d'ajout rapide.