f# - 为什么将不可变列表实现为链表？

Question

根据 F# 的 list documentation :

“F# 中的列表是有序的、 不可变的 系列相同类型的元素”

“F# 中的列表被实现为 单向链表 ”

为什么不在内存中连续实现它，因为它是不可变的，因此具有固定的大小？为什么要使用 F# list而不是 F# array ?

Answer 1

它们用于不同的目的，例如:

您在 F# 中使用数组来存储需要以相对较低的开销随机访问的大量数据。

当您需要在递归函数的迭代中积累一些东西时，F# 中的 List 很有用。数组在这里不能很好地发挥作用，因为它们的大小是固定的。

带 list ，您可以在 O(M) 时间内将 ListM(大小 M)的所有元素添加到 ListN(大小 N)。同样，您可以在 O(1) 时间内将单个元素添加到任何列表中。