Scala - List - Create, Access, Modify
• Scala Lists are immutable, persistent data structures that share structure between versions, making operations like prepending O(1) but appending O(n)
Key Insights
• Scala Lists are immutable, persistent data structures that share structure between versions, making operations like prepending O(1) but appending O(n) • Access patterns differ significantly from arrays: head/tail operations are constant time, but random access by index degrades to O(n) due to linked list implementation • Modifications create new List instances through structural sharing, enabling safe concurrent access without defensive copying
Creating Lists
Scala provides multiple approaches to construct Lists, each suited to different scenarios.
// Using List companion object apply method
val numbers = List(1, 2, 3, 4, 5)
val strings = List("apple", "banana", "cherry")
// Empty list
val empty = List.empty[Int]
val alsoEmpty = List[String]()
val nil = Nil // The singleton empty list
// Using cons operator (::)
val consed = 1 :: 2 :: 3 :: Nil
// Equivalent to: ::(1, ::(2, ::(3, Nil)))
// Range-based creation
val range = List.range(1, 10) // 1 to 9
val rangeWithStep = List.range(0, 20, 5) // 0, 5, 10, 15
// Fill and tabulate for pattern-based creation
val zeros = List.fill(5)(0) // List(0, 0, 0, 0, 0)
val squares = List.tabulate(5)(n => n * n) // List(0, 1, 4, 9, 16)
// From other collections
val fromArray = Array(1, 2, 3).toList
val fromSeq = (1 to 5).toList
The cons operator :: is right-associative and prepends elements efficiently. Understanding this operator is crucial for pattern matching and recursive operations.
// Builder pattern for efficient construction
import scala.collection.mutable.ListBuffer
def buildLargeList(n: Int): List[Int] = {
val builder = ListBuffer[Int]()
for (i <- 1 to n) {
builder += i
}
builder.toList
}
// This is more efficient than repeated append operations
// Bad: var list = List[Int](); for (i <- 1 to n) list = list :+ i
Accessing Elements
List access operations exploit the linked list structure. Head and tail operations are optimal, while indexed access requires traversal.
val fruits = List("apple", "banana", "cherry", "date", "elderberry")
// Head and tail operations - O(1)
val first = fruits.head // "apple"
val rest = fruits.tail // List("banana", "cherry", "date", "elderberry")
val last = fruits.last // "elderberry" - O(n)
val initial = fruits.init // All except last - O(n)
// Safe access with Option
val headOption = fruits.headOption // Some("apple")
val emptyHead = List.empty[String].headOption // None
// Index-based access - O(n)
val second = fruits(1) // "banana"
val third = fruits.apply(2) // "cherry"
// Pattern matching access
fruits match {
case head :: tail =>
println(s"First: $head, Rest: $tail")
case Nil =>
println("Empty list")
}
// Decomposing multiple elements
fruits match {
case first :: second :: rest =>
println(s"$first, $second, and ${rest.length} more")
case _ =>
println("Less than 2 elements")
}
For finding elements with conditions:
val numbers = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
// Finding elements
val firstEven = numbers.find(_ % 2 == 0) // Some(2)
val firstOver5 = numbers.find(_ > 5) // Some(6)
// Filtering
val evens = numbers.filter(_ % 2 == 0) // List(2, 4, 6, 8, 10)
// Taking and dropping
val firstThree = numbers.take(3) // List(1, 2, 3)
val afterFive = numbers.drop(5) // List(6, 7, 8, 9, 10)
val whileLessThan5 = numbers.takeWhile(_ < 5) // List(1, 2, 3, 4)
val dropWhileLessThan5 = numbers.dropWhile(_ < 5) // List(5, 6, 7, 8, 9, 10)
// Slicing
val middle = numbers.slice(3, 7) // List(4, 5, 6, 7)
Modifying Lists
Since Lists are immutable, “modifications” create new Lists. Understanding structural sharing prevents unnecessary performance concerns.
val original = List(1, 2, 3, 4, 5)
// Prepending - O(1), efficient
val withZero = 0 :: original // List(0, 1, 2, 3, 4, 5)
val withMultiple = -2 :: -1 :: original // List(-2, -1, 1, 2, 3, 4, 5)
// Appending - O(n), creates new list
val withSix = original :+ 6 // List(1, 2, 3, 4, 5, 6)
// Concatenation
val list1 = List(1, 2, 3)
val list2 = List(4, 5, 6)
val combined = list1 ++ list2 // List(1, 2, 3, 4, 5, 6)
val alsoCombi = list1 ::: list2 // Same result, List-specific
// Updating by index - O(n)
val updated = original.updated(2, 99) // List(1, 2, 99, 4, 5)
// Mapping transformations
val doubled = original.map(_ * 2) // List(2, 4, 6, 8, 10)
val strings = original.map(_.toString) // List("1", "2", "3", "4", "5")
// FlatMap for nested structures
val nested = List(List(1, 2), List(3, 4), List(5))
val flattened = nested.flatten // List(1, 2, 3, 4, 5)
val words = List("hello", "world")
val chars = words.flatMap(_.toList) // List(h, e, l, l, o, w, o, r, l, d)
Advanced Modification Patterns
Complex transformations often combine multiple operations:
case class Person(name: String, age: Int)
val people = List(
Person("Alice", 25),
Person("Bob", 30),
Person("Charlie", 25),
Person("Diana", 35)
)
// Collect - filter and map combined
val youngNames = people.collect {
case Person(name, age) if age < 30 => name.toUpperCase
} // List("ALICE", "CHARLIE")
// Partition - split into two lists
val (under30, over30) = people.partition(_.age < 30)
// GroupBy - create Map of Lists
val byAge = people.groupBy(_.age)
// Map(25 -> List(Person("Alice", 25), Person("Charlie", 25)), ...)
// Scan - running accumulation
val numbers = List(1, 2, 3, 4, 5)
val runningSum = numbers.scan(0)(_ + _) // List(0, 1, 3, 6, 10, 15)
// Patch - replace section
val original = List(1, 2, 3, 4, 5)
val patched = original.patch(1, List(99, 88), 2) // List(1, 99, 88, 4, 5)
Performance Considerations
Understanding List performance characteristics guides appropriate usage:
import scala.collection.mutable.ListBuffer
// Anti-pattern: Building list with append
def slowBuild(n: Int): List[Int] = {
var result = List[Int]()
for (i <- 1 to n) {
result = result :+ i // O(n) each iteration = O(n²) total
}
result
}
// Better: Use prepend and reverse
def betterBuild(n: Int): List[Int] = {
var result = List[Int]()
for (i <- n to 1 by -1) {
result = i :: result // O(1) each iteration = O(n) total
}
result
}
// Best: Use ListBuffer for complex construction
def bestBuild(n: Int): List[Int] = {
val buffer = ListBuffer[Int]()
for (i <- 1 to n) {
buffer += i // O(1) amortized
}
buffer.toList // O(1) conversion
}
// Benchmark comparison
def timeOperation[A](op: => A): (A, Long) = {
val start = System.nanoTime()
val result = op
val duration = System.nanoTime() - start
(result, duration)
}
// For frequent index access, consider Vector instead
val vector = Vector(1, 2, 3, 4, 5)
val indexed = vector(3) // O(log32 n) ≈ O(1) for practical sizes
Lists excel at sequential processing, pattern matching, and prepend-heavy operations. For random access or append-heavy workloads, Vector or ListBuffer provide better performance characteristics. Choose the right collection based on access patterns, not just familiarity.