《Scala编程》中两种队列实现的性能疑问及原因解析

嘿，我来帮你把这些问题拆解开，结合Scala List的特性给你讲明白：

问题1：两个队列的tail实现是否均耗时与队列元素数量成正比？ #

答案是否，两者的tail性能差异很大：

• 对于SlowAppendQueue的tail：它调用的是elems.tail，Scala List的tail操作是直接返回链表头部之后的剩余子列表，这是O(1)常数时间操作——因为List是单链表结构，头部节点直接持有指向剩余元素的引用，不需要遍历整个队列，耗时和元素数量完全无关。
• 对于SlowHeadQueue的tail：它调用的是smele.init，init方法需要返回去掉最后一个元素的列表。由于Scala List只能从头部开始遍历，要找到倒数第二个元素并截断链表，必须完整遍历整个队列，这是O(n)线性时间操作，耗时和队列元素数量成正比。

问题2：第二个队列的head实现比第一个慢，耗时与队列长度成正比，原因是什么？Scala的List是否为带指针的链表结构？ #

首先明确：Scala的List确实是单链表结构，每个节点（内部是Cons类）包含两个部分：当前元素，以及一个指向下一个节点的引用（也就是剩余的List）。这种结构决定了它只能高效地从头部进行操作，尾部没有直接的访问入口。

再看两个head的差异：

• SlowAppendQueue的head直接调用elems.head，这是O(1)操作——直接取单链表的第一个元素，一步到位，不需要任何遍历。
• SlowHeadQueue的head调用smele.last，last方法必须从链表头部开始，逐个遍历直到最后一个元素才能返回结果，这是O(n)操作，队列越长，遍历的元素越多，耗时也就越长，所以它的head比第一个队列慢很多。

问题3：为何Odersky认为第二个类的tail实现存在问题，而第一个则没有？ #

核心原因还是操作的时间复杂度带来的性能差异：

• SlowAppendQueue的tail是O(1)操作，不管队列有多长，都能快速生成新的子队列；它的性能痛点其实是enqueue（用:::拼接两个列表，需要遍历整个原队列，是O(n)操作），但tail本身的实现是高效的，没有问题。
• SlowHeadQueue的tail是O(n)操作，这会引发连锁性能问题：比如如果我们要遍历整个队列，需要连续调用tail n次，总耗时会达到O(n²)——这在队列元素较多时，性能会急剧下降，完全不符合队列应该具备的高效尾部删除（或者说子队列生成）的特性，所以Odersky认为它的tail实现存在严重问题。

内容的提问来源于stack exchange，提问作者Jwan622