scala - MutableList 和 ListBuffer 的区别

Question

Scala 的MutableList 有什么区别？和 ListBuffer scala.collection.mutable 中的类(class)?您什么时候使用一个与另一个？

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

Answer 1

首先，让我们回顾一下 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]

与在命令式语言中更标准的 LinkedList 相比，List 是一种功能数据结构(不变性)。

现在，让我们看看

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

MutableList - 基于 LinkedList 的实现(如果将其命名为 LinkedListBuffer 会更容易解释)

They both offer similar complexity bounds on most operations.

但是，如果您请求 List来自 MutableList ，然后它必须将现有的线性表示转换为采用 O(n) 的递归表示，这就是@Jean-Philippe Pellet 指出的。但是，如果您请求 Seq来自 MutableList复杂度为 O(1)。

因此，IMO 的选择范围缩小到您的代码细节和您的偏好。不过，我怀疑还有更多 List和 ListBuffer在那里。