Why exactly is prepend to a Scala List a constant time operation, but append a linear time operation?

Question

I am in the middle of learning Scala right now from Odersky's 'Programming in Scala' and I just read this

...the time it takes to append to a list grows linearly with the size of the list, whereas prepending with :: takes constant time...

Why exactly does it take linear time to append to append to a list but only constant time to prepend to it. My current guess is it's somehow implemented as a linked list internally which would explain the difference between the two operations. In that case, how are ListBuffers implemented which have a constant time append?

Answer 1

There's two questions here: one is a very basic one about lists, and the other is scala-specific. For the first, I'll draw a picture. The "List" abstract data type is one of the oldest in computer science; it goes right back to 1956 and the first implementation of the LISP language.

The list ADT is indeed implemented using a one-way linked list. Each element is traditionally called a cons cell (Nil indicates end of list):

+------+------+      +------+------+    +--------+
|   1  |   * -+----> |  3   +   * -+--->|  NIL   |
+------+------+      +-------------+    +--------+
^
|
val list1 

This corresponds to the chained "cons" (list construction) call in scala:

scala> val list1 = 1 :: 3 :: Nil
list1: List[Int] = List(3, 1)

List is an immutable data structure. We cannot destructively update it by rewriting any existing pointer/reference. So what if we want to prepend to it?

scala> val list2 = 0 :: list1
list2: List[Int] = List(0, 1, 3)

Creating list2 is very fast and easy, we simply create a new cons cell and prepend it to the existing list:

+------+------+      +------+------+      +------+------+    +--------+
|   0  |   *--+----->|   1  |   * -+----> |  3   +   * -+--->|  NIL   |
+------+------+      +------+------+      +-------------+    +--------+
 ^                   ^
 |                   |
 val list2           val list1 

The beauty of this is that it leaves all existing references unchanged, preserving immutability. However, if we want to /append/ to the list, we would have to overwrite the reference to Nil to a new element, thus mutating list1. Thus, the only way to do it is to duplicate the entire existing list and rewrite it thus:

scala> val list3 = list1 ++ (5 :: Nil)
list3: List[Int] = List(1, 3, 5)


+------+------+      +------+------+      +------+------+    +--------+
|   0  |   *--+----->|   1  |   * -+----> |  3   +   * -+--->|  NIL   |
+------+------+      +------+------+      +-------------+    +--------+
^                    ^                                           ^
|                    |                                           |
val list2            val list1                                   |
                                                                 |
                                                                 |
(copy)                                                           |
+------+------+      +------+------+    +--------+-------+       |
|   1  |   * -+----> |  3   +   * -+--->|   5    |    *--+-------+
+------+------+      +-------------+    +--------+-------+    
^
|
val list3 

It's a linear time operation because, to append to a list of length N, we have to make copies of all N cons cells (except for Nil).

As for scala's ListBuffer, its append works by directly mutating the backing list, rewriting the tail reference of the final cons cell, which has the slighly awkward looking type ::[A].

In List.scala:

final case class ::[B](override val head: B, private[scala] var tl: List[B]) extends List[B] {
   override def tail : List[B] = tl
   override def isEmpty: Boolean = false
}

[..] In ArrayList.scala:

/** Appends a single element to this buffer. This operation takes constant time.
*
*  @param x  the element to append.
*  @return   this $coll.
*/
def += (x: A): this.type = {
  if (exported) copy()
  if (isEmpty) {
    last0 = new :: (x, Nil)
    start = last0
  } else {
    val last1 = last0
    last0 = new :: (x, Nil)
    last1.tl = last0
  }
  len += 1
  this
} 

last1.tl = last0 is permitted because ::.tl has visibility private[scala], permitting unsafe "under the hood" operations for mutating collections such as ListBuffer.