Difference between MutableList and ListBuffer

by

A little explanation on how they work.

ListBuffer uses internally Nil and :: to build an immutable List and allows constant-time removal of the first and last elements. To do so, it keeps a pointer on the first and last element of the list, and is actually allowed to change the head and tail of the (otherwise immutable) :: class (nice trick allowed by the private[scala] var members of ::). Its toList method returns the normal immutable List in constant time as well, as it can directly return the structure maintained internally. It is also the default builder for immutable Lists (and thus can indeed be reasonably expected to have constant-time append). If you call toList and then again append an element to the buffer, it takes linear time with respect to the current number of elements in the buffer to recreate a new structure, as it must not mutate the exported list any more.

MutableList works internally with LinkedList instead, an (openly, not like ::) mutable linked list implementation which knows of its element and successor (like ::). MutableList also keeps pointers to the first and last element, but toList returns in linear time, as the resulting List is constructed from the LinkedList. Thus, it doesn’t need to reinitialize the buffer after a List has been exported.

Given your requirements, I’d say ListBuffer and MutableList are equivalent. If you want to export their internal list at some point, then ask yourself where you want the overhead: when you export the list, and then no overhead if you go on mutating buffer (then go for MutableList), or only if you mutable the buffer again, and none at export time (then go for ListBuffer).

My guess is that in the 2.8 collection overhaul, MutableList predated ListBuffer and the whole Builder system. Actually, MutableList is predominantly useful from within the collection.mutable package: it has a private[mutable] def toLinkedList method which returns in constant time, and can thus efficiently be used as a delegated builder for all structures that maintain a LinkedList internally.

So I’d also recommend ListBuffer, as it may also get attention and optimization in the future than “purely mutable” structures like MutableList and LinkedList.

More Related Contents:

  1. Scala 2.8 breakOut
  2. Is the Scala 2.8 collections library a case of “the longest suicide note in history”? [closed]
  3. Why is Scala’s immutable Set not covariant in its type?
  4. What is the difference between JavaConverters and JavaConversions in Scala?
  5. When should I choose Vector in Scala?
  6. What does param: _* mean in Scala?
  7. Scala 2.8 collections design tutorial
  8. withFilter instead of filter
  9. What type to use to store an in-memory mutable data table in Scala?
  10. Scala Map implementation keeping entries in insertion order?
  11. Stream vs Views vs Iterators
  12. How to read files from resources folder in Scala?
  13. Function returns an empty List in Spark
  14. Scala: Why does Seq.contains take an Any argument, instead of an argument of the sequence type?
  15. Reduce, fold or scan (Left/Right)?
  16. Scala Sets contain the same elements, but sameElements() returns false
  17. Scala: Parallel collection in object initializer causes a program to hang
  18. Scala best way of turning a Collection into a Map-by-key?
  19. scala parallel collections degree of parallelism
  20. Spark extracting values from a Row
  21. How to pass -D parameter or environment variable to Spark job?
  22. Pattern matching on generic type in Scala
  23. Escape a dollar sign in string interpolation
  24. Explicit self-references with no type / difference with ”this”
  25. Getting the index of the current loop in Play! 2 Scala template
  26. Addition of two RDD[mllib.linalg.Vector]’s
  27. Differences between these three ways of defining a function in Scala
  28. How to reference external sbt project from another sbt project?
  29. Dynamically compiling scala class files at runtime in Scala 2.11
  30. How to instantiate an instance of type represented by type parameter in Scala

Leave a Comment