¿Por qué agregar a una Lista en Scala tiene una complejidad de tiempo O (n)?

Acabo de leer que el tiempo de ejecución de la operación append para a List(: +) crece linealmente con el tamaño de List.

Agregar a un Listparece una operación bastante común. ¿Por qué la forma idiomática de hacer esto es anteponer los componentes y luego invertir la lista? Tampoco puede ser un fallo de diseño, ya que la implementación podría modificarse en cualquier momento.

Desde mi punto de vista, tanto antes como anexar deberían ser O (1).

¿Hay alguna razón legítima para esto?

Ampliaré mi comentario un poco. La List[T]estructura de datos, desde scala.collection.immutableestá optimizada para funcionar como funciona una lista inmutable en un lenguaje de programación más puramente funcional. Tiene tiempos de preparación previos muy rápidos , y se supone que estará trabajando en la cabeza para casi todo su acceso.

Las listas inmutables tienen tiempos de preparación previos muy rápidos debido al hecho de que modelan sus listas vinculadas como una serie de "celdas en contra". La celda define un valor único y un puntero a la siguiente celda (estilo clásico de lista individualmente vinculada):

Cell [Value| -> Nil]

Cuando antepone una lista, en realidad solo está creando una nueva celda, con el resto de la lista existente apuntando a:

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

Debido a que la lista es inmutable, puede hacerlo sin ninguna copia real . No hay peligro de que la lista anterior cambie y provoque que todos los valores de su nueva lista se vuelvan inválidos. Sin embargo, pierde la capacidad de tener un puntero mutable al final de su lista como un compromiso.

Esto se presta muy bien para trabajar recursivamente en listas. Digamos que definiste tu propia versión 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)
  }
}

Esa es una función recursiva que funciona exclusivamente desde el principio de la lista y aprovecha la coincidencia de patrones a través del :: extractor. Esto es algo que se ve mucho en idiomas como Haskell.

Si realmente desea adiciones rápidas, Scala proporciona muchas estructuras de datos mutables e inmutables para elegir. En el lado mutable, podría investigar ListBuffer. Alternativamente, Vectordesde scala.collection.immutabletiene un tiempo de adición rápido.