160

In what cases I should use Array(Buffer) and List(Buffer). Only one difference that I know is that arrays are nonvariant and lists are covariant. But what about performance and some other characteristics?

Eugene Yokota
  • 94,654
  • 45
  • 215
  • 319
Jeriho
  • 7,129
  • 9
  • 41
  • 57

3 Answers3

170

Immutable Structures

The Scala List is an immutable recursive data structure which is such a fundamental structure in Scala, that you should (probably) be using it much more than an Array (which is actually mutable - the immutable analog of Array is IndexedSeq).

If you are coming from a Java background, then the obvious parallel is when to use LinkedList over ArrayList. The former is generally used for lists which are only ever traversed (and whose size is not known upfront) whereas the latter should be used for lists which either have a known size (or maximum size) or for which fast random access is important.

Mutable Structures

ListBuffer provides a constant-time conversion to a List which is reason alone to use ListBuffer if such later conversion is required.

A scala Array should be implemented on the JVM by a Java array, and hence an Array[Int] may be much more performant (as an int[]) than a List[Int] (which will box its contents, unless you are using the very latest versions of Scala which have the new @specialized feature).

However, I think that the use of Arrays in Scala should be kept to a minimum because it feels like you really need to know what is going on under the hood to decide whether your array really will be backed by the required primitive type, or may be boxed as a wrapper type.

oxbow_lakes
  • 133,303
  • 56
  • 317
  • 449
  • also see http://stackoverflow.com/questions/3213368/strange-behaviour-of-the-array-type and http://stackoverflow.com/questions/2481149/why-does-array0-1-2-array0-1-2-not-return-the-expected-result the definition of "equals" for Arrays is that they refer to the same array – oluies Jul 09 '10 at 18:42
139

In addition to the answers posted already, here are some specifics.

While an Array[A] is literally a Java array, a List[A] is an immutable data structure that is either Nil (the empty list) or consists of a pair (A, List[A]).

Performance differences

                          Array  List
Access the ith element    θ(1)   θ(i)
Delete the ith element    θ(n)   θ(i)
Insert an element at i    θ(n)   θ(i)
Reverse                   θ(n)   θ(n)
Concatenate (length m,n)  θ(n+m) θ(n)
Count the elements        θ(1)   θ(n)

Memory differences

                          Array  List
Get the first i elements  θ(i)   θ(i)
Drop the first i elements θ(n-i) θ(1)
Insert an element at i    θ(n)   θ(i)
Reverse                   θ(n)   θ(n)
Concatenate (length m,n)  θ(n+m) θ(n)

So unless you need rapid random access, need to count elements, or for some reason you need destructive updates, a List is better than an Array.

Apocalisp
  • 34,834
  • 8
  • 106
  • 155
  • Do these Os have to consider the time to copy the List? I assume you are doing the test like this, e.g.: `list = list.drop(i)`. Or, Does occur some magic behind the hood? –  Jan 14 '13 at 14:10
  • 2
    This takes into account copying lists and arrays when necessary. Note that things like `drop` never need to copy the part of the list that wasn't dropped. E.g. `(x::xs).drop(1)` is exactly `xs`, not a "copy" of `xs`. – Apocalisp Jan 14 '13 at 15:05
  • Horrible Reverse and Concatenate complexities for lists… in C you could quite easily get O(1) complexity. I'm sure the same is true if it were implemented properly in Scala >. – A T Oct 07 '13 at 10:10
  • 7
    These asymptotics have nothing to do with Scala whatsoever. The same data structure in C will be exactly as fast up to constant factors. – Apocalisp Oct 07 '13 at 15:54
  • There is one more fundamental memory difference: `Array` holds one reference for each element where `List` holds two - one for an element and one for the rest of the list. For primitive types it means twice as big memory consumption just for storing it in memory. – icl7126 Jun 06 '16 at 06:34
  • 1
    @Apocalisp Do you have a reference or under what conditions did you determine this information? – Phil Jun 18 '16 at 18:52
  • 1
    @Phil These are asymptotics, not measurements. They will hold true under all conditions. – Apocalisp Jun 19 '16 at 03:15
  • @icl7126 A small constant factor is not a fundamental difference in my view. – Apocalisp Aug 22 '18 at 13:52
20

An Array is mutable, meaning you can change the values of each index, while a List (by default) is immutable, meaning that a new list is created every time you do a modification. In most cases it is a more "functional" style to work with immutable datatypes and you should probably try and use a List with constructs like yield, foreach, match and so forth.

For performance characteristics, an Array is faster with random access to elements, whereas a List is faster when prepending (adding) new elements. Iterating over them is comparable.

leonm
  • 6,454
  • 30
  • 38
  • @leonm - apols, I thought the OP was asking exclusively about the *Buffer classes, I realize that they were also asking about the "normal" ones! – oxbow_lakes Apr 26 '10 at 11:35
  • 2
    It's usually faster to append to an ArrayBuffer than to prepend to a List (or add an element to a ListBuffer) since lists require the creation of a wrapper object while ArrayBuffer merely needs to copy the object (on average about twice) to a new array. Two copies are usually faster than one object creation, so ArrayBuffer append usually beats List prepend. – Rex Kerr Apr 26 '10 at 20:16
  • array performs much faster than list when `iterate over`, because of cache – Bin Dec 13 '16 at 03:07