scala MutableList 和 ListBuffer 的区别

Difference between MutableList and ListBuffer

提问by Mike

What is the difference between Scala's MutableListand ListBufferclasses in scala.collection.mutable? When would you use one vs the other?

ScalaMutableList和 中的ListBuffer类有scala.collection.mutable什么区别？你什么时候会使用一个和另一个？

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?

我的用例是有一个线性序列，我可以有效地删除第一个元素、前置和附加。什么是最好的结构？

回答by Jean-Philippe Pellet

A little explanation on how they work.

关于它们如何工作的一点解释。

ListBufferuses internally Niland ::to build an immutable Listand allows constant-time removal of the first and lastelements. 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] varmembers of ::). Its toListmethod returns the normal immutable Listin 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 toListand 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.

ListBuffer在内部使用Nil并::构建一个不可变的List并允许恒定时间删除第一个和最后一个元素。为此，它在列表的第一个和最后一个元素上保留一个指针，并且实际上允许更改（否则不可变）::类的头部和尾部（private[scala] var成员允许的好技巧::）。它的toList方法同样List在常数时间内返回正常的不可变，因为它可以直接返回内部维护的结构。它也是 immutable Lists的默认构建器（因此确实可以合理地预期具有恒定时间附加）。如果你打电话toList然后再次将一个元素附加到缓冲区，相对于缓冲区中的当前元素数量，重新创建一个新结构需要线性时间，因为它不能再改变导出的列表。

MutableListworks internally with LinkedListinstead, an (openly, not like ::) mutable linked list implementation which knows of its element and successor (like ::). MutableListalso keeps pointers to the first and last element, but toListreturns in linear time, as the resulting Listis constructed from the LinkedList. Thus, it doesn't need to reinitialize the buffer after a Listhas been exported.

MutableListLinkedList相反，在内部使用一个（公开的，不喜欢的::）可变链表实现，它知道它的元素和后继者（比如::）。MutableList还保留指向第一个和最后一个元素的指针，但toList在线性时间内返回，因为结果List是从LinkedList. 因此，List在导出a 后不需要重新初始化缓冲区。

Given your requirements, I'd say ListBufferand MutableListare 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).

鉴于您的要求，我会说ListBuffer并且MutableList是等效的。如果你想在某个时候导出他们的内部列表，那么问问自己你想要的开销：当你导出列表时，如果你继续改变缓冲区（然后去 for MutableList），或者只有当你改变缓冲区时没有开销再次，在导出时没有（然后去ListBuffer）。

My guess is that in the 2.8 collection overhaul, MutableListpredated ListBufferand the whole Buildersystem. Actually, MutableListis predominantly useful from within the collection.mutablepackage: it has a private[mutable] def toLinkedListmethod which returns in constant time, and can thus efficiently be used as a delegated builder for all structures that maintain a LinkedListinternally.

我的猜测是在 2.8 收藏大修中，MutableList早于ListBuffer和整个Builder系统。实际上，MutableList在collection.mutable包内主要是有用的：它有一个private[mutable] def toLinkedList在恒定时间内返回的方法，因此可以有效地用作所有LinkedList内部维护的结构的委托构建器。

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

所以我也推荐ListBuffer，因为它在未来也可能比像MutableListand这样的“纯可变”结构更受关注和优化LinkedList。

回答by 0__

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

这为您提供了性能特征的概述：http://www.scala-lang.org/docu/files/collections-api/collections.html；有趣的是，MutableList并ListBuffer没有什么不同。的文档MutableList说它在内部用作Stackand 的基类Queue，所以ListBuffer从用户的角度来看，它可能更像是官方类？

回答by Daniel C. Sobral

You want a list (why a list?) that is growableand 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.

您想要一个可增长和可收缩的列表（为什么是列表？），并且您想要不断追加和前置。嗯，Buffer一个特征，具有恒定的附加和前置，大多数其他操作都是线性的。我猜ListBuffer，一个实现了 的类Buffer，有固定的时间移除第一个元素。

So, my own recommendation is for ListBuffer.

所以，我自己的建议是针对ListBuffer.

回答by smartnut007

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

首先，让我们回顾一下 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- 一个不可变的集合。递归实现，即。即列表的实例有两个主要元素，头和尾，其中尾引用另一个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.

LinkedList- 定义为一系列链接节点的可变集合，其中每个节点包含一个值和一个指向下一个节点的指针。

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.

与 LinkedList 相比，List 是一种函数式数据结构（不变性），后者在命令式语言中更为标准。

Now, lets look at

现在，让我们看看

ListBuffer- A mutable buffer implementation backed by a List.

ListBuffer- 一个由List.

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

MutableList- 基于 LinkedList 的实现（如果LinkedListBuffer改为命名会更不言自明）

They both offer similar complexity bounds on most operations.

它们都为大多数操作提供了相似的复杂度界限。

However, if you request a Listfrom 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 Seqfrom MutableListthe complexity is O(1).

但是，如果您List从 a请求 a MutableList，那么它必须将现有的线性表示转换为采用 O(n) 的递归表示，这就是@Jean-Philippe Pellet 指出的。但是，如果您Seq从MutableList复杂度中请求 a是 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 Listand ListBufferout there.

因此，IMO 的选择范围缩小到您的代码细节和您的偏好。虽然，我怀疑是有很多List和ListBuffer在那里。

回答by Herc

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

请注意，ListBuffer 是最终/密封的，而您可以扩展 MutableList。根据您的应用程序，可扩展性可能很有用。