Recientemente comencé a aprender Scala, y me encontré con el:: (Cons) función, que precede a una lista.
En el libro "Programación en Scala", se indica que no hay una función de anexar porque al anexar a una lista tiene un rendimiento o (n) mientras que al anteponer tiene un rendimiento de o (1)

Algo me parece que está mal con esa afirmación.

¿El rendimiento no depende de la implementación? ¿No es posible simplemente implementar la lista con los enlaces hacia adelante y hacia atrás y almacenar el primer y último elemento en el contenedor?

Supongo que la segunda pregunta es qué debo hacer cuando tengo una lista, digamos 1,2,3 y quiero agregar 4 al final.