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

问题描述

我最近开始学习 Scala，并且遇到了 :: (cons) 函数，该函数位于列表的前面.
在Scala 编程"一书中，它指出没有追加函数，因为追加到列表的性能为 o(n) 而前置的性能为 o(1)

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?

我想的第二个问题是当我有一个列表时我应该做什么，比如 1,2,3 并且我想在它的末尾添加 4?

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?

推荐答案

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

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.

如果用双向链表代替，x也必须设置为somelist头部的前驱，这会修改somelist.所以如果我们想在O(1)中做::而不修改原链表，我们只能使用单向链表.

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.

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

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屋！