Learn Scala 3 Fast: Collections: Other Sequence Classes

Before we get into more lessons on how to use sequence classes, it’s important for me to be clear about the List class and other sequence classes in Scala.

As mentioned, List is an immutable, linked-list, sequence class:

Immutable means that the elements in a List cannot be changed, and the size of a List cannot be changed.
Linked-list means that one element in a list is daisy-chained to the next element in the list. If you took programming classes in college, you probably wrote a linked-list in one of your classes. (This type of sequence is also known as a linear sequence.)
Sequence means that the class contains an ordered sequence of elements. The elements are always returned to you in the order that you put them into the sequence.

Scala has other sequence classes

At this point there are two important things to know about Scala’s sequence classes:

Scala has other sequence classes, and each is intended for a specific purpose
Because Scala is an object-oriented language, the sequence classes are created in a specific hierarchy

Of the other sequence classes, the most important ones to know are:

Vector is an immutable, indexed sequence
ArrayBuffer is a mutable, indexed sequence

We’ll look at those in a few moments, but first we need to look at some other things.

Indexed

Indexed means that any element in a sequence can be accessed very rapidly. For instance, to access the one-millionth element in a List, you have to start at the first element in the list and follow the linked-list daisy-chain until you get to the one-millionth element, and that’s a slow process, requiring one million operations. But with a Vector or ArrayBuffer — because they are created with a tree-like data structure — accessing the one-millionth element requires just a few hops.

Vector and ArrayBuffer are much faster for this purpose, and their structure also makes other operations, such as appending elements, much faster than List. To be clear, I only use List for small sequences.

The sequence class hierarchy

Because Scala is an OOP language, the List, Vector, and ArrayBuffer classes extend other data types. For example, this figure shows part of the Scala class hierarchy for immutable sequence classes:

(figure not included in this HTML version)

As shown, both List and Vector extend the base class Seq. This gives them many common methods that are implemented in Seq (and other classes above Seq that I don’t show.) But after Seq they diverge, and List extends LinearSeq, and Vector extends IndexedSeq, which gives them the performance attributes I just described.

Choosing a sequence

Because of these attributes, you generally use these sequence classes at the following times:

Use List or Vector when you want an immutable sequence
Prefer Vector over List when (a) you need to randomly access elements in the sequence, (b) the size gets large, or (c) when you’ll be constantly appending elements to the sequence
Use ArrayBuffer when you want a mutable sequence class (for instance, when you know that you will constantly add, remove, and update elements)

Also because of these attributes:

Vector and ArrayBuffer are typically your “go to” classes
List and Vector are used in an FP style, and in OOP when you know you’re sequence won’t be mutated
ArrayBuffer is used in an OOP style

Performance considerations

When you get into advanced use cases, the Scaladoc for these classes can also help you with additional information, such as performance characteristics. For instance, the ArrayBuffer Scaladoc page states, “Append, update and random access take constant time (amortized time). Prepends and removes are linear in the buffer size.” The constant time portion of the description is one reason that ArrayBuffer is the preferred mutable sequence.

Similarly, the Vector Scaladoc page states, “It provides random access and updates in O(log n) time, as well as very fast append/prepend/tail/init (amortized O(1), worst case O(log n)). Because vectors strike a good balance between fast random selections and fast random functional updates, they are currently the default implementation of immutable indexed sequences.”

I also include performance details in the Scala Cookbook.

List

All of that being said, the List class is a nice class to use when you’re working with small sequences. I tend to use it a lot, and it’s used a lot in the Scala library code as well.

The Scala library creators once ran a test where they replaced every instance of List in the libraries with Vector, and they actually saw a slight slowdown in the code, likely because most of their sequences are small, and List is more efficient with small sequences than Vector.

Therefore, I’ll show the List class in the following lessons, but remember that you can also use the Vector classes in these examples, because both classes are immutable sequences.