Work with List, Vector, and Array

You've spent years in Python blissfully calling append, extend, and slicing lists without a second thought. Now you’re learning Scala, and suddenly there are three different types of sequences — List, Vector, and Array — each with its own performance profile, mutability characteristics, and idiomatic usage. It feels like walking into a room where your trusty Python list has been split into clones, and you don't know which one to use without looking foolish. This lesson demystifies the trio, gives you a clear mental model to choose the right tool for the job, and walks you through hands-on examples so you can say goodbye to guesswork and write Scala code that's both correct and efficient.

The problem this lesson solves

Python developers live on list. It’s the workhorse collection — used for everything from a quick stack to a data pipeline buffer. But in Scala, the moment you open the documentation, you see List, Vector, and Array all described as "sequences," and the internet is full of conflicting advice: "Use Vector for most things," "List is recursive," "Array is just a Java array."

The real pain appears when you start writing code. Let’s say you build a function that repeatedly adds elements to the end of a collection. In Python:

items = []
for i in range(100000):
    items.append(i)

That runs in O(n) overall. Now try the naive Scala List:

var items = List[Int]()
for (i <- 0 until 100000) {
    items = items :+ i   // appending at the end — O(n) each time!
}

That code will be painfully slow because List prepends in O(1) but appends at the end in O(n). If you don’t understand the difference between List, Vector, and Array, you’ll make performance mistakes like this all over your codebase. This lesson solves that problem by giving you a practical roadmap: when to use which collection, how they behave, and what pitfalls to avoid.

By the end, you’ll be able to read a Scala codebase and instantly understand why one collection was chosen over another, and you’ll know how to translate your Python habits into efficient Scala idioms.

Core concept / mental model

Think of the three collections as different storage apprentices in a workshop:

• List is a linked list — each element knows its successor, but not its predecessor. It's the cons cell model: a head element and a tail list. Operations at the head (prepend) are lightning fast (O(1)), but random access requires walking the chain (O(n)). It’s immutable by default — perfect for recursive algorithms.

• Vector is a deque-like structure with a branching factor (typically 32). It gives you near-constant-time random access (O(log32(n)) ≈ O(1) for practical sizes) and O(1) append/prepend. It’s the jack-of-all-trades — you can add to the front or back quickly and access any index quickly. It’s also immutable, and it’s the default choice for most "I need a list-like thing" scenarios.

• Array is the raw, mutable counterpart. Underneath the hood, it’s a contiguous block of memory — same as Array in Java or list from Python’s array module. You get O(1) random access and O(1) update of a single element, but resizing or inserting in the middle is expensive. Using it for a large collection that changes size frequently is bad news.

The mental model boils down to:

In Python, you likely used list for everything. In Scala, you have to be more deliberate. The key: understand the operation you perform most often and pick the collection that excels at it.

How it works step by step

Let’s break down the practical steps to choose and work with each collection.

Step 1 — Identify your operation pattern

Ask yourself these questions:

1. Do I need to add elements to the front repeatedly? → Use List.
2. Do I need random access by index and occasional appends? → Use Vector.
3. Do I need to call a Java library that expects an array, or do I need a fixed-size mutable buffer? → Use Array.

Step 2 — Understand creation and type inference

Creating each collection is slightly different. List and Vector are immutable, so the standard way is to use their companion object's apply method or the :: operator for List. Array is mutable, but you can create it with Array(...) as well.

// List — immutable linked list
val list = List(1, 2, 3)
val prepended = 0 :: list   // 0 in front

// Vector — immutable, fast access
val vector = Vector(1, 2, 3)
val withAppend = vector :+ 4

// Array — mutable, JVM array
val array = Array(1, 2, 3)
array(0) = 99  // update in place

Step 3 — Apply transformations with care

Both List and Vector are immutable, so transformations return new collections. Array is mutable, and transformations often return a new Array too, but you can also mutate elements directly.

Step 4 — Choose based on performance

If you’re doing a fold that rebuilds from the front, List is your friend. If you’re doing lookups and updates by index, Vector is better. If you need to pass data to a legacy Java API, Array is the only option.

Hands-on walkthrough

Let’s get our hands dirty. We’ll write a small program that compares the three collections in a realistic scenario: building a collection by appending at the end, then accessing random indices.

Example 1: Appending at the end — the trap

// Beware: `:+` on a List is O(n) each time
val initialList = List[Int]()
val appendedList = (0 until 10000).foldLeft(initialList)((acc, i) => acc :+ i)
// This takes O(n^2) — awful!

// Vector appends efficiently
val initialVector = Vector.empty[Int]
val appendedVector = (0 until 10000).foldLeft(initialVector)((acc, i) => acc :+ i)
// Near O(n) — much better!

Output (conceptually):

List approach: extremely slow, may time out.
Vector approach: completes quickly.

Example 2: Building a collection from the head

// Prepend to a List is O(1) — build from the front
val listFromFront = (1 to 10).foldLeft(List.empty[Int])((acc, i) => i :: acc)
// listFromFront is List(10, 9, 8, ..., 1) — order reversed, but fast.

// To keep order, reverse at the end
val inOrder = (1 to 10).foldLeft(List.empty[Int])((acc, i) => i :: acc).reverse
// inOrder is List(1, 2, ..., 10)

Output:

listFromFront: List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)
inOrder: List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

Example 3: Random access and mutation with Array

import scala.collection.mutable.ArrayBuffer

// Use Array for fixed-size buffers
val arr = Array(10, 20, 30)  // indices 0, 1, 2
arr(1) = 42                  // update in place
println(arr.mkString(", ")) // 10, 42, 30

// For dynamic resizing, use ArrayBuffer (like Python's list)
val buffer = ArrayBuffer(1, 2, 3)
buffer += 4                  // append
buffer.insert(1, 99)         // insert at index 1
println(buffer.toArray.mkString(", ")) // 1, 99, 2, 3, 4

Output:

10, 42, 30
1, 99, 2, 3, 4

Example 4: Choosing the right collection for a specific task

Imagine you need to parse a log file line by line, process each line, and keep results in a list. If you need to access results by index later, use Vector. If you’re just processing sequentially and don’t need random access, List is fine.

val lines = scala.io.Source.fromFile("logs.txt").getLines().toVector
// Now we can safely index into lines
val thirdLine = lines(2)

Pro tip: In Scala 2.13+, the default scala.collection.immutable.Seq is List, but in many guidelines, Vector is recommended as the default for general-purpose immutabilty due to its better balance. However, Seq is an alias that you can use when you don’t care about the underlying type.

Compare options / when to choose what

Here’s a head-to-head comparison to help you decide at a glance. Use this table as your quick reference.

When to pick which

• Pick List when you’re writing a recursive function that builds results via ::, or when you need to perform many prepends and then convert once. Think of it as the natural fit for pattern matching on the head/tail.
• Pick Vector when you need a balance between fast random access and fast updates/appends — that’s most day-to-day collection work in Scala. It’s the “safe default” for collections you’ll query and modify.
• Pick Array when you need to pass data to a Java method that expects int[] or String[], or when you’re doing heavy numerical computation where mutability and cache locality matter (e.g., matrix operations).

Pro tip: Be wary of premature optimization. Unless you measure a bottleneck, Vector usually gives you the best speed and safety. List shines in algorithmic code where recursion is natural, but it’s a poor choice for random access.

Troubleshooting & edge cases

Mistake 1: Using :+ on a List inside a loop

As seen in the earlier example, repeated :+ on a List causes O(n²) behavior. Instead, build with :: and reverse, or switch to Vector.

Mistake 2: Expecting Array to be immutable

Array is mutable — if you accidentally share an Array and mutate it, you might break invariants in your code. Use immutable collections unless you truly need mutability.

Mistake 3: Forgetting that List is recursive and can cause stack overflow

List is a recursive data structure, and certain operations (like length or last) are O(n). More dangerously, if you implement a recursive function that isn’t tail-recursive, you’ll hit StackOverflowError for large lists. Use tail recursion or switch to Vector.

Edge case: Empty collection type inference

Always specify the type when creating an empty collection:

val emptyList = List[Int]()  // correct
val emptyArray = new Array[Int](0)  // correct
// val emptyArray = Array()  // This gives Array[Nothing], which is often not what you want.

Edge case: Array and equality

In Scala, Array equality is based on reference identity, not content. To compare arrays by content, use sameElements:

val a = Array(1, 2, 3)
val b = Array(1, 2, 3)
println(a == b)          // false (reference comparison)
println(a.sameElements(b)) // true (content equality)

Edge case: Converting between collections

You’ll often need to convert. Use .toList, .toVector, .toArray, or .toSeq. Be aware that .toArray on a List is O(n) but fine.

What you learned & what's next

You now have a solid grasp of List, Vector, and Array and can confidently choose the right collection for your Scala code. You learned:

• The key differences between the three: List is a recursive linked list good for prepends; Vector is a balanced tree providing fast random access and appends; Array is a mutable contiguous block for Java interop and performance.
• How to create, update, and transform each collection, and the performance implications of different operations.
• How to avoid common pitfalls like O(n²) appends to List or forgotten mutability of Array.
• To apply this knowledge in a hands-on walkthrough with practical examples.

In the next lesson, you’ll dive into pattern matching with Scala’s powerful match expressions, where the recursive nature of List really shines. You’ll learn how to deconstruct collections and write elegant, concise code that directly mirrors the data’s shape.

Keep practicing — write a small function that accepts a List, a Vector, and an Array, and performs the same logic on each. Observe how the implementation and performance differ. This will cement your understanding before moving on.