Eu comecei recentemente a aprender scala, e eu me deparei com o:: (cons) função, que prepends para uma lista.
No livro "Programação em Scala", afirma que não há nenhuma função de anexação porque anexar a uma lista tem desempenho o (n) ao passo que prepending tem uma performance de o (1)

Algo me parece errado sobre essa declaração.

O desempenho não depende da implementação? Não é possível simplesmente implementar a lista com links para frente e para trás e armazenar o primeiro e o último elemento no contêiner?

A segunda pergunta que eu suponho é o que devo fazer quando tenho uma lista, digamos 1,2,3 e quero adicionar 4 ao final dela?