[dmeb]

Trees with a very high branching factor can be used to support immutable vectors which support effectively constant time insert/remove/indexed lookup. However, it's not necessary to use trees to implement immutable lists.

In scala:

  val xs = List(1, 2, 3) // i.e. 1 -> 2 -> 3 -> Nil
  val ys = 42 :: xs  // i.e. 42 -> xs

In this instance, ys is a reference to a "Cons" node consisting of the value 42 and a reference to the immutable list xs. As xs is immutable, there is no risk of ys.tail changing, so we don't have to copy xs but just make a reference to it. So creating the "new" list ys only incurs the O(1) memory required to create the new node (42,xs).

Now, if you instead did:

  val xs = List(1,2,3) // 1 -> 2 -> 3 -> Nil
  val zs = xs ++ List(42) // 1 -> 2 -> 3 -> 42 -> Nil 

This would in fact trigger a copy of the entire list xs, as you are modifying the reference pointed to of the Cons node containing 3, requiring a copy of the entire xs so that your modification doesn't affect other references to the original xs.

Performance characteristics of different Scala collections: http://www.scala-lang.org/docu/files/collections-api/collect...