What Is a List in Scala?
Scala's List is one of the most fundamental and heavily used collection types in the language. It is an immutable, singly-linked sequence defined in scala.collection.immutable, meaning every List holds elements of a single type (or a common supertype) and, once constructed, can never be modified in place. Structurally a List is a chain of "cons" cells, each holding one element (the head) and a reference to the rest of the list (the tail), terminating in the empty list Nil. This linked-list design makes prepending an element extremely cheap, but it makes random access and appending to the end comparatively expensive.
Cricket analogy: A Scala List is like a Test match batting order card pinned before the innings - you can add a new opener at the very top instantly, but if you want to check who's batting at number nine, you have to read down through every name before it, just like traversing head to tail.
Creating Lists and the Cons Operator
Lists can be created with the convenient List(...) factory syntax or built manually using the cons operator ::, which prepends an element onto an existing List. The literal 1 :: 2 :: 3 :: Nil is exactly equivalent to List(1, 2, 3), since :: is right-associative and Nil is the empty List that every chain must terminate in. Once you have a List, head returns its first element, tail returns everything after the first element (itself a List), and isEmpty checks whether the List has any elements at all - these three operations are the fundamental building blocks for everything else you do with a List.
Cricket analogy: Writing 1 :: 2 :: 3 :: Nil is like building a batting lineup one name at a time from the bottom up, ending the list with Nil the way an innings card ends with "extras" on the umpire's scoresheet, and head/tail let you peel off the opener and the rest of the order separately.
val empty: List[Int] = Nil
val nums: List[Int] = 1 :: 2 :: 3 :: Nil
val same: List[Int] = List(1, 2, 3)
println(nums.head) // 1
println(nums.tail) // List(2, 3)
println(nums.isEmpty) // false
println(nums(2)) // 3 (O(n) random access)Core List Operations: map, filter, foldLeft, :::
List supports the standard higher-order operations shared across Scala collections: map transforms every element, filter keeps only elements matching a predicate, and foldLeft aggregates elements into a single result while walking left to right. Two List-specific operations round out the toolkit: ::: concatenates two Lists, with a cost proportional to the length of the left-hand List because every one of its elements must be copied to attach the right-hand List at the end; and reverse flips element order, which is itself an O(n) traversal.
Cricket analogy: Using ::: to concatenate two Lists is like stitching together the first innings scorecard with the second innings scorecard - the cost depends on how long the first innings card is, since every entry in it must be copied before appending the second.
Appending a single element to the end of a List with :+ is O(n) because the whole list must be copied. If you're building a sequence by repeatedly appending, prefer prepending with :: and calling .reverse once at the end, or use a mutable ListBuffer and convert with .toList.
Pattern Matching and Recursion over Lists
Because List is defined inductively - either empty (Nil) or an element attached to another List (head :: tail) - pattern matching is the idiomatic way to process it recursively: case Nil => ... handles the base case and case head :: tail => ... handles the recursive case. A naive recursive function that isn't tail-recursive keeps one stack frame alive per element while it waits for the recursive call to return, which risks a StackOverflowError on sufficiently long Lists. Annotating a function with @tailrec asks the compiler to verify the recursive call is genuinely the last operation performed, so it can be compiled down into a loop that uses constant stack space regardless of List length.
Cricket analogy: Pattern matching case Nil => 0 and case head :: tail => ... on a batting list is like a scorer's rule: if the innings card is empty the total is zero, otherwise add the current batter's runs and recurse on the rest of the card - exactly how a tail-recursive run-total function walks a List.
import scala.annotation.tailrec
def sum(xs: List[Int]): Int = xs match {
case Nil => 0
case head :: tail => head + sum(tail)
}
@tailrec
def sumTailRec(xs: List[Int], acc: Int = 0): Int = xs match {
case Nil => acc
case head :: tail => sumTailRec(tail, acc + head)
}The plain sum function above is not tail-recursive - each call waits on head + sum(tail), so a List with hundreds of thousands of elements can throw a StackOverflowError. The @tailrec-annotated version accumulates the result as it goes so the compiler can turn it into a loop with constant stack usage.
- List is Scala's immutable, singly-linked sequence built from cons cells (::) terminating in Nil.
- Prepending with :: is O(1); appending with :+, random access with apply, and ::: concatenation cost is proportional to the length copied.
- head, tail, and isEmpty are the fundamental deconstruction operations.
- map, filter, and foldLeft transform and aggregate a List without mutation, returning new Lists.
- Pattern matching with case Nil / case head :: tail mirrors List's inductive definition and is the idiomatic way to recurse.
- Use @tailrec for recursive List functions to avoid StackOverflowError on large inputs.
Practice what you learned
1. What is the time complexity of prepending an element to a Scala List using ::?
2. Which expression correctly represents Nil being extended with elements 1, 2, and 3 using cons?
3. What happens when a non-tail-recursive function processes a List with hundreds of thousands of elements?
4. What is the time complexity of list1 ::: list2 (List concatenation)?
5. Which pattern correctly matches an empty List in Scala?
Was this page helpful?
You May Also Like
Maps and Sets
Understand Scala's Map and Set collections - how they guarantee unique keys and elements, the difference between immutable and mutable variants, and their core operations.
map, filter, and reduce
Master Scala's core higher-order functions for transforming, selecting, and aggregating collections declaratively instead of writing manual loops.
Tuples in Scala
Learn how Scala's Tuple types bundle a fixed number of heterogeneous values, how to create, access, and destructure them, and when a case class is a better fit.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics