List prepend
Note that lists are great when we insert a node at the beginning, in other words, prepend a value to the head of a list. Let's see how that works.
We have the list with values 17, 199, and 337. We prepend the value 37 first. Next, we prepend 99 to the resulting list. Finally, we prepend 12 to the new resulting list again.
When we prepend the value 37, we just allocate the node; while constructing this node, we append the original list to 37. In other words, 37 becomes the head and the original list becomes the tail.
Note that there is no copying needed at all. We just allocate the new node and append the existing list to it. As this does not affect the persistence of the already existing data structure, we have a very efficient prepend operation.
The version V0 is, as before, list b. V1 gets created when 37 is prepended to the list, V2 when 99 is prepended, and V3 when 12 is prepended. Thus, the complexity of prepend is O(1).
Here is the prepend method:
scala> def prepend[A...
