# Recursion: Let’s Look at Lists

“In computer science, a linked list is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer.”

## Visualizing lists

Because the `List` data structure — and the head and tail components of a `List` — are so important to recursion, it helps to visualize what a list and its head and tail components look like:

This creative imagery comes from the online version of “Learn You a Haskell for Great Good”, and it does a great job of imprinting the concept of head and tail components of a list into your brain. As shown, the “head” component is simply the first element in the list, and the “tail” is the rest of the list.

A slightly more technical way to visualize the head and tail of a list is like this:

An even more accurate way to show this is with a `Nil` value at the end of the `List`, because that’s what it really looks like:

## Linked lists and “cons” cells

To be clear, the `List` that I’m talking about is a linked list — scala.collection.immutable.List, which is the default list you get if you type `List` in your IDE or the REPL. This `List` is a series of cells, where each cell contains two things: (a) a value, and (b) a pointer to the next cell:

As shown, the last cell in a linked list contains the `Nil` value. The `Nil` in the last cell is very important: it’s how your recursive Scala code will know when it has reached the end of a `List`.

When drawing a list like this, here again is the head element:

and here are the tail elements:

Just like Haskell — and Lisp before it — the default Scala `List` works with these head and tail components, and I’ll use them extensively in the examples that follow.

For historical reasons these cells are known as “cons cells.” That name comes from Lisp, and if you like history, you can read more about it on Wikipedia.

## Note 1: The empty `List`

As a first note about `List`s, a `List` with no elements in it is an empty list. An empty `List` contains only one cell, and that cell contains a `Nil` element:

You can create an empty `List` in Scala in two ways:

``````scala> val empty = List()
empty: List[Nothing] = List()

scala> val empty = Nil
empty: scala.collection.immutable.Nil.type = List()``````

Because I haven’t given those lists a data type (like `Int`), the results look a little different, but if I add a type to those expressions, you’ll see that the result is exactly the same:

``````scala> val empty1: List[Int] = List()
empty: List[Int] = List()

scala> val empty2: List[Int] = Nil
empty: List[Int] = List()

scala> empty1 == empty2
res0: Boolean = true``````

In summary:

`List() == Nil`

## Note 2: Several ways to create `List`s

There are several ways to create non-empty `List`s in Scala, but for the most part I’ll use two approaches. First, here’s a technique you’re probably already familiar with:

``val list = List(1,2,3)``

Second, this is an approach you may not have seen yet:

``val list = 1 :: 2 :: 3 :: Nil``

These two techniques result in the exact same `List[Int]`, which you can see in the REPL:

``````scala> val list1 = List(1,2,3)
list: List[Int] = List(1, 2, 3)

scala> val list2 = 1 :: 2 :: 3 :: Nil
list: List[Int] = List(1, 2, 3)

scala> list1 == list2
res1: Boolean = true``````

The second approach is known as using “cons cells.” As you can see, it’s a very literal approach to creating a `List`, where you specify each element in the `List`, including the `Nil` element, which must be in the last position. If you forget the `Nil` element at the end, the Scala compiler will bark at you:

``````scala> val list = 1 :: 2 :: 3
<console>:10: error: value :: is not a member of Int
val list = 1 :: 2 :: 3
^``````

I show this because it’s important — very important — to know that the last element in a `List` must be the `Nil` element. (I like to say that the `Nil` element is to a `List` as a caboose is to a train.) We’re going to take advantage of this knowledge as we write our first recursive function.