What is an efficient way to concatenate lists?

Question

When we have two lists a and b, how can one concatenate those two (order is not relevant) to a new list in an efficient way ?

I could not figure out from the Scala API, if a ::: b and a ++ b are efficient. Maybe I missed something.

Answer 1

In Scala 2.9, the code for ::: (prepend to 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 generic, since it takes a CanBuildFrom parameter, i.e. it can return a collection type different from 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, the two perform identical.

The ListBuffer is a clever mechanism in that it can be used as a mutating builder, but eventually "consumed" by the toList method. So what (new ListBuffer[B] ++= prefix).prependToList(this) does, is first sequentially add all the elements in prefix (in the example a), taking O(|a|) time. It then calls prependToList, which is a constant time operation (the receiver, or b, does not need to be taken apart). Therefore, the overall time is O(|a|).

On the otherhand, 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|), hence is no more or less efficient that the other two methods (although for small list sizes, you save the overhead of having an intermediate ListBuffer creation).

---

In other words, if you have knowledge about the relative sizes of a and b, you should make sure that the prefix is the smaller of the two lists. If you do not have that knowledge, there is nothing you can do, because the size operation on a List takes O(N) :)

---

On the other hand, in a future Scala version you may see an improved Vector concatenation algorithm, as demonstrated in this ScalaDays talk. It promises to solve the task in O(log N) time.