Scala 中的惯用方式在列表上获得 O(1) 索引查找

Question

来自 List.scala 的 javadoc：

 Time: List has O(1) prepend and head/tail access. Most other operations are `O(n)` on the number of elements in the list.
 *  **This includes the index-based lookup of elements**, `length`, `append` and `reverse`.

这与 Java 中的 ArrayList 比较（不利）。（是的，我意识到它是可变的，而 List 不是 .. 但放弃这种性能是不可能的）。

那么什么是 Scala 中可能的/首选的“go-to”不可变列表实现，O(1) 用于基于索引的查找（最好也用于长度）。可以理解/接受 append 和 reverse 是 O(n)

更新 Om-nom-nom 提名的 Vector，我同意（等待他对此做出真正的回答）。

来自 Vector 上的 javadoc：

Vector 是一种通用的、不可变的数据结构。它在有效的恒定时间内提供随机访问和更新，以及非常快速的追加和前置。因为向量在快速随机选择和快速随机函数更新之间取得了很好的平衡，所以它们目前是不可变索引序列的默认实现。

Answer 1

对于不可变结构，您可能需要一个Vector; 与数组相比，直接访问速度非常慢，但对于查找和重复追加或前置，它接近 O(1) 。（然而，混合的附加/前置混淆了它。）

ArrayBuffer是可变的，并且java.util.ArrayList与上面的所有 Scala 集合好东西基本相同的数据结构。（地图等）

如果您喜欢列表的类似堆栈的属性，ArrayStack则在堆栈顶部元素为 0（ArrayStack也是可变的）的情况下具有 push/pop 和索引。