为什么在Scala List前面添加一个常量时间操作,但是附加一个线性

发布时间：2020-12-16 09:08:54 所属栏目：安全来源：网络整理

导读：我现在正在从Odersky的“ Scala编程”中学习 Scala,我刚读完这篇文章 …the time it takes to append to a list grows linearly with the size of the list,whereas prepending with :: takes constant time… 为什么在线性时间附加到附加到列表但是只有不变

我现在正在从Odersky的“ Scala编程”中学习 Scala,我刚读完这篇文章

…the time it takes to append to a list grows linearly with the size of the
list,whereas prepending with :: takes constant time…

为什么在线性时间附加到附加到列表但是只有不变的时间来预先添加到列表中.我目前的猜测是它以某种方式在内部实现为链接列表,这将解释两个操作之间的差异.在这种情况下,如何实现具有恒定时间附加的ListBuffers？

解决方法

它们都与链接列表类似地实现.不同之处在于ListBuffer还包含指向列表尾部的指针. Scala的源代码是开放的,如果你对它的细节感到好奇,你可以在github上探索它(例如,这里是 ListBuffer的附加代码)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!