为什么追加到列表不好？ [英] Why is appending to a list bad?

问题描述

我最近开始学习scala，并且遇到了 :: （cons）函数，这个函数前缀为列表。

在Programming in Scala一书中，它指出不存在追加函数，因为追加到列表的性能为o（n），而预先计算的性能为o（1）

性能是否依赖于实现？是不是可以简单地使用向前和向后的链接来实现列表并将第一个和最后一个元素存储在容器中？

第二个问题我想是什么我应该做什么，当我有一个列表，说1,2,3，我想在它的结尾添加4？

解决方案

关键是 x :: somelist 不会改变 somelist ，而是会创建一个新列表，其中包含x后跟所有元素 somelist 。这可以在O（1）时间完成，因为您只需要将 somelist 设置为 x 新创建的单链表。

如果使用双向链接列表， x 也必须被设置为<$ c的前任$ c> somelist 的头，它会修改 somelist 。因此，如果我们希望能够在O（1）中执行 :: 而不修改原始列表，那么我们只能使用单个链表。

关于第二个问题：您可以使用 ::: 将单个元素列表连接到列表的末尾。这是一个O（n）操作。

 列表（1,2,3）:::列表（4）
  

I've recently started learning scala, and I've come across the :: (cons) function, which prepends to a list.
In the book "Programming in Scala" it states that there is no append function because appending to a list has performance o(n) whereas prepending has a performance of o(1)

Something just strikes me as wrong about that statement.

Isn't performance dependent on implementation? Isn't it possible to simply implement the list with both forward and backward links and store the first and last element in the container?

The second question I suppose is what I'm supposed to do when I have a list, say 1,2,3 and I want to add 4 to the end of it?

解决方案

The key is that x :: somelist does not mutate somelist, but instead creates a new list, which contains x followed by all elements of somelist. This can be done in O(1) time because you only need to set somelist as the successor of x in the newly created, singly linked list.

If doubly linked lists were used instead, x would also have to be set as the predecessor of somelist's head, which would modify somelist. So if we want to be able to do :: in O(1) without modifying the original list, we can only use singly linked lists.

Regarding the second question: You can use ::: to concatenate a single-element list to the end of your list. This is an O(n) operation.

List(1,2,3) ::: List(4)

这篇关于为什么追加到列表不好？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！