Scala - Seq vs List vs Array Differences
• Seq is a trait representing immutable sequences, while List is a concrete linked-list implementation and Array is a mutable fixed-size collection backed by Java arrays
Key Insights
• Seq is a trait representing immutable sequences, while List is a concrete linked-list implementation and Array is a mutable fixed-size collection backed by Java arrays • List excels at prepending elements (O(1)) and head/tail operations but has O(n) random access, while Array provides O(1) random access but expensive resizing • Choose List for functional transformations and recursive algorithms, Array for numeric computations and Java interop, and Seq as an abstraction when implementation flexibility matters
Understanding the Type Hierarchy
Scala’s collection hierarchy places Seq as an abstraction over sequential collections. When you declare a method parameter as Seq[T], you’re accepting any sequential collection—List, Vector, Array (wrapped), or others.
import scala.collection.immutable.Seq
def processSequence(items: Seq[Int]): Int = items.sum
// All of these work
processSequence(List(1, 2, 3))
processSequence(Vector(1, 2, 3))
processSequence(Array(1, 2, 3)) // Implicitly wrapped
List is a concrete implementation of Seq, specifically a singly-linked list. Array isn’t technically a Seq—it’s a Java array—but Scala provides implicit conversions that wrap arrays in ArraySeq when needed.
val list: List[Int] = List(1, 2, 3)
val seq: Seq[Int] = list // Upcasting works naturally
val array: Array[Int] = Array(1, 2, 3)
val seqFromArray: Seq[Int] = array // Wrapped in ArraySeq
Performance Characteristics
The performance differences dictate which structure to use. List operations shine at the head but degrade toward the tail:
val list = List(1, 2, 3, 4, 5)
// O(1) - Fast operations
val prepended = 0 :: list
val head = list.head
val tail = list.tail
// O(n) - Slow operations
val lastElement = list.last
val appended = list :+ 6
val indexed = list(3)
Array provides constant-time random access but is mutable and fixed-size:
val array = Array(1, 2, 3, 4, 5)
// O(1) - Fast operations
array(3) = 10 // Direct index access and mutation
val element = array(2)
// O(n) - Requires copying
val expanded = array :+ 6 // Creates new array
Here’s a benchmark comparison for common operations:
import scala.collection.mutable.ArrayBuffer
def benchmarkAccess(size: Int): Unit = {
val list = (1 to size).toList
val array = (1 to size).toArray
// Random access - Array wins
val start1 = System.nanoTime()
(0 until 1000).foreach(_ => array(size / 2))
println(s"Array random access: ${System.nanoTime() - start1}ns")
val start2 = System.nanoTime()
(0 until 1000).foreach(_ => list(size / 2))
println(s"List random access: ${System.nanoTime() - start2}ns")
// Prepending - List wins
val start3 = System.nanoTime()
var tempList = list
(1 to 1000).foreach(i => tempList = i :: tempList)
println(s"List prepend: ${System.nanoTime() - start3}ns")
val start4 = System.nanoTime()
var tempArray = array
(1 to 1000).foreach(i => tempArray = i +: tempArray)
println(s"Array prepend: ${System.nanoTime() - start4}ns")
}
Memory Layout and Mutability
List nodes are allocated individually on the heap, with each node containing a value and reference to the next node. This enables structural sharing:
val original = List(2, 3, 4)
val modified = 1 :: original
// original and modified share nodes 2, 3, 4
// Structural sharing in action
val base = List(3, 4, 5)
val branch1 = 1 :: base
val branch2 = 2 :: base
// base is shared between branch1 and branch2
Array allocates contiguous memory, making it cache-friendly but preventing structural sharing:
val array1 = Array(1, 2, 3)
val array2 = array1.clone() // Must copy entire array
array2(0) = 10
// array1 remains unchanged, but we've duplicated memory
Arrays are mutable by default, which matters for concurrent code:
import scala.concurrent.Future
import scala.concurrent.ExecutionContext.Implicits.global
val mutableArray = Array(1, 2, 3, 4, 5)
// Dangerous - race conditions possible
Future {
mutableArray(0) = 100
}
Future {
println(mutableArray(0)) // Could print 1 or 100
}
val immutableList = List(1, 2, 3, 4, 5)
// Safe - transformations create new lists
Future {
val updated = 100 :: immutableList.tail
}
Future {
println(immutableList.head) // Always prints 1
}
Pattern Matching and Recursion
List’s structure makes it ideal for recursive algorithms using pattern matching:
def sum(numbers: List[Int]): Int = numbers match {
case Nil => 0
case head :: tail => head + sum(tail)
}
def reverse[A](list: List[A]): List[A] = {
@scala.annotation.tailrec
def loop(remaining: List[A], acc: List[A]): List[A] = remaining match {
case Nil => acc
case head :: tail => loop(tail, head :: acc)
}
loop(list, Nil)
}
// Usage
println(sum(List(1, 2, 3, 4, 5))) // 15
println(reverse(List(1, 2, 3))) // List(3, 2, 1)
Array doesn’t support pattern matching the same way:
// This doesn't work naturally
def processArray(arr: Array[Int]): Int = arr match {
case Array() => 0
case Array(single) => single
case _ => arr.head + processArray(arr.tail) // tail creates new array
}
Java Interoperability
Array maps directly to Java arrays, making interop seamless:
// Scala side
def processJavaArray(javaArray: Array[String]): Unit = {
javaArray.foreach(println)
}
// Java method signature: public void javaMethod(String[] args)
val javaLib = new JavaLibrary()
val scalaArray = Array("one", "two", "three")
javaLib.javaMethod(scalaArray) // Direct pass-through
List requires conversion:
import scala.jdk.CollectionConverters._
val scalaList = List("one", "two", "three")
val javaList = scalaList.asJava // Converts to java.util.List
// Going back
val backToScala = javaList.asScala.toList
Choosing the Right Collection
Use List when:
// Building collections incrementally from the front
def buildRange(n: Int): List[Int] = {
@scala.annotation.tailrec
def loop(current: Int, acc: List[Int]): List[Int] = {
if (current < 0) acc
else loop(current - 1, current :: acc)
}
loop(n, Nil)
}
// Processing with recursive algorithms
def quicksort(list: List[Int]): List[Int] = list match {
case Nil => Nil
case pivot :: tail =>
val (less, greater) = tail.partition(_ < pivot)
quicksort(less) ::: pivot :: quicksort(greater)
}
Use Array when:
// Numeric computations with frequent random access
def matrixMultiply(a: Array[Array[Double]],
b: Array[Array[Double]]): Array[Array[Double]] = {
val result = Array.ofDim[Double](a.length, b(0).length)
for {
i <- a.indices
j <- b(0).indices
k <- b.indices
} result(i)(j) += a(i)(k) * b(k)(j)
result
}
// Java interop scenarios
def writeToJavaBuffer(data: Array[Byte]): Unit = {
val outputStream = new java.io.ByteArrayOutputStream()
outputStream.write(data)
}
Use Seq when:
// Writing flexible APIs
def findDuplicates[A](items: Seq[A]): Seq[A] = {
items.groupBy(identity)
.collect { case (item, occurrences) if occurrences.size > 1 => item }
.toSeq
}
// Caller can pass any sequential collection
findDuplicates(List(1, 2, 2, 3))
findDuplicates(Vector(1, 2, 2, 3))
findDuplicates(Array(1, 2, 2, 3))
Conversion Between Types
Converting between these types has different costs:
val list = List(1, 2, 3, 4, 5)
val array = Array(1, 2, 3, 4, 5)
// List to Array - O(n), allocates contiguous memory
val listToArray = list.toArray
// Array to List - O(n), creates linked structure
val arrayToList = array.toList
// Both to Seq - cheap for List, wraps Array
val listAsSeq: Seq[Int] = list // No copy
val arrayAsSeq: Seq[Int] = array // Wrapped in ArraySeq
// Seq to concrete type - depends on underlying implementation
val seq: Seq[Int] = List(1, 2, 3)
val seqToList = seq.toList // No-op if already List
val seqToArray = seq.toArray // Always copies
Understanding these differences lets you make informed decisions based on your access patterns, performance requirements, and API constraints. Default to List for functional code, reach for Array when performance profiling shows random access as a bottleneck, and use Seq in public APIs to maintain flexibility.