In Scala the way you add elements to an immutable list as follows:
val l = 1 :: 2 :: Nil
l: List[Int] = List(1, 2)
What this means is you first create a Nil (Empty) List, and to that you add 2 and then 1. i.e. These operations are right-associated. So, effectively, it can be re-written in a clearer way, like so:
val l = (1 :: (2 :: Nil))
l: List[Int] = List(1, 2)
The question is, if List is supposed to preserve the order of insertion, and if 2 is added first to an empty list and then 1 is added, then why is the answer not l: List[Int] = List(2, 1) ??
This is because elements are prepended: first 2 then 1.
From definition of cons method:
def ::[B >: A] (x: B): List[B] =
new scala.collection.immutable.::(x, this)
here you can see that each time new instance of case class scala.collection.immutable.:: is created:
case class ::[B](val head: B, var tail: List[B]) extends List[B]
you just use your new element as a head for new list and your whole previous list as its tail.
Also prepend operation for immutable List takes constant time O(1), append is linear O(n) (from Scala docs).