Starting to write an immutable singly-linked list in Scala

For some examples in my new book on functional programming in Scala I needed to create a collection class of some sort. Conceptually an immutable, singly-linked list is relatively easy to grok, so I decided to create my own Scala list from scratch. This tutorial shows how I did that.

Back to top

Background: What is a Cons cell?

The first time I learned about linked lists was in a language named Lisp. In Lisp, a linked list is created as a series of “Cons” cells. A cons cell is simple, it contains only two things:

A Java tuple class (Tuple2 or Pair, if you prefer)

After working with Scala for a long time, I had to come back to Java for a while to work on an Android app. Right away I missed a lot of things from the Scala world, including all of the built-in Scala collection methods, and other things as simple as the Scala Tuple classes.

If you haven’t used them before, a Scala Tuple class lets you write code like this:

Tuple<String, Integer> t = new Tuple<>("age", 41);

If you’re comfortable with generics, the Java implementation of a Tuple class like this is simple:

How to create a Scala ArrayBuffer

As a quick note, this is how you create a Scala ArrayBuffer:

import scala.collection.mutable.ArrayBuffer

var fruits = ArrayBuffer[String]()
var ints = ArrayBuffer[Int]()

The key there is that the keyword new is not required before the ArrayBuffer.

While I’m in the neighborhood, here are some other ways you can work with ArrayBuffer:

Scala code to read a text file to an Array (or Seq)

As a quick note, I use code like this read a text file into an Array, List, or Seq using Scala:

def readFile(filename: String): Seq[String] = {
    val bufferedSource = io.Source.fromFile(filename)
    val lines = (for (line <- bufferedSource.getLines()) yield line).toList
Creating random strings and shuffling them (for JavaFX ListView) alvin January 17, 2017 - 4:35pm

As a short “note to self,” I just used this Scala code to (a) create a list that contains random strings of different lengths, then (b) shuffle the list of strings to create a more random effect:

How to shuffle (randomize) a list in Scala

As a quick note today, to shuffle a list in Scala, use this technique:


Here’s what this approach looks like in the Scala REPL: