When you first move from Java or Python to Scala, the way we handle lists can feel completely backwards. You're used to an ArrayList where you just call .add(). In a functional world, we don't "add" to a list; we create new versions of lists that share data with the old ones. It's a mental shift, but once it clicks, it makes your code significantly more predictable.

How do I actually define a list structure without using a mutable array?

We use a pattern called an Algebraic Data Type (ADT). Essentially, a linked list is either empty or it's a "cell" containing one element and a reference to the rest of the list. In Scala, we model this using a sealed trait and case classes.

sealed trait MyList[+A]
case object Nil extends MyList[Nothing]
case class Cons[A](head: A, tail: MyList[A]) extends MyList[A]

I use sealed here because it tells the compiler that Nil and Cons are the only two possible subtypes. This is huge for us later when we use pattern matching—the compiler will actually warn you if you've forgotten to handle the Nil case. The +A is a covariance annotation; it just ensures that a MyList[String] is also considered a MyList[Any], which makes the Nil object usable for any type of list.

If the list is immutable, does adding an item mean copying the whole thing?

This is the part that usually worries people. If you have a list of 10,000 items and you want to add one more, you might think you're duplicating those 10,000 items in memory. You aren't. We use something called structural sharing.

Because the list is immutable, we know the existing list will never change. So, to "add" an element to the front, we just create one new Cons cell that points to the existing list as its tail.

val original = Cons(1, Cons(2, Cons(3, Nil)))
val updated = Cons(0, original) 
// 'updated' is now [0, 1, 2, 3], but it literally points to the same memory as 'original'

This is why prepending (adding to the front) is an $O(1)$ operation. Appending to the end, however, is a different story—you'd have to copy every single cell to update the final Nil to a Cons. In functional programming, we almost always prepend and then reverse the list if order matters.

How do I process the list without using a while loop?

Since we can't mutate a counter or an index, we use recursion and pattern matching. Think of it as peeling an onion: you handle the first element (the head), and then you call the same function on the rest of the list (the tail) until you hit Nil.

Let's say we want to sum a list of integers:

def sum(list: MyList[Int]): Int = list match {
  case Nil => 0
  case Cons(head, tail) => head + sum(tail)
}

It's clean, right? But there's a catch. Every time we call sum(tail), we push a new frame onto the call stack. If your list has 100,000 items, you're going to hit a StackOverflowError. I've spent way too many late nights debugging that exact issue.

How do I prevent the stack from overflowing on large lists?

The solution is Tail Recursion. We need to rewrite the function so that the recursive call is the very last thing the function does. We do this by introducing an "accumulator" to carry the running total along with us.

import scala.annotation.tailrec

def sumSafe(list: MyList[Int]): Int = {
  @tailrec
  def loop(remaining: MyList[Int], acc: Int): Int = remaining match {
    case Nil => acc
    case Cons(head, tail) => loop(tail, acc + head)
  }
  
  loop(list, 0)
}

By adding the @tailrec annotation, we're asking the Scala compiler to optimize this into a jump (basically a while loop under the hood). If the function isn't actually tail-recursive, the compiler will throw an error, which is a great safety net.

📋 Practical Task

Exercise: Implementing a Recursive List Reverser

In this exercise, you will implement a function to reverse a custom functional linked list. Remember that appending to the end of a functional list is expensive, but prepending is cheap. The most efficient way to reverse a list is to iterate through it and prepend each element to a new list (the accumulator).

Requirements:

• Define the MyList[+A] trait, Nil object, and Cons class as shown in the lesson.
• Write a function reverseList[A](list: MyList[A]): MyList[A].
• The implementation must be tail-recursive. Use the @tailrec annotation to ensure the compiler optimizes it.
• Test your function with a list of at least 5 elements (e.g., Cons(1, Cons(2, Cons(3, Cons(4, Cons(5, Nil)))))) and verify the order is inverted.