Reversing a list

Let's look at how to reverse a list. Here is our first implementation:

scala> def slowRev(list: List[Int]): List[Int] = list match { 
     |   case Nil => Nil 
     |   case x :: xs => slowRev(xs) :+ x 
     | } 
slowRev: (list: List[Int])List[Int] 
 
scala> slowRev(List(1,2,3)) 
res2: List[Int] = List(3, 2, 1) 

 This is not a very efficient algorithm. We end up doing too much copying. The following diagram shows the copying of nodes for a list with three elements:

As we know from Chapter 2, Building Blocks, every time we append an element, we need to copy the entire source list. We cannot resort to pointer juggling, as in-place update is not allowed. Never forget that we work with immutable and persistent data structures.

An append operation has O(n) complexity. As there are n appends, the total complexity is O(n²).

The preceding version is not tail-recursive and hence is prone to Stack Overflow errors:

scala> import scala.annotation.tailrec 
import scala.annotation...