MutableList和ListBuffer之间的区别

Question

Scala中scala.collection.mutable包下的MutableList和ListBuffer类有什么区别？在什么情况下会使用其中之一？

我的使用场景是有一个线性序列，我可以高效地删除第一个元素、添加前缀和后缀。什么是最好的数据结构？

- Mike

Answer 1

关于它们的工作方式做一些解释。 ListBuffer 内部使用 Nil 和 :: 来构建一个不可变的 List，并允许常数时间删除第一个和最后一个元素。为此，它保持对列表的第一个和最后一个元素的指针，并且实际上可以改变（否则不可变的）:: 类的头部和尾部（通过 :: 的 private[scala] var 成员变量的巧妙技巧）。它的 toList 方法也能够以常数时间返回正常的不可变的 List，因为它可以直接返回内部维护的数据结构。它也是不可变 List 的默认构建器（因此可以合理地预期它具有常数时间追加）。如果你调用了 toList，然后又向缓冲区追加一个元素，那么它需要与当前缓冲区中的元素数量成线性关系的时间来重新创建一个新的结构，因为它不能再更改导出的列表了。 MutableList 内部使用 LinkedList，一个（公开的，不像 ::）可变链表实现，它知道它的元素和后继（就像 ::）。MutableList 也保持对第一个和最后一个元素的指针，但是 toList 返回的时间复杂度是线性的，因为结果的 List 是从 LinkedList 中构建的。因此，在导出 List 后，它不需要重新初始化缓冲区。

根据您的要求，我认为 ListBuffer 和 MutableList 是等价的。如果你想在某个时候导出它们的内部列表，那么问问自己在哪里需要开销：当你导出列表时，并且在你继续改变缓冲区时没有开销（那么选择 MutableList），还是仅在你再次改变缓冲区时有开销，而导出时没有开销（那么选择 ListBuffer）。

我猜测在2.8的集合重构中，MutableList 先于 ListBuffer 和整个 Builder 系统出现。实际上，MutableList 主要有用于在 collection.mutable 包内部使用：它有一个private[mutable] def toLinkedList 方法，以常数时间返回结果，因此可以高效地用作维护 LinkedList 的所有结构的委托构建器。

因此，我也建议使用ListBuffer，因为它未来可能会得到更多关注和优化，而“纯可变”结构如 MutableList 和 LinkedList 则不然。

- Jean-Philippe Pellet

---

我认为ListBuffer不允许常数时间获取/删除最后一个元素！请参阅[ListBuffer.scala]（https://github.com/scala/scala/blob/2.10.x/src/library/scala/collection/mutable/ListBuffer.scala） - Bùi Việt Thành

你是正确的-看起来确实不行。太遗憾了，因为它很容易就可以做到。 - Jean-Philippe Pellet

在这个答案中，'::' 是什么意思？ - Kamal Chandraprakash

@KamalChandraprakash a :: as 返回一个新的序列，其中元素 a 被添加到现有序列 as 的前面。 - Jean-Philippe Pellet

Answer 2

这为您提供了性能特征的概述：http://www.scala-lang.org/docu/files/collections-api/collections.html；有趣的是，MutableList和ListBuffer在此方面没有区别。 MutableList的文档说它被用作Stack和Queue的基类，所以也许ListBuffer更适合从用户角度看作官方类？

- 0__

Answer 3

您想要一个可增长和可收缩的列表（为什么是列表？），并且您需要常量级别的追加和插入。好的，Buffer 是一个 trait，它具有常量级别的追加和插入，而大多数其他操作都是线性的。我猜测实现了 Buffer 的类 ListBuffer 具有常量级别的删除第一个元素的时间复杂度。

因此，我的建议是使用 ListBuffer。

- Daniel C. Sobral

Answer 4

首先，让我们了解一下Scala中的几个相关类型

List - 一个不可变集合。它是一种递归实现，即列表的一个实例有两个主要元素：头部和尾部，其中尾部引用另一个List。

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

LinkedList - 一种可变的集合，由一系列链接的节点组成，每个节点包含一个值和一个指向下一个节点的指针。

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

LinkedList[T]
  first: Node[T]

列表（List）是一种函数式数据结构（不可变性），相对于在命令式语言中更为常见的链表（LinkedList）。

现在，让我们看看：

ListBuffer - 由List支持的可变缓冲区实现。

MutableList - 基于LinkedList实现（如果它被命名为LinkedListBuffer，那将更为自说明）。

两者大多数操作都提供类似的复杂度范围。

但是，如果您从MutableList请求一个List，那么它必须将现有的线性表示转换为递归表示，这需要O(n)，正如@Jean-Philippe Pellet所指出的那样。但是，如果您从MutableList请求一个Seq，则复杂度为O(1)。

因此，我认为选择取决于您代码的具体情况和个人偏好。尽管我怀疑有更多的List和ListBuffer存在。

- smartnut007

Answer 5

请注意，ListBuffer是final/sealed的，而您可以扩展MutableList。根据您的应用程序，可扩展性可能会很有用。

- Herc