13

这篇文章只讨论scala.collection.mutable.LinkedList。其他实现不是这个线程的主题。

我的问题是：这个类的用例是什么？我发现它具有可变和不可变结构类型的问题，同时没有产生任何好处。我这么说是因为：

  • API 在我看来就像是一个不可变的 API（filter, map,drop等都take返回一个新LinkedList的而不是进行就地修改）
  • 不可变链表的所有好处至少我猜是不存在的，即结构之间的最大共享，因为它们仍然是可变的（通过var elem和var next.

所以基本上我们有一个线性访问时间、线性附加时间、线性空间等，并且在空间复杂性或推理代码的能力方面没有任何表现（除了 O(1) 前置，但它仍然是不可变列表的情况） .

我看不到这种结构的重要好处吗？我正在寻找适用于此类的客观度量和/或用例。

4

1 回答 1

5

我想说原因是复杂性 - 链表类允许您保存对列表中间节点的引用，并在该节点处使用insertor update，而不是通过列表的头部。

[] --> [] --> ... --> [] --> ... --> [] --|
^                     ^
head                  myReference

在我确切知道某个序列的更改将发生在哪里的应用程序中（myReference如上），修改该位置的成本要比将所有内容复制到该位置的成本要低得多immutable.List（即我只是在之后插入一个新节点myReference） .

                             myNewNode
                             v
[] --> [] --> ... --> [] --> [] ---> ... --> [] --|
^                     ^
head                  myReference

这种应用程序的一个示例 - 一个L 系统，您可以在其中扩展字符串的一部分。就地插入新节点比每次需要扩展时复制整个字符串要便宜得多。

另一个原因是完整性——因为DoubleLinkedList和LinkedListLike共享许多通用基础设施，提供额外的LinkedList类对标准库的大小来说是低成本的。

于 2012-10-02T15:44:34.020 回答