Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 37 ยท Collections

Lists and Vectors

Master Scala's List and Vector: building with :: and Nil, head and tail, pattern matching on lists, recursion, performance trade-offs, LazyList and common operations.

List is the workhorse of Scala. It is an immutable singly linked list, perfect for functional recursion and pattern matching. Vector is its better-balanced sibling, with fast access at any position. In this lesson you will build lists, take them apart, process them recursively and learn which of the two to pick. The Scala is read-only; Java and Kotlin demos run live.

Creating a List

SCALA
val primes = List(2, 3, 5, 7)
val empty = List.empty[Int]      // or Nil
val letters = List("a", "b", "c")
val range = List.range(1, 5)     // List(1, 2, 3, 4)
val filled = List.fill(3)("x")   // List(x, x, x)

A List[A] is either Nil (the empty list) or a cons cell made with :: that holds a head element and a tail list:

SCALA
val same = 2 :: 3 :: 5 :: 7 :: Nil   // List(2, 3, 5, 7)

The :: operator ends with a colon, so it is right-associative and is called on the list to its right. 1 :: xs means xs.::(1): it builds a new list in constant time and shares xs.

flowchart LR
  A["2"] --> B["3"] --> C["5"] --> D["7"] --> E["Nil"]

A list is a chain of cells. head is the first, tail is everything after it.

Reading a List

SCALA
primes.head          // 2
primes.tail          // List(3, 5, 7)
primes.last          // 7
primes.init          // List(2, 3, 5)
primes(2)            // 5  (but O(n), see below)
primes.take(2)       // List(2, 3)
primes.drop(2)       // List(5, 7)
primes.length        // 4
primes.headOption    // Some(2)
Nil.headOption       // None

head and tail on an empty list throw a NoSuchElementException / UnsupportedOperationException. When the list may be empty, use headOption, lastOption and drop/take, which are always safe.

Adding and joining

SCALA
val more = primes :+ 11       // List(2, 3, 5, 7, 11): O(n), copies the list
val first = 1 +: primes       // List(1, 2, 3, 5, 7): same as 1 :: primes
val both = primes ::: List(13, 17)   // List(2, 3, 5, 7, 13, 17)
val also = primes ++ List(13, 17)    // same

Appending to a list is slow because the whole chain must be copied. Prepend and reverse at the end, or use Vector or a buffer.

Pattern matching on lists

Lists work beautifully with match using :: and Nil:

SCALA
def sum(xs: List[Int]): Int = xs match
  case Nil => 0
  case head :: tail => head + sum(tail)

sum(List(1, 2, 3, 4))   // 10

Patterns can look deeper:

SCALA
def describe(xs: List[Int]): String = xs match
  case Nil => "empty"
  case x :: Nil => s"just $x"
  case x :: y :: Nil => s"two: $x and $y"
  case x :: _ => s"starts with $x"

describe(List(5)) is "just 5" and describe(List(1, 2, 3)) is "starts with 1".

The Kotlin version of recursive summing, runnable, uses head/tail style with slices:

Kotlin Recursive sum over a list (Kotlin comparison)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readln()), it gets the next line from this box.

A non-tail-recursive sum uses stack space proportional to the list length. For big lists, use xs.sum or foldLeft. Both are covered in transforming collections.

Vector

Vector is an immutable indexed sequence backed by a wide tree. Almost all operations, such as indexing, updating, prepending and appending, take effectively constant time (a handful of steps for any size).

SCALA
val v = Vector(10, 20, 30, 40)
v(2)                // 30
v.updated(1, 99)    // Vector(10, 99, 30, 40)
v :+ 50             // Vector(10, 20, 30, 40, 50)
0 +: v              // Vector(0, 10, 20, 30, 40)

The original v is unchanged. updated returns a new vector that shares most of its structure with the old one.

List vs Vector

Operation List Vector
Prepend (+:, ::) constant effectively constant
Append (:+) linear effectively constant
Index xs(i) linear effectively constant
Update at index linear effectively constant
Pattern match with :: yes no (use +: extractors)
Memory per element higher lower

Rule of thumb: use List when you process from the front, recurse or pattern match. Use Vector when you need random access or appends. If unsure, Vector is a safe default for data you store, while List suits short-lived sequences.

Java has the same two trade-offs in LinkedList (cheap at the ends) and ArrayList (cheap by index). Here the two are used through the same interface, which is also how Scala lets you swap List and Vector behind Seq:

Java One interface, two layouts (Java comparison)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The results are identical; only the cost of get(i) differs, linear for the linked list and constant for the array.

A Scala List is like the linked list (cheap at the head, costly by index), and Vector is like the array-backed list.

Common operations

SCALA
val xs = List(3, 1, 4, 1, 5, 9, 2, 6)
xs.sum              // 31
xs.max              // 9
xs.min              // 1
xs.sorted           // List(1, 1, 2, 3, 4, 5, 6, 9)
xs.reverse          // List(6, 2, 9, 5, 1, 4, 1, 3)
xs.distinct         // List(3, 1, 4, 5, 9, 2, 6)
xs.contains(5)      // true
xs.indexOf(4)       // 2
xs.take(3)          // List(3, 1, 4)
xs.slice(2, 5)      // List(4, 1, 5)
xs.zipWithIndex.take(2) // List((3,0), (1,1))
xs.mkString("[", ", ", "]") // "[3, 1, 4, 1, 5, 9, 2, 6]"
xs.grouped(3).toList // List(List(3, 1, 4), List(1, 5, 9), List(2, 6))

LazyList

A LazyList computes elements only when they are needed, so it can be infinite:

SCALA
val naturals: LazyList[Int] = LazyList.from(1)
naturals.take(5).toList            // List(1, 2, 3, 4, 5)

def fibs(a: Int = 0, b: Int = 1): LazyList[Int] = a #:: fibs(b, a + b)
fibs().take(8).toList              // List(0, 1, 1, 2, 3, 5, 8, 13)

The #:: operator builds a lazy cell. Remember take before toList on an infinite list, or the program never ends. Elements that were computed are cached.

Common mistakes

  • Appending in a loop (result = result :+ x) on a List. Use Vector or a ListBuffer.
  • Calling head or last on a possibly empty list.
  • Forgetting Nil when writing a recursive function, causing MatchError.
  • Indexing a long List repeatedly in a loop (each index is linear).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does 1 :: List(2, 3) evaluate to?

    :: prepends the element to the list on its right, giving List(1, 2, 3).
  2. 2. Which collection offers effectively constant-time indexing and appending while staying immutable?

    Vector is a tree-based indexed sequence with fast index, update, prepend and append.
  3. 3. What does List(1, 2, 3).headOption give for an empty list?

    headOption returns an Option, so an empty list gives None instead of throwing.
  4. 4. What does the pattern case x :: tail match?

    The :: pattern deconstructs a cons cell into head and tail.

Summary

  • A List is Nil or head :: tail; it is immutable and fast at the front.
  • Use headOption, take and drop for safe access; match with :: and Nil for recursion.
  • Appending to a List is linear; use Vector for random access and appends.
  • Operations return new collections that share structure with the original.
  • LazyList computes elements on demand and can be infinite.

Next: Sets and Maps