Non deprecated way of appending an element to a List in Scala 2.7.5?

Question

How do you add an element to a List in Scala 2.7.5, without creating a new List and without using a deprecated solution.

Answer 1

The following is not true for certain operations List implementation. Thanks to sschaef for the correction.

---

A very important point that I haven't seen mentioned here is that creating a new collection from another collection necessarily isn't as expensive in Scala as it is in Java. This concept is called persistence. Daniel Spiewak lays it out in his article, http://www.codecommit.com/blog/scala/scala-collections-for-the-easily-bored-part-1.

Here is a snippet of the relevant section,

Of course, the natural question which comes to mind is, what about performance? If each invocation actually creates a brand new Set for every recursive call, doesn’t that require a lot of inefficient object copying and heap operations? Well, as it turns out, this isn’t really the case. Yes, a new instance must be created at each turn, which is is a comparatively expensive operation on the JVM, but almost nothing is being copied. All of Scala’s immutable data structures have a property known as persistence, which means that you don’t copy the data out of the old container when creating a new, you just have the new reference the old and treat all of its contents as if they were its own.

So while it will be less expensive to use a mutable list it isn't as much of a concern as it is under Java.

Answer 2

Non deprecated way of appending an element to a List in Scala 2.7.5?

That does not exist, and it will never exist.

How do you add an element to a List in Scala 2.7.5, without creating a new List and without using a deprecated solution.

Use :::

val newList = element :: oldList

Or, if list is a var,

list ::= element

It does not create a new List (though, it creates a new ::, also known as cons), and it adds an element to it.

If you want to append elements to a sequence without creating a new sequence, use a mutable data structure.

Answer 3

It's worth pointing out that List has a very specific meaning in scala, which is not equivalent to the java.util.List interface. List is a sealed, abstract class representing a recursive data-structure which has a head and a tail. (There do exist Java list-like structures in scala, some of which are mutable.)

Scala's Lists are immutable; modifying a list in any way is not possible, although you can create a new list be prepending to an existing one (which gives a new object back). Even though they are immutable, the structure is no more expensive in terms of object creation than, say, appending to a java.util.LinkedList

The + method has been deprecated for good reason because it is inefficient; instead use:

val newList = theList ::: List(toAppend)

I suppose a different way would be to prepend with 2 reversals:

val newList = (toAppend :: theList.reverse).reverse

I doubt this is any more efficient! In general, if I want append behaviour, I use prepend and then reverse (at the point of needing to access the list):

val newList = toAppend :: theList
//much later! I need to send the list somewhere...
target ! newList.reverse

Answer 4

You could use a ListBuffer, which provides constant time append:

val buffer = new scala.collection.mutable.ListBuffer[Int]
buffer += 1
buffer += 2
val list = buffer.toList

Answer 5

This should do it: http://www.scala-lang.org/docu/files/api/scala/collection/mutable/SingleLinkedList.html#append%28This%29

Or this: http://www.scala-lang.org/docu/files/api/scala/collection/mutable/ListBuffer.html#%2B%3A%28A%29

The basic trick is to use a mutable List (or class with similiar functionality)

Answer 6

The += method on a list is deprecated because it adds an element to the tail, which is expensive. The least expensive way of adding an element to a list is to add to the head using ::=.

So the deprecation warning is a subtle hint that you should redesign your program to work by prepending instead of appending:

scala> var l = List(1, 2, 3)
l: List[Int] = List(1, 2, 3)

scala> l ::= 4

scala> l
res1: List[Int] = List(4, 1, 2, 3)

(Note that ::= and += on a var are not real methods, but sugar for l = l :: elem, etc)