LinkedList的用例

Question

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

我的问题是:这门课的用例是什么？我发现它具有可变和不可变类型结构的问题,同时产生无效的好处.我这样说是因为:

• 该API在我看来,就好像它是一个不可改变的API( ,filter,,map 等全部返回一个新的,而不是做就地修改)droptakeLinkedList
• 至少我猜,不可变链表的所有好处都不存在,即结构之间的最大共享,因为它们仍然是可变的(通过var elem和var next.

所以基本上我们有线性访问时间,线性附加时间,线性空间等,并且没有任何东西可以在空间复杂性或推理代码的能力中显示(除了可能是O(1)前置,但它仍然是不可变列表的情况) .

我没有看到这种结构的重要好处吗？我正在寻找适用于本课程的客观测量和/或用例.

Answer 1

我要说的原因是复杂性 - 链表类允许您保持对列表中间节点的引用,并使用insert或update在该节点,而不是通过列表的头部.

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

在我确切知道某个序列发生变化的应用程序中(myReference上图),修改该位置所花费的成本要比将所有内容复制到该位置要少得多immutable.List(即我之后只插入一个新节点myReference) .

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

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

另一个原因是完整性 - 因为DoubleLinkedList并且LinkedListLike共享许多常见的基础设施,提供额外的LinkedList类是标准库大小的低成本.