Kotlin是否具备函数式List数据结构？有无O(1)追加的不可变List？

Kotlin标准库本身没有内置类似Scala的Cons式函数链表，但可以通过以下方式实现或使用具备该特性的数据结构：

• 借助第三方函数式库：比如Arrow库提供的NonEmptyList、ListK等结构，它们基于Cons链表实现，头部追加元素时仅需创建新的节点，时间复杂度为O(1)，且保持不可变性。
• 手动实现简易不可变链表：你可以快速定义一个基础的Cons链表结构，示例代码如下：

sealed class ImmutableList<out T> {
    object Nil : ImmutableList<Nothing>()
    data class Cons<out T>(val head: T, val tail: ImmutableList<T>) : ImmutableList<T>()

    // 重载+运算符实现头部追加
    operator fun plus(element: @UnsafeVariance T): ImmutableList<T> = Cons(element, this)
}

这个实现里，+操作直接生成新的Cons节点，无需复制原有元素，时间复杂度为O(1)。

• 标准库List的限制：Kotlin标准库的List底层基于数组实现，任何修改操作（包括头部追加）都需要复制整个数组，因此时间复杂度必然是O(N)，这是其结构特性决定的。

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