Why are Scala's `Lists` implemented as linked lists

Question

I always thought that the benefit of linked lists was that you could add or remove items (especially not from the end) without having to copy lots of elements thanks to the beauty of pointers.

However, Scala's List is immutable (at least by default). What is the benefit of having an immutable linked list (because there are definite downsides, e.g. not O(1) element access.)

Thanks!

Answer 1

I think the main reason is that one of the most powerful uses of linked lists is head/tail splitting. There are lots of recursive algorithms that look like this one:

def listlen[A](xs: List[A], already: Int = 0): Int = xs match {
  case Nil => already
  case x :: rest => listlen(rest, already+1)
}

Of course, lists already know how to get their length; this is just an example. The point is that you pull off the head, and then do something else with the tail--lots of useful things work this way.

Since lists are immutable, we can do something else--we can take as much time as we want to evaluating the rest of our list! We don't have to finish in one go; we're sure it will never change. This would not be the case if the list were mutable--either we need to lock the list, preventing anyone else from seeing it, or we need to make a defensive copy of the whole thing just in case someone might swap it.

Now, if you really want a mutable list, there's mutable.LinkedList that has the nice insertion properties that you're talking about. But that doesn't give you the elegant recursion with peace of mind that the immutable lists give you.

(Note that you could do some of this with an immutable array-backed structure, but the possible benefit of a collection with each element wrapped is that you don't need to save or copy the whole array just because you need a few elements from the end; if the early elements in the list aren't pointed to any more, they can be garbage collected.)