Insert a new element in a specified position of a list
In the Scala course by his eminence Martin Odersky himself, he implements it similarly to
def insert(list: List[Any], i: Int, value: Any): List[Any] = list match {
case head :: tail if i > 0 => head :: insert(tail, i-1, value)
case _ => value :: list
}
One traversal at most.
You can also use xs.patch(i, ys, r)
, which replaces r
elements of xs
starting with i
by the patch ys
, by using r=0
and by making ys
a singleton:
List(1, 2, 3, 5).patch(3, List(4), 0)
Type Safety
The most glaring thing I see is the lack of type safety / loss of type information. I would make the method generic in the list's element type:
def insert[T](list: List[T], i: Int, value: T) = {
list.take(i) ++ List(value) ++ list.drop(i)
}
Style
If the body only consists of a single expression, there is no need for curly braces:
def insert[T](list: List[T], i: Int, value: T) =
list.take(i) ++ List(value) ++ list.drop(i)
Efficiency
@Marth's comment about using List.splitAt
to avoid traversing the list twice is also a good one:
def insert[T](list: List[T], i: Int, value: T) = {
val (front, back) = list.splitAt(i)
front ++ List(value) ++ back
}
Interface
It would probably be convenient to be able to insert more than one value at a time:
def insert[T](list: List[T], i: Int, values: T*) = {
val (front, back) = list.splitAt(i)
front ++ values ++ back
}
Interface, take 2
You could make this an extension method of List
:
implicit class ListWithInsert[T](val list: List[T]) extends AnyVal {
def insert(i: Int, values: T*) = {
val (front, back) = list.splitAt(i)
front ++ values ++ back
}
}
List(1, 2, 3, 6).insert(3, 4, 5)
// => List(1, 2, 3, 4, 5, 6)
Closing remarks
Note, however, that inserting into the middle of the list is just not a good fit for a cons list. You'd be much better off with a (mutable) linked list or a dynamic array instead.