关键是 x :: somelist 不会改变 somelist ，而是会创建一个新列表，其中包含x后跟所有元素 somelist 。这可以在O（1）时间完成，因为您只需要将 somelist 设置为 x 新创建的单链表。

如果使用双向链接列表， x 也必须被设置为 somelist 的头，它会修改 somelist 。因此，如果我们希望能够在O（1）中执行 :: 而不修改原始列表，那么我们只能使用单个链表。

关于第二个问题：您可以使用 ::: 将单个元素列表连接到列表的末尾。这是一个O（n）操作。

 列表（1,2,3）:::列表（4）
 

I've recently started learning scala, and I've come across the :: (cons) function, which prepends to a list.
In the book "Programming in Scala" it states that there is no append function because appending to a list has performance o(n) whereas prepending has a performance of o(1)

Something just strikes me as wrong about that statement.

Isn't performance dependent on implementation? Isn't it possible to simply implement the list with both forward and backward links and store the first and last element in the container?

The second question I suppose is what I'm supposed to do when I have a list, say 1,2,3 and I want to add 4 to the end of it?

The key is that x :: somelist does not mutate somelist, but instead creates a new list, which contains x followed by all elements of somelist. This can be done in O(1) time because you only need to set somelist as the successor of x in the newly created, singly linked list.

If doubly linked lists were used instead, x would also have to be set as the predecessor of somelist's head, which would modify somelist. So if we want to be able to do :: in O(1) without modifying the original list, we can only use singly linked lists.

Regarding the second question: You can use ::: to concatenate a single-element list to the end of your list. This is an O(n) operation.

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