• ETS ordered_set tables, for mutable AVL trees (for when you want to cheaply apply a sequence of random mutations to a collection of terms without building a lot of garbage);
• The process dictionary (https://www.erlang.org/course/advanced#dict), a mutable per-process hash-map data-structure, for when ETS ordered_set tables have too much inter-process copying overhead.
All that, plus Erlang lists (singly-linked lists) are really cheap the way Erlang does them. (Each Erlang actor-process gets its own heap that gets independently GCed; short-lived processes never experience even a single GC, so allocating linked-list nodes (by consing to the beginning of a list) is just a matter of incrementing the actor-process's heap's free pointer—about the same level of optimality you'd hope to get from pushing to the end of a vector.)
• http://erlang.org/doc/man/atomics.html and http://erlang.org/doc/man/counters.html for cheap, mutable uint64 arrays;
• The http://erlang.org/doc/man/array.html module for a functional persistent vector abstraction (similar to the one in Clojure);
• ETS ordered_set tables, for mutable AVL trees (for when you want to cheaply apply a sequence of random mutations to a collection of terms without building a lot of garbage);
• The process dictionary (https://www.erlang.org/course/advanced#dict), a mutable per-process hash-map data-structure, for when ETS ordered_set tables have too much inter-process copying overhead.
All that, plus Erlang lists (singly-linked lists) are really cheap the way Erlang does them. (Each Erlang actor-process gets its own heap that gets independently GCed; short-lived processes never experience even a single GC, so allocating linked-list nodes (by consing to the beginning of a list) is just a matter of incrementing the actor-process's heap's free pointer—about the same level of optimality you'd hope to get from pushing to the end of a vector.)