In Scala 2.9, the code ::: (prefix for the list) is as follows:
def :::[B >: A](prefix: List[B]): List[B] = if (isEmpty) prefix else (new ListBuffer[B] ++= prefix).prependToList(this)
whereas ++ is more general, since it accepts the CanBuildFrom parameter, that is, it can return a collection type other than List :
override def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[List[A], B, That]): That = { val b = bf(this) if (b.isInstanceOf[ListBuffer[_]]) (this ::: that.seq.toList).asInstanceOf[That] else super.++(that) }
So, if your return type is List , then they are both identical.
ListBuffer is a smart mechanism in that it can be used as a mutating builder, but is ultimately "consumed" by the toList method. So, what does (new ListBuffer[B] ++= prefix).prependToList(this) , first sequentially add all the elements to prefix (in example a ), taking the time O (| a |). Then it calls prependToList , which is a constant-time operation (receiver or b , no need to parse). Therefore, the total time is O (| a |).
On the other hand, as pst pointed out, we have reverse_:::
def reverse_:::[B >: A](prefix: List[B]): List[B] = { var these: List[B] = this var pres = prefix while (!pres.isEmpty) { these = pres.head :: these pres = pres.tail } these }
So, with a reverse_::: b this again takes O (| a |), therefore no more or less efficient than the other two methods (although for small list sizes you save the overhead of creating an intermediate ListBuffer ).
In other words, if you are aware of the relative sizes of a and b , you must make sure that the prefix is the smaller of the two lists. If you do not have this knowledge, you cannot do anything, because the size operation on List takes O (N) :)
On the other hand, in a future version of Scala, you can see an improved Vector concatenation algorithm, as shown in this ScalaDays talk . These are promises for solving the problem in O (log N) time.