The Collections Library — From Lists to LazyLists | Scala Programming Guide

Introduction

Scala's collections library is one of the language's greatest strengths. Unlike Java, which has a monolithic collections API, Scala provides a unified, mathematically elegant hierarchy where every collection shares common operations. Whether you're building a video rental system with thousands of movies, managing a warehouse inventory with complex transformations, or processing streaming data in real-time, Scala's collections have you covered.

In this chapter, we'll explore the collections hierarchy, understand performance trade-offs, and master the operations that make Scala programming feel effortless.

The Collections Hierarchy Overview

Scala organizes collections into a clear inheritance hierarchy. Understanding this hierarchy is essential because it explains why different collections exist, how they relate, and which operations are available on each. The hierarchy isn't arbitrary—it reflects fundamental design trade-offs between performance, mutability, and evaluation strategy. When you recognize that a collection implements Iterable, you immediately know it supports map, filter, and fold, regardless of its specific type. This unified interface is one of Scala's greatest design achievements. Here's the mental model:

graph TD
    A["Iterable"] --> B["Seq"]
    A --> C["Set"]
    A --> D["Map"]
    B --> E["List"]
    B --> F["Vector"]
    B --> G["Range"]
    B --> H["Array"]
    B --> I["LazyList"]
    B --> J["ArrayBuffer"]

Key Insight: All collections inherit from Iterable, meaning they all support iteration and the same high-level operations (map, filter, fold, etc.). The differences lie in:

• Access patterns: Random access (Vector, Array) vs sequential (List)
• Mutability: Immutable (List, Vector) vs mutable (ArrayBuffer, mutable.Map)
• Evaluation: Eager (List, Vector) vs lazy (LazyList)
• Performance: Different time complexities for different operations

List — The Workhorse

The List is Scala's quintessential immutable collection. It's a singly-linked list, perfect for sequential processing. Lists are the default choice when you're primarily doing head/tail decomposition, prepending elements, or processing data recursively. Because of its linked structure, a List shares its tail with any new list created by prepending—this structural sharing is what makes prepend O(1) and enables the compiler to reason about immutability without paying runtime costs.

Creation

When creating a List, you have multiple strategies depending on your use case. Explicit creation works well when you know all elements upfront. The cons operator (::) is idiomatic for building lists recursively. The fill and tabulate factory methods handle repetition and generation patterns elegantly. Understanding these creation methods helps you write more expressive code and avoid unnecessary intermediate steps.

// Explicit creation
val emptyList: List[String] = List()
val movieList = List("Inception", "Interstellar", "The Matrix")

// Using the cons operator (::) - prepends an element
val moreMovies = "Oppenheimer" :: movieList
// Result: List(Oppenheimer, Inception, Interstellar, The Matrix)

// Using :+ operator - appends (slower than ::)
val appendedMovies = movieList :+ "Tenet"
// Result: List(Inception, Interstellar, The Matrix, Tenet)

// Creating from ranges
val numberList = (1 to 10).toList
// Result: List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

// Using List.fill - repeat the same element
val repeatedList = List.fill(5)("Netflix")
// Result: List(Netflix, Netflix, Netflix, Netflix, Netflix)

// Using List.tabulate - generate based on index
val indexedList = List.tabulate(5)(i => s"Movie $i")
// Result: List(Movie 0, Movie 1, Movie 2, Movie 3, Movie 4)

Head, Tail, and Pattern Matching

Lists are fundamentally recursive data structures: a list is either empty or consists of a head (first element) and a tail (remaining elements). Understanding this structure is critical because many list algorithms decompose using head and tail. Pattern matching is the idiomatic Scala approach—it's not just syntactic sugar but a powerful way to express recursive algorithms clearly. The compiler optimizes pattern matching, and using it helps readers immediately understand your intent. Working with head and tail directly is generally less preferred than pattern matching, which forces you to handle the empty case explicitly.

val movies = List("Dune", "Dune: Part Two", "Arrival", "Interstellar")

// head returns the first element
val firstMovie = movies.head
// Result: "Dune"

// tail returns everything except the first element
val restOfMovies = movies.tail
// Result: List(Dune: Part Two, Arrival, Interstellar)

// isEmpty and nonEmpty for safety checks
if (movies.nonEmpty) {
  println(s"First movie: ${movies.head}")
}

// Pattern matching is the Scala way
movies match {
  case first :: rest =>
    println(s"First: $first, Others: $rest")
  case _ => println("Empty list")
}

// Match multiple elements
movies match {
  case first :: second :: rest =>
    println(s"First: $first, Second: $second, Rest: $rest")
  case _ => println("Fewer than 2 elements")
}

Prepend vs Append

Understanding the performance difference between prepend and append is crucial for writing efficient list code. Prepend (::) is O(1) because you're just creating a new node pointing to the existing list—structural sharing at work. Append (:+) is O(n) because linked lists have no backward pointers; appending requires traversing to the end and creating a new chain. This asymmetry is a fundamental characteristic of singly-linked lists. When you need many appends, consider using Vector or collecting elements in a ListBuffer and then converting to a List. The pattern of building in reverse then reversing is a classic optimization for list construction.

// PREPEND (::) is O(1) - very fast
val scifi = List("Blade Runner", "Ghost in the Shell")
val extendedScifi = "2001: A Space Odyssey" :: scifi
// Instant! The new list just points to the old list.

// APPEND (:+) is O(n) - slow for large lists
val allScifi = scifi :+ "Ex Machina"
// This creates a new list by copying all elements.
// For a list of 1,000,000 elements, this is slow!

// Good pattern: build in reverse, then reverse
val movies = scala.collection.mutable.ListBuffer[String]()
movies += "Parasite"
movies += "Memories of Murder"
val finalList = movies.toList.reverse
// Or use a Vector if you need both efficient append and access

Core Operations on Lists

Lists support all the functional operations you'd expect: map transforms elements, filter selects based on predicates, flatMap chains operations, and fold reduces collections to single values. These operations are the bread and butter of functional programming. They compose elegantly, allowing you to express complex transformations as pipelines. The operations maintain immutability—they always return new collections rather than modifying the original. Understanding when to chain operations versus when to create intermediate variables is partly a matter of readability; generally, short chains are readable, but long chains benefit from intermediate steps with meaningful names.

// Scenario: Movie streaming platform with ratings
case class Movie(title: String, year: Int, rating: Double)

val movies = List(
  Movie("Inception", 2010, 8.8),
  Movie("Interstellar", 2014, 8.6),
  Movie("The Matrix", 1999, 8.7),
  Movie("Oppenheimer", 2023, 8.5)
)

// MAP - transform each element
val titles = movies.map(m => m.title)
// Result: List(Inception, Interstellar, The Matrix, Oppenheimer)

// FILTER - keep elements that satisfy a condition
val classiCMovies = movies.filter(m => m.year < 2000)
// Result: List(Movie(The Matrix, 1999, 8.7))

// FOLDLEFT - reduce to a single value, processing left to right
val totalRating = movies.foldLeft(0.0)((acc, movie) => acc + movie.rating)
// Step 1: 0.0 + 8.8 = 8.8
// Step 2: 8.8 + 8.6 = 17.4
// Step 3: 17.4 + 8.7 = 26.1
// Step 4: 26.1 + 8.5 = 34.6
// Result: 34.6

// FOLDLEFT with more complex logic - build a sentence
val sentence = movies.foldLeft("")((acc, movie) =>
  s"$acc${movie.title}(${movie.year}) "
)
// Result: "Inception(2010) Interstellar(2014) The Matrix(1999) Oppenheimer(2023) "

// FOLDRIGHT - fold from the right side
val revSentence = movies.foldRight("")((movie, acc) =>
  s"${movie.title}(${movie.year}) $acc"
)

// FLATMAP - map then flatten
val allWords = List("machine learning", "deep learning", "reinforcement learning")
val wordList = allWords.flatMap(phrase => phrase.split(" ").toList)
// Result: List(machine, learning, deep, learning, reinforcement, learning)

// DISTINCT - remove duplicates
val genres = List("sci-fi", "drama", "sci-fi", "action", "drama", "action", "sci-fi")
val uniqueGenres = genres.distinct
// Result: List(sci-fi, drama, action)

// SORTED - sort elements (requires Ordering)
val ratedMovies = List(8.8, 8.6, 8.7, 8.5)
val sortedRatings = ratedMovies.sorted
// Result: List(8.5, 8.6, 8.7, 8.8)

// SORTBY - sort by a function result
val sortedByRating = movies.sortBy(m => m.rating).reverse
// Result: List(Movie(Inception,...), Movie(The Matrix,...), ...)

// GROUPBY - partition by a function
val moviesByDecade = movies.groupBy(m => (m.year / 10) * 10)
// Result: Map(2020 -> List(Movie(Oppenheimer,...)), 2010 -> List(...), 1990 -> List(...))

Vector — The Balanced Alternative

Vector represents a fundamental shift in philosophy from List's linked-list approach. While List optimizes for prepend through structural sharing, Vector uses a tree structure (specifically a 32-ary tree) that balances performance across multiple operations. Why does this matter? Suppose you're building a large collection of user IDs and need both efficient append and frequent random access. List forces a tragic choice: either accept O(n) append costs or use prepend and reverse your logic. Vector solves this elegantly with O(log₃₂ n) for both operations, which in practice is nearly O(1) even for millions of elements. The tree structure is why a Vector of 33 million elements has a depth of only 5 levels—accessing any element requires at most 5 tree traversals. This predictable performance makes Vector the pragmatic default for most scenarios. Additionally, Vector maintains immutability through structural sharing; modifying one element creates a new Vector sharing most of the structure with the original, making it efficient for both memory and speed. Understanding this trade-off is crucial: Vector uses more memory than List and has higher constant factors, but its balanced performance makes it suitable for scenarios where you can't predict access patterns in advance.

Vector is Scala's answer to the age-old compromise between List's efficient prepend and random access efficiency: it provides both, using a tree-based structure that achieves logarithmic performance for both operations. Where List has O(n) random access (you must traverse to the nth element), Vector gives you O(log n) access. Where List's append is O(n), Vector's append is also O(log n). This balance makes Vector the default choice for most scenarios: you get near-constant-time append (constant-ish, with logarithmic growth that's negligible in practice), fast random access, and all the immutable/persistent semantics. The trade-off is slightly higher memory overhead and a smaller constant factor in operations compared to List, but these are usually irrelevant compared to the predictable performance characteristics. Think of Vector like a well-engineered array that never needs to be replaced: it grows efficiently, supports indexed access, and maintains immutability through structural sharing. Let's see why Vector often replaces List in practice:

// Creation
val vectorMovies = Vector("Dune", "Dune: Part Two", "Arrival")

// Indexed access - O(log n), much faster than List's O(n)
val secondMovie = vectorMovies(1)
// Result: "Dune: Part Two"

// Efficient append with :+
val extended = vectorMovies :+ "Interstellar"
// Result: Vector(Dune, Dune: Part Two, Arrival, Interstellar)

// Efficient prepend with +: (note the different operator)
val withPrequel = "Dune (1984)" +: vectorMovies
// Result: Vector(Dune (1984), Dune, Dune: Part Two, Arrival)

// All operations from List work on Vector
val highRatedMovies = Vector(
  Movie("Inception", 2010, 8.8),
  Movie("Interstellar", 2014, 8.6),
  Movie("The Matrix", 1999, 8.7)
).filter(m => m.rating > 8.6).map(m => m.title)
// Result: Vector(Inception, The Matrix)

// Converting between collections
val fromList = Vector(1, 2, 3)
val backToList = fromList.toList

Performance Insight: Vector uses a 32-ary tree, so even with millions of elements, accessing any element takes at most ~5-6 steps. For most use cases, Vector is the default choice for indexed collections.

Range — Generating Sequences

Range is a lazy collection that represents a sequence of integers without storing them in memory. This is a powerful concept: you can create a Range representing millions of numbers without allocating memory for those numbers. The cost is O(1) in space and O(1) to compute any individual element. Ranges are perfect for loops where you don't need the elements as a concrete collection, or for generating test data. If you actually need to materialize the elements (convert to List or Array), the cost becomes O(n), which is expected. Ranges are also the mechanism by which for loops work with numeric sequences—when you write for (i <- 1 to 10), Scala creates a Range and iterates over it.

Range is a lazy collection that represents a sequence of integers without storing them in memory.

// Inclusive range
val oneToTen = 1 to 10
// Creates Range(1, 2, 3, ..., 10) without allocating all numbers

// Exclusive range
val oneToNine = 1 until 10
// Creates Range(1, 2, 3, ..., 9)

// With step
val evenNumbers = 1 to 20 by 2
// Result: Range(1, 3, 5, 7, 9, 11, 13, 15, 17, 19)

// Descending
val tenToOne = 10 to 1 by -1
// Result: Range(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)

// Using Range for iterations
for (i <- 1 to 5) {
  println(s"Movie index: $i")
}

// Converting to concrete collections when needed
val rangeAsList = (1 to 100).toList
val rangeAsVector = (1 to 100).toVector
val rangeAsArray = (1 to 100).toArray

// Ranges are lazy - no performance penalty for large ranges
val million = 1 to 1000000
// This is instant - no memory allocation
val firstTen = million.take(10).toList
// This is also fast - only computes 10 elements

LazyList (Stream) — Lazy Evaluation and Infinite Sequences

LazyList (called Stream in older Scala versions) represents one of Scala's most powerful and subtle features. It's a collection that evaluates elements on-demand, enabling two transformative capabilities: infinite sequences and composable deferred computations. The power comes from lazy evaluation: a LazyList head is computed immediately, but the tail is wrapped in a thunk—a computation that hasn't yet run. This delays evaluation until the tail is requested. This seemingly simple mechanism unlocks sophisticated patterns. You can express infinite mathematical sequences (Fibonacci, primes, random numbers) without special machinery, just recursive LazyLists. You can chain transformations (map, filter) without eagerly computing intermediate results; the transformations compose and only execute when you actually consume elements via take or toList. This is profoundly different from eager evaluation: compare List(1 to 1000000).filter(_ > 999990).map(_ * 2).take(5) with LazyList.iterate(1)(_ + 1).filter(_ > 999990).map(_ * 2).take(5)—the eager version allocates a million-element list before filtering, while the lazy version computes only the final 5 elements. Caution: LazyList requires careful handling of mutable state. Because evaluation is deferred, sharing LazyLists between threads or interleaving computations with side effects creates subtle bugs. Prefer pure transformations over side effects. Also, LazyList caches computed values, so creating a long LazyList and discarding it wastes memory—unlike iterator-based approaches. Despite these caveats, LazyList is invaluable for infinite sequences, streaming architectures, and elegant expression of complex algorithms.

LazyList (called Stream in older Scala versions) is a collection that evaluates elements on-demand. This enables infinite sequences and composable computations.

// Create a LazyList explicitly
val numbers = LazyList(1, 2, 3, 4, 5)

// Create an infinite LazyList using a generator function
val infiniteOnes: LazyList[Int] = LazyList.continually(1)
// Represents: 1, 1, 1, 1, 1, ... (infinite)

// Generate the Fibonacci sequence (infinitely)
val fibs: LazyList[Long] = {
  def fib(a: Long, b: Long): LazyList[Long] =
    a #:: fib(b, a + b)  // #:: prepends lazily
  fib(1, 1)
}
// fibs represents: 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

// Take only what you need from infinite sequences
val firstTenFibs = fibs.take(10).toList
// Result: List(1, 1, 2, 3, 5, 8, 13, 21, 34, 55)

// Practical example: Generate a sequence of scaled movie ratings
val baseRating = 8.5
val ratingSequence: LazyList[Double] = LazyList.iterate(baseRating)(r => r + 0.1)
// Represents: 8.5, 8.6, 8.7, 8.8, 8.9, 9.0, ...

// Take ratings until we reach 9.0
val ratingsUpTo9 = ratingSequence.takeWhile(_ <= 9.0).toList
// Result: List(8.5, 8.6, 8.7, 8.8, 8.9, 9.0)

// Transform lazy sequences
val doubledOnes = infiniteOnes.map(_ * 2)
// Represents: 2, 2, 2, 2, 2, ... (still lazy, not computed yet)

val firstFiveDoubled = doubledOnes.take(5).toList
// Result: List(2, 2, 2, 2, 2)

// Real-world scenario: Generate movie recommendations
def recommendationStream(baseScore: Double): LazyList[Double] = {
  LazyList.iterate(baseScore)(score => score + 0.05)
}

val myRecommendations = recommendationStream(7.0)
  .take(5)
  .map(score => f"Movie with confidence score: $score%.2f")
  .toList
// Result: List("Movie with confidence score: 7.00", "Movie with confidence score: 7.05", ...)

Caution: LazyList can be tricky with mutable state. Keep transformations pure (no side effects).

Array — JVM Arrays with Scala Sugar

Array is Scala's wrapper around Java arrays. It's mutable and provides fast random access, but use it carefully to maintain immutability principles. Arrays are valuable primarily for interoperability with Java libraries that expect Array types and for performance-critical code where the overhead of wrapper types matters. Scala provides functional operations on Arrays (map, filter, etc.), but remember that these operations return new Arrays, not applying in-place transformations. When working with Arrays in idiomatic Scala code, convert them to immutable collections at boundaries to maintain functional guarantees.

// Creation
val emptyArray = Array[String]()
val movieArray = Array("Inception", "Interstellar", "The Matrix")

// Indexed access and mutation
movieArray(0) = "Oppenheimer"
// Array is now: Array(Oppenheimer, Interstellar, The Matrix)

// Length
val length = movieArray.length
// Result: 3

// Iteration
for (movie <- movieArray) {
  println(movie)
}

// All functional operations work on Array
val ratingsArray = Array(8.8, 8.6, 8.7, 8.5)
val mappedRatings = ratingsArray.map(r => r + 0.1)
// Result: Array(8.9, 8.7, 8.8, 8.6)

// Convert between Array and other collections
val arrayToList = movieArray.toList
val listToArray = List("Dune", "Dune: Part Two").toArray

// Practical: Working with JVM libraries that expect arrays
def processMovieRatings(ratings: Array[Double]): Double = {
  // Some JVM library method requiring an Array
  ratings.sum / ratings.length
}

val scalarRatings = Array(8.8, 8.6, 8.7)
val avgRating = processMovieRatings(scalarRatings)
// Result: 8.7

ArrayBuffer — When You Need Mutable Growth

ArrayBuffer is a mutable, indexed collection that grows dynamically. Use it when you're building a collection iteratively, accumulating elements based on input or complex logic. ArrayBuffer is backed by an Array that grows geometrically (typically doubling) when needed, providing O(1) amortized time for appending. This makes it far more efficient than repeatedly concatenating immutable Lists. The pattern is simple: create an ArrayBuffer, accumulate elements via +=, then convert to an immutable collection before returning. This pattern keeps your public API purely functional while leveraging efficient mutable operations internally.

import scala.collection.mutable

// Creation
val buffer = mutable.ArrayBuffer[String]()

// Add elements with +=
buffer += "Inception"
buffer += "Interstellar"
buffer += "The Matrix"
// buffer: ArrayBuffer(Inception, Interstellar, The Matrix)

// Add multiple elements
buffer ++= List("Oppenheimer", "Tenet")
// buffer: ArrayBuffer(Inception, Interstellar, The Matrix, Oppenheimer, Tenet)

// Insert at specific position
buffer.insert(1, "Dune")
// buffer: ArrayBuffer(Inception, Dune, Interstellar, The Matrix, Oppenheimer, Tenet)

// Remove by index
buffer.remove(1)
// buffer: ArrayBuffer(Inception, Interstellar, The Matrix, Oppenheimer, Tenet)

// Remove by value (first occurrence)
buffer -= "Matrix"
// buffer: ArrayBuffer(Inception, Interstellar, Oppenheimer, Tenet)

// Indexed access
val firstMovie = buffer(0)
// Result: "Inception"

// Update element
buffer(0) = "2001: A Space Odyssey"
// buffer: ArrayBuffer(2001: A Space Odyssey, Interstellar, Oppenheimer, Tenet)

// Convert to immutable when done
val finalList = buffer.toList
val finalVector = buffer.toVector

// Real-world scenario: Building a movie collection from API responses
def buildMovieCollection(movieTitles: List[String]): List[String] = {
  val collection = mutable.ArrayBuffer[String]()

  for (title <- movieTitles) {
    // Process each title (simulate validation)
    if (title.nonEmpty) {
      collection += title
    }
  }

  collection.toList  // Convert to immutable before returning
}

val result = buildMovieCollection(List("", "Inception", "Interstellar", ""))
// Result: List(Inception, Interstellar)

Performance Characteristics Table

Understanding trade-offs is crucial for choosing the right collection:

*LazyList is lazy; actual performance depends on how many elements you use.

Guidelines:

• List: Sequential processing, building recursively, prepending
• Vector: Default choice for indexed access and balanced performance
• Array: When interfacing with Java, need extreme performance
• LazyList: Infinite sequences, deferred computations, memory efficiency
• ArrayBuffer: Building collections iteratively, then converting to immutable

Common Operations Showcase

// Scenario: Movie warehouse inventory system
case class MovieItem(title: String, quantity: Int, price: Double)

val inventory = Vector(
  MovieItem("Inception", 5, 19.99),
  MovieItem("Interstellar", 3, 24.99),
  MovieItem("The Matrix", 8, 14.99),
  MovieItem("Oppenheimer", 0, 29.99)
)

// MAP - transform quantities to dollar values
val inventoryValues = inventory.map(item => item.title -> (item.quantity * item.price))
// Result: Vector((Inception,99.95), (Interstellar,74.97), (The Matrix,119.92), (Oppenheimer,0.0))

// FLATMAP - flatten nested structures
val allMovieTitles: List[List[String]] = List(
  List("Inception", "Interstellar"),
  List("The Matrix", "Oppenheimer"),
  List("Dune")
)
val flatTitles = allMovieTitles.flatMap(titles => titles)
// Result: List(Inception, Interstellar, The Matrix, Oppenheimer, Dune)

// FILTER - movies in stock
val inStock = inventory.filter(item => item.quantity > 0)
// Result: Vector(MovieItem(Inception,5,...), MovieItem(Interstellar,3,...), MovieItem(The Matrix,8,...))

// FOLDLEFT - total inventory value
val totalValue = inventory.foldLeft(0.0) { (acc, item) =>
  acc + (item.quantity * item.price)
}
// Result: 294.84

// FOLDRIGHT - build a report string
val report = inventory.foldRight("") { (item, acc) =>
  s"${item.title}: ${item.quantity} units\n$acc"
}
// Result: "Inception: 5 units\nInterstellar: 3 units\nThe Matrix: 8 units\nOppenheimer: 0 units\n"

// SCAN - track running total inventory value
val runningValues = inventory.scanLeft(0.0) { (acc, item) =>
  acc + (item.quantity * item.price)
}
// Result: Vector(0.0, 99.95, 174.92, 294.84, 294.84)

// SLIDING - compare consecutive items
val windows = inventory.sliding(2)
// Result: Iterator(Vector(Inception,Interstellar), Vector(Interstellar,The Matrix), Vector(The Matrix,Oppenheimer))

// GROUPED - batch into chunks
val batches = inventory.grouped(2)
// Result: Iterator(Vector(Inception,Interstellar), Vector(The Matrix,Oppenheimer))

// ZIP - pair two collections
val prices = Vector(19.99, 24.99, 14.99, 29.99)
val paired = inventory.map(_.title).zip(prices)
// Result: Vector((Inception,19.99), (Interstellar,24.99), (The Matrix,14.99), (Oppenheimer,29.99))

// UNZIP - split pairs back apart
val (titles, pricesBack) = paired.unzip
// titles: Vector(Inception, Interstellar, The Matrix, Oppenheimer)
// pricesBack: Vector(19.99, 24.99, 14.99, 29.99)

// DISTINCT - unique items (based on custom equality)
val tags = Vector("drama", "sci-fi", "drama", "action", "sci-fi", "action")
val uniqueTags = tags.distinct
// Result: Vector(drama, sci-fi, action)

// SORTED - by inventory quantity
val byQuantity = inventory.sortBy(item => item.quantity)
// Result: Vector(Oppenheimer:0, Interstellar:3, Inception:5, The Matrix:8)

// Complex chain - find the most valuable item in stock
val mostValuable = inventory
  .filter(_.quantity > 0)
  .sortBy(item => item.quantity * item.price)
  .lastOption
  .map(item => s"${item.title}: ${item.quantity * item.price}")
// Result: Some(The Matrix: 119.92)