Scala List, in depth: cons cells, structural sharing, the cost model, recursion and stack safety, ListBuffer and when to use something else

What a List is

In the 2.13 library, List[+A] is a sealed abstract class with exactly two subtypes: the case object Nil, the empty list, and the final case class :: (pronounced cons), which holds a head element and a reference to the rest of the list. A list of three elements is three cons cells chained together and ending in Nil.

Because the hierarchy is sealed, the compiler knows a list is either empty or a cons cell, so a pattern match covering both is exhaustive. The +A makes List covariant: a List[Cat] is a List[Animal], and Nil, a List[Nothing], fits any list type. Covariance is safe only because List is immutable; the type rules behind it are in the Scala type system.

val xs: List[Int] = List(1, 2, 3)        // same as 1 :: 2 :: 3 :: Nil
val ys = 0 :: xs                         // :: is right-associative: xs.::(0)
val zs = xs.tail                         // List(2, 3), no allocation

xs match {
  case Nil          => "empty"
  case h :: Nil     => s"one element: $h"
  case h :: t       => s"head $h, then ${t.length} more"
}

One implementation detail matters later. In the 2.13 source the tail field of :: is declared private[scala] var next. It is mutable, but only code inside the scala package can touch it, and the library mutates it only while building a list that nobody else has seen yet. From your code's point of view, a published list never changes.

Structural sharing

Because cells never change, a new list can reuse an old one. Prepending allocates one cell that points at the existing list. Taking the tail returns a reference to the second cell. Neither copies anything.

Sharing is what makes List cheap as a persistent data structure: many versions of a list can coexist, each differing by a few cells at the front. It also means operations that change the end of a list must copy everything before the change. Appending one element to a list of n elements copies all n cells, because the last cell's next must point somewhere new and every cell before it must point at a new successor.

Sharing makes List a natural persistent stack. An editor's undo history can be a List[State]: pushing a state is s :: history, undoing is history.tail, and every earlier version stays valid, so a background thread rendering a snapshot can keep its reference while the user carries on editing. No locks are needed, because no thread ever sees a cell change. The same property lets an actor or a Ref in an effect library publish a new list by swapping one reference.

The library takes care of the one moment when a cell does change: while ListBuffer or a method such as map is still linking cells together. In 2.13 ListBuffer.toList issues a release fence before handing the cells over, so another thread that receives the list through a safe publication sees fully linked cells.

The cost model

The scaladoc summarises it: List has constant-time prepend and head and tail access, and most other operations are linear. In detail:

The practical rule: if your code calls length, apply or :+ on a list inside a loop, the algorithm is quadratic. Measured costs, including allocation and boxing, are compared across collections in Scala collections performance.

Memory footprint

Each cons cell is a JVM object with a header and two references. On a 64-bit JVM with compressed references that is roughly 24 bytes per cell after alignment; exact numbers depend on the JVM and its flags. Elements are references too, so a List[Int] stores boxed java.lang.Integer objects, each about 16 bytes, except for small values the JVM caches. A list of one million distinct integers can therefore occupy around 40 MB, against 4 MB for an Array[Int]. Pointer chasing also defeats CPU caches, so iteration over a List is slower per element than over an array even when both are linear.

None of that matters for a list of twenty configuration entries. It matters a great deal for a list of ten million events held in memory; for bulk numeric data, use an array or a specialised structure.

Recursion and stack safety

Pattern matching invites recursive functions, and the naive version breaks on long lists:

import scala.annotation.tailrec

// Not tail-recursive: the addition happens after the recursive call returns.
def sumNaive(xs: List[Long]): Long = xs match {
  case Nil    => 0L
  case h :: t => h + sumNaive(t)         // one stack frame per element
}

// Tail-recursive: the recursive call is the last thing evaluated.
def sum(xs: List[Long]): Long = {
  @tailrec def go(rest: List[Long], acc: Long): Long = rest match {
    case Nil    => acc
    case h :: t => go(t, acc + h)
  }
  go(xs, 0L)
}

val big = List.range(0L, 1_000_000L)
// sumNaive(big)   // StackOverflowError with a default thread stack
sum(big)           // runs in a loop; no stack growth
big.foldLeft(0L)(_ + _)  // same result, library implementation

The @tailrec annotation does not make a function tail-recursive; it makes the compiler fail if the function is not, so a later edit cannot quietly reintroduce the stack overflow. The compiler turns a self-recursive tail call into a loop.

foldRight looks dangerous because it combines from the right, which a naive recursive version would do with one stack frame per element. In 2.13 the List implementation reverses the list first and then iterates forwards, so it is stack-safe at the price of allocating a reversed copy. Prefer foldLeft when the operation allows it; fold, map and filter in depth covers how the folds differ.

Building lists: prepend and reverse, or ListBuffer

Because prepending is cheap and appending is not, the idiomatic way to build a list in order is to prepend while walking the input and reverse once at the end, which costs two linear passes. The alternative is scala.collection.mutable.ListBuffer, which keeps a reference to the first and last cells and appends in constant time by setting the last cell's next field, the private[scala] var shown earlier.

Its toList is constant-time. It sets an internal aliased flag and returns the existing chain of cells. If you later mutate the buffer, it first copies its contents into fresh cells, so the list you were handed is never altered. List's own map uses the same trick, linking fresh cells through next before publishing them, so it builds its result in one pass without an extra reverse.

import scala.collection.mutable.ListBuffer

final case class Event(ts: Long, level: String, msg: String)

def parse(lines: Iterator[String]): List[Event] = {
  val buf = ListBuffer.empty[Event]
  for (line <- lines) line.split(" ", 3) match {
    case Array(ts, lvl, msg) => ts.toLongOption.foreach(t => buf += Event(t, lvl, msg))
    case _                   => ()       // skip malformed lines
  }
  buf.toList      // O(1): hands over the cells; later buf mutations copy first
}

Worked example: the quadratic append

A team's log parser read 100,000 lines and built a list with events = events :+ e. Each append copies the whole list, so the total work is about 1 + 2 + ... + 100,000 cell copies, roughly five billion, plus five billion short-lived objects for the garbage collector. Parsing took minutes on a file that should take well under a second.

Three fixes are available, all linear: build with e :: events and call reverse once at the end; use a ListBuffer as above; or, if the code then indexes into the result, build a Vector, whose append and index are effectively constant time. The second version keeps the public type as List and changes nothing for callers. Whichever you pick, add a test with a large input so the quadratic version cannot come back unnoticed.

Equality and other traps

• Equality is by elements, across Seq types. List(1, 2) == Vector(1, 2) is true, because both are Seqs with the same elements in order. Comparing lists is O(n), so using long lists as map keys makes every lookup expensive.
• head on an empty list throws. Nil.head raises NoSuchElementException. Use headOption or a pattern match.
• Pattern matching with a non-exhaustive match. Matching only case h :: t compiles with a warning and throws MatchError on Nil. Treat that warning as an error.
• Huge literal lists or deep recursion in user code. Library methods are iterative, but your own recursive helpers are not unless they are tail-recursive.
• Lazy expectations. List is strict: xs.map(f).filter(p).take(10) evaluates f on every element. Use iterator or view when you only need a prefix.

Choosing List or something else

List remains the right default for small, functionally processed sequences, especially recursive algorithms and stacks. Higher-order functions on lists are covered in Scala higher-order functions.

Failure modes

What to do next

1. Search your code for :+, .length and (i) on List values inside loops, and replace them with prepend-and-reverse, ListBuffer or Vector.
2. Annotate every recursive list function with @tailrec, or rewrite it with foldLeft.
3. Enable fatal warnings for non-exhaustive matches so an unhandled Nil fails the build.
4. Replace head with headOption or a pattern match wherever the list can be empty.
5. Profile memory of any List holding more than a few hundred thousand elements and move bulk data to arrays.
6. Use iterator or view for pipelines that need only a prefix of the result.
7. Write one benchmark with a large input for each hot list-building path so a quadratic regression is caught in CI.