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)