Scala's mutable.ListBuffer seems to use List's tail function yet it is documented as having linear complexity?

Question

As of scala's 2.12.8 current documentation, List's tail is constant and ListBuffer's tail is linear. However, looking at the source code, it looks like there is no overwrite for the tail function and in most use-cases (such as remove the head element), List's tail function is explicitly called. Since ListBuffer seems to be little more than a List wrapper with a length var and a pointer to the last element, why is it linear?

I timed both methods and indeed it seems like List's tail is constant and ListBuffer's tail is indeed linear:

import scala.collection.mutable
import scala.collection.immutable

val immutableList: immutable.List[Int] = (1 to 10000).toList
val mutableListBuffer: mutable.ListBuffer[Int] = mutable.ListBuffer.empty[Int] ++= (1 to 10000).toList

// Warm-up
(1 to 100000).foreach(_ => immutableList.tail)
(1 to 100000).foreach(_ => mutableListBuffer.tail)

// Measure
val start = System.nanoTime()
(1 to 1000).foreach(_ => immutableList.tail)
val middle = System.nanoTime()
(1 to 1000).foreach(_ => mutableListBuffer.tail)
val stop = System.nanoTime()

println((middle - start) / 1000)
println((stop - middle) / 1000)

The results were, as documented:

1076
86010

However, if you use functions such as remove(0) that use List's tail, it is constant with the following results:

1350
1724

I expect that the linearity complexity comes from building a whole new list to return, but since the internal structure is a List, why not return the List's tail?

Answer 1

ListBuffer doesn't extend List, and the fact that it doesn't override tail doesn't mean it's using List#tail. If you look at the Definition Classes section of the docs for tail on ListBuffer, you'll see that it comes from TraversableLike, where it's defined like this:

override def tail: Repr = {
  if (isEmpty) throw new UnsupportedOperationException("empty.tail")
  drop(1)
}

And if you look at drop, you'll see that it uses a builder to construct a new collection containing all but the first element, which explains why it's linear.

As talex hints at in the comments above, ListBuffer#tail has to return a new collection because the original buffer could be modified, and the standard library designers have decided that you wouldn't want those modifications reflected in the result you get from tail.

Answer 2

since the internal structure is a List

If you look at the source, the internal structure is actually two lists:

private var start: List[A] = Nil
private var last0: ::[A] = _

last0 has this type because it's mutated using internal API (and it has to be for ListBuffer to make sense) (actually, just having two lists for the front and back parts with the back part in the reverse order should support all ListBuffer operations quite efficiently, including (amortized) O(1) tail; presumably the current implementation wins on constant factors, or maybe I am missing some operation it does much better).

So tail can't just "return the List's tail": it would at the least have to copy last0 because you can't share the same mutable part between two buffers. Even if the designers wanted changes to tail to reflect changes to the original ListBuffer and vice versa, sharing last0 wouldn't have this effect (without a lot more effort). This is already linear.

Note that if return type of ListBuffer#tail were List you also need to copy last0, or copy the contents from last0 to start before returning its tail, etc. So it doesn't make tail constant-time. But it does create additional problems: does ArrayBuffer#tail return Array? How do you declare tail's return type in GenTraversableLike if it's still available there?