Difference between MutableList and ListBuffer

What is the diffe开发者_运维百科rence between Scala's MutableList and ListBuffer classes in scala.collection.mutable? When would you use one vs the other?

My use case is having a linear sequence where I can efficiently remove the first element, prepend, and append. What's the best structure for this?

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.

This gives you an overview of the performance characteristics: http://www.scala-lang.org/docu/files/collections-api/collections.html ; interestingly, MutableList and ListBuffer do not differ there. The documentation of MutableList says it is used internally as base class for Stack and Queue, so maybe ListBuffer is more the official class from the user perspective?

You want a list (why a list?) that is growable and shrinkable, and you want constant append and prepend. Well, Buffer, a trait, has constant append and prepend, with most other operations linear. I'm guessing that ListBuffer, a class that implements Buffer, has constant time removal of the first element.

So, my own recommendation is for ListBuffer.

First, lets go over some of the relevant types in Scala

List - An Immutable collection. A Recursive implementation i.e . i.e An instance of list has two primary elements the head and the tail, where the tail references another List.

List[T]
  head: T
  tail: List[T]  //recursive

LinkedList - A mutable collection defined as a series of linked nodes, where each node contains a value and a pointer to the next node.

Node[T]
  value: T
  next: Node[T]  //sequential

LinkedList[T]
  first: Node[T]

List is a functional data structure (immutability) compared to LinkedList which is more standard in imperative languages.

Now, lets look at

ListBuffer - A mutable buffer implementation backed by a List.

MutableList - An implementation based on LinkedList ( Would have been more self explanatory if it had been named LinkedListBuffer instead )

They both offer similar complexity bounds on most operations.

However, if you request a List from a MutableList, then it has to convert the existing linear representation into the recursive representation which takes O(n) which is what @Jean-Philippe Pellet points out. But, if you request a Seq from MutableList the complexity is O(1).

So, IMO the choice narrows down to the specifics of your code and your preference. Though, I suspect there is a lot more List and ListBuffer out there.

Note that ListBuffer is final/sealed, while you can extend MutableList. Depending on your application, extensibility may be useful.