scala - 使用 Scala 从末尾进行恒定时间追加和检索

Question

所以我想我需要使用像 DoubleLinkedList 这样的结构，但是当我在 scala 中看到 DLL 的实现时，似乎它没有为 last() 函数或其他快速访问结尾的东西提供有效的实现。这是我在实现中看到的：

  def last: A = {
    var lst = head
    for (x <- this)
      lst = x
    lst
  }

它看起来是线性的，不是吗？也许DLL应该覆盖这个函数，你怎么看？

Answer 1

双重链接DoubleLinkedListLike仅指沿列表前进和后退。没有指向列表末尾的直接指针。

如果您只需要对最后一个元素进行快速访问和更新，则可以使用 a Listwith reverse order。这取决于您需要哪些其他操作。使用最后一个指针滚动您自己的 DLL 非常简单，但如果您只需要一个性能良好的现成结构，请查看不可变的Vector. 它具有准恒定的更新和访问（一些 log32 因子是“有效”恒定的）。

---

如果您真的想要一个可变类型，请参阅官方文档以获取概述和功能。即查看 DLL 的用途。“可变列表”部分涵盖了快速附加的情况。