Clojure Vectors has a tree-like representation which results in O(log_32 N) access for most operations: see:
Does Kotlin have anything like this?
===
Context: I’m about to have an Array, and constantly add an item to the end of it, and I’m not sure if this is going to be O(n) or O(1) in Kotlin. If O(n), what collection should I use instead?
What platform are you talking about? On JVM there are a lot different implementations covering all possible algorithms. Basic ones are in java collections framework. Additional ones are provided via libraries. On native the choice is rather limited at the moment, but you can connect native libraries.
Also if you just care about the speed of adding you can simply use a LinkedList. As long as you don’t need a fast lookup speed only iteration, push and pop it should work perfectly.
If the maximum size is known beforehand, then simple ArrayList could be even faster for write operations and much faster for read operations. For non-uniform data structures there is a TreeMap, which is very convenient, but I don’t know if there is an implementation for native.
Sorry for not clarifying:
I need it to work on both JVM and JS.
I was hoping to find something in the Kotlin stdlib, rather than some external Java lib. (Yes, I do agree that there is probably exists a java lib for this particular need.)
More generally, I’m curious if kotlin stdlib has a standard set of “persistent datastructures” (as in we create a new obj via sharihng, instead of destructive updates) – but it appears not.
I am pretty sure that there are js implementations for LinkedList out there or whatever data structure you choose to go with. You will just have to create a utility function returning them.
expect fun <T> linkedListOf(varargs elements: T): List<T>
It should not matter that your Java and JS programs use different implementations of the data structure.
It provides ArrayList implementation for JS. For anything else one needs to create a library with common module. It is not so easy though, because different platforms have different tricks to improve performance. It is not hard to hide actual implementation behind expect.
There’s a proposal for immutable collections, but nothing standard yet. Even then, a JVM optimized data structure is unlikely to translate directly to JS. For persistent collections on the JVM consider Paguro which is directly inspired by Clojure. As always, consider whether the benefits of a novel data structure over a platform one are really necessary.