Scala Collections: List, Vector, Set and Map Explained

Reaching for List by habit for everything is one of the most common early Scala mistakes — not because List is bad, but because its performance characteristics are specific, and using it for the wrong access pattern turns an O(1) operation you’d expect into an O(n) one silently. This guide covers the actual collection hierarchy, how immutable collections avoid the naive “copy everything” cost through structural sharing, and a concrete decision guide for which collection actually fits your access pattern.

The Immutable-by-Default Hierarchy

val list: List[Int] = List(1, 2, 3)
val vector: Vector[Int] = Vector(1, 2, 3)
val set: Set[Int] = Set(1, 2, 3)
val map: Map[String, Int] = Map("a" -> 1, "b" -> 2)

As covered in the previous guide, all four of these are immutable by default with no special import — Scala’s Predef automatically brings the immutable versions into scope, and reaching for a mutable variant requires an explicit import scala.collection.mutable._.

List — A Linked List, Not an Array

val numbers = List(1, 2, 3)
val prepended = 0 :: numbers   // List(0, 1, 2, 3) — O(1), extremely fast
val appended = numbers :+ 4    // List(1, 2, 3, 4) — O(n), must traverse the entire list

List in Scala is a genuine singly-linked list, not an array — each element is a node pointing to the rest of the list. This is why prepending (::, pronounced “cons”) is O(1): it just wraps a new node pointing at the existing list, with zero copying of the existing structure. Appending (:+) is O(n): there’s no way to add to the end of a linked list without walking every node to find it first.

numbers(0)     // O(1) — the head is directly accessible
numbers(2)     // O(n) — must walk from the head, 2 nodes deep, to reach index 2

Random access by index is also O(n) for exactly the same structural reason — there’s no direct memory offset to jump to, only a chain of pointers to follow one at a time. This is the single most important fact about List: it’s fast specifically at operations touching the front (prepend, read the head, pattern-match into head/tail), and slow at anything touching the middle or end.

Structural sharing — why prepending is cheap without copying

0 :: numbers doesn’t copy [1, 2, 3] at all — it creates exactly one new node (0) pointing at the existing, unchanged list [1, 2, 3]. Both the original numbers and the new prepended list can coexist, sharing the same tail structure in memory, because neither can ever be mutated — this is only safe because the list is immutable; if [1, 2, 3] could change later, sharing it between two supposedly-independent lists would be a correctness bug. Structural sharing is the concrete mechanism that makes “immutable update” cheap rather than “copy the whole thing every time,” and it applies throughout Scala’s immutable collection library, not just List.

Vector — The General-Purpose Default

val v = Vector(1, 2, 3, 4, 5)
val updated = v.updated(2, 99)   // Vector(1, 2, 99, 4, 5) — efficient, not a full copy
val appended = v :+ 6              // efficient append, unlike List
val prepended = 0 +: v             // efficient prepend too, unlike a plain array

Vector is implemented as a shallow, wide tree (specifically, a 32-way branching trie) rather than a linked list or a flat array — this gives it effectively constant-time performance (technically O(log₃₂ n), which is so close to constant for any realistic collection size that it’s treated as O(1) in practice) for indexing, updating, appending, and prepending, at the cost of being marginally slower than List for the specific pure-prepend case List is optimized for, and marginally slower than a raw array for pure sequential iteration.

The practical rule: default to Vector unless you specifically know your access pattern is prepend-heavy and never needs random access or appending — that specific, narrow pattern (common in recursive algorithms processing a list head-first, like the pattern-matching recursion shown in the functions guide) is where List’s specialization genuinely wins. For general-purpose “a sequence of things I’ll read, update, and grow,” Vector is the safer, more broadly performant default.

Set — Unique Elements, No Guaranteed Order

val fruits = Set("apple", "banana", "cherry")
val withGrape = fruits + "grape"        // new Set, with grape added
val withoutBanana = fruits - "banana"    // new Set, banana removed

fruits.contains("apple")   // true — O(1) average, backed by a hash table internally
fruits ++ Set("date", "elderberry")   // union
fruits & Set("banana", "fig")           // intersection — Set("banana")

Set guarantees no duplicate elements and (for the default HashSet implementation) offers average O(1) membership testing via internal hashing — the same performance characteristic as a HashMap/HashSet in Java. contains being fast is Set’s entire reason for existing over a List: checking “is this element already present” in a List requires an O(n) linear scan, while a hash-based Set does it in near-constant time regardless of size.

// SortedSet for when order matters
import scala.collection.immutable.SortedSet
val sorted = SortedSet(3, 1, 4, 1, 5, 9)   // SortedSet(1, 3, 4, 5, 9) — sorted and deduplicated

Map — Key-Value Associations

val ages = Map("Alice" -> 30, "Bob" -> 25)

ages("Alice")               // 30 — throws NoSuchElementException if the key is missing
ages.get("Alice")            // Some(30) — the safe alternative, covered in depth in the next guide
ages.getOrElse("Carol", 0)   // 0 — fallback for a missing key

val updated = ages + ("Carol" -> 35)     // new Map with Carol added
val removed = ages - "Bob"                 // new Map with Bob removed
val merged = ages ++ Map("Dave" -> 40)     // combine two maps

Map’s direct apply-style access (ages("Alice")) throws if the key is missing — this is a real, common source of runtime errors for developers who forget the distinction, and the Option/Either/Try guide covers the idiomatic, safer alternatives (get, getOrElse) in depth, since avoiding exceptions for expected “might be missing” cases is one of Scala’s core functional-programming idioms.

// Iterating and transforming a Map
val doubled = ages.map { case (name, age) => (name, age * 2) }
val namesOnly = ages.keys.toList
val agesOnly = ages.values.toList
val adults = ages.filter { case (_, age) => age >= 18 }

Mutable Collections — When You Explicitly Opt In

import scala.collection.mutable

val buffer = mutable.ListBuffer[Int]()
buffer += 1
buffer += 2
buffer.append(3)
val finalList = buffer.toList   // convert to an immutable List once done building

val mutableMap = mutable.Map("a" -> 1)
mutableMap("b") = 2              // in-place assignment
mutableMap += ("c" -> 3)

ListBuffer exists specifically for the case where you’re incrementally building up a collection in a loop and want to avoid the (small, but real) cost of repeatedly producing new immutable collections one element at a time — build it up mutably inside a tightly-scoped function, then convert to an immutable collection (.toList, .toVector) before returning it or exposing it further. This pattern — mutable internally within a small, controlled scope; immutable at every boundary the rest of the program sees — is a common, idiomatic compromise that gets performance where it matters without leaking mutability into the broader program.

Choosing a Collection — A Decision Guide

LazyList — Infinite and On-Demand Sequences

def naturals(n: Int): LazyList[Int] = n #:: naturals(n + 1)

val nats = naturals(1)
nats.take(5).toList   // List(1, 2, 3, 4, 5) — only the first 5 elements are ever actually computed

LazyList computes elements only as they’re actually accessed, and caches each computed element for reuse — this is what makes defining a genuinely infinite sequence (naturals, which would recurse forever if eagerly evaluated) both possible and safe, since .take(5) only forces the first five elements to actually be computed. This is useful for generating sequences whose full extent either isn’t known upfront or would be wasteful to compute entirely (searching for the first N results matching a condition, for instance, without knowing in advance how far into the sequence that search needs to go).

Common Pitfalls

Frequently Asked Questions

Why does Scala default to Vector being recommended over List for general use, when List is more commonly seen in tutorials? Tutorials often reach for List first because pattern matching on head :: tail is a clean, illustrative way to teach recursion — but for real applications with unpredictable access patterns (random reads, appends, updates), Vector’s more uniform performance profile is the safer default in practice.

Is Array ever the right choice in idiomatic Scala? Yes — for raw performance-critical code, tight interop with Java APIs expecting arrays, or fixed-size numeric buffers, Array (a mutable, JVM-native array) is appropriate. It’s used more sparingly than List/Vector in typical application code specifically because it’s mutable and doesn’t fit Scala’s immutable-by-default idiom as naturally.

Does structural sharing mean immutable collections use less memory than I’d expect? Generally yes for related collections that share common structure (like a list and its prepended variant) — but each entirely independent immutable collection still needs its own full structure; sharing only happens between collections derived from one another, not between unrelated ones.

Why does ages("Alice") throw instead of returning None directly? apply on Map mirrors direct indexing semantics (like list(0) throwing for an out-of-bounds index) — for the explicitly-safe alternative, get (returning Option[V]) is the idiomatic choice, covered fully in the next guide.

When should I reach for a mutable collection instead of an immutable one? Almost exclusively for tightly-scoped, performance-sensitive local code building up a result incrementally — converting to an immutable collection before that result is exposed to the rest of the program. Reaching for mutable collections as a general default undermines the safety and reasoning benefits immutability provides throughout the rest of your codebase.

What’s Next

You now know which collection fits which access pattern, and why immutable collections avoid the naive performance cost their immutability might suggest. Next: Collection Operations, covering map, filter, fold, and reduce — the transformation vocabulary you’ll use on every one of these collection types daily.